¡LO SENTIMOS! ¡MI ERROR! Gracias por su recordatorio, descubrí f (0, k) == f (k, 0) == 1. Esta pregunta es acerca de cómo contar el número de caminos más cortos de la cuadrícula (0,0) a (m, n)Encuentra la fórmula de esta ecuación de recurrencia binaria? f (m, n) = f (m-1, n) + f (m, n-1)
Tengo que resolver la siguiente ecuación ahora, descubrir exactamente qué es f (m, n) igual a.
1) f(m,n) = 0 : when (m,n) = (0,0)
**2) f(m,n) = 1 : when f(0,k) or f(k,0)**
3) f(m,n) = f(m-1,n) + f(m,n-1) : when else
por ejemplo:
1) f(0,0) = 0;
2) f(0,1) = 1; f(2,0) = 1;
3) f(2,1) = f(1,1) + f(2,0) = f(0, 1) + f(1, 0) + f(2, 0) = 1 + 1 + 1 = 3
recuerdo que es una forma estándar para resolver ese tipo de ecuación de recurrencia binario como aprendí en mi clase de algoritmo hace varios años, pero simplemente no puedo recordar por ahora .
¿Alguien podría dar alguna pista? O una palabra clave cómo encontrar la respuesta?
¿Quiere decir que usted necesita para encontrar la fórmula que no utiliza la recursividad? ¿O solo un algoritmo que calcula la recurrencia de manera eficiente? – svick
¿Estás seguro de que f (2,1) = 3? Leo f (2,1) = f (1,1) + f (2,0) = (f (0,1) + f (1,0)) + f (2,0) = (1 + 1) + 2 = 2 + 2 = 4 –
Estás buscando la solución de forma cerrada ¿no? – ElKamina