} Pensar en una solución recursiva, o una relación de recurrencia es la parte más importante para resolver el problema de DP. Es posible que no escriba explícitamente la función recursiva que implica el cálculo y la memorización, pero siempre necesita averiguar las variables y la función de esas variables que resolverán el problema.
Creo que encontrar la solución recursiva es útil en las etapas iniciales, ya que encuentro que el enfoque de arriba hacia abajo es más intuitivo .
Entonces, si desea seguir el enfoque de arriba hacia abajo, una solución recursiva es la solución al problema de DP.
Si desea tener una solución de abajo hacia arriba, descubrir la función recursiva es tan bueno como encontrar la solución exacta, excepto que primero debe completar los casos base y escribir una solución iterativa.
Por ejemplo, consideremos que desea encontrar el coeficiente binomial [math] ^ nC_r [/ math].
Puede descubrir que [matemáticas] ^ nC_r [/ matemáticas] [matemáticas] = [/ matemáticas] [matemáticas] ^ {n-1} C_ {r-1} [/ matemáticas] [matemáticas] + [/ matemáticas] [ matemática] ^ {n-1} C_ {r} [/ matemática], que es la relación de recurrencia para resolver este problema con la ayuda de la programación dinámica.
No estoy seguro de cómo se puede resolver este problema con la programación dinámica, si no se le ocurre esto u otra recurrencia válida 🙂
- ¿Vale la pena iniciar una compresión de datos sin pérdidas?
- Cómo encontrar la complejidad de tiempo de caso promedio de un algoritmo
- Cuando se utilizan códigos de corrección de errores (ECC), ¿cómo detecta el algoritmo si los bits de ECC están dañados?
- ¿Cuál es la lógica y la intuición detrás del algoritmo de optimización de momento y por qué se considera mejor que el descenso de gradiente?
- ¿Qué algoritmo está detrás de la convolución en MATLAB?
Por lo tanto, encontrar una solución recursiva es básicamente equivalente a encontrar la solución completa.