Estaba leyendo en Programación dinámica y soy bastante nuevo en esto. Quería saber si la Programación Dinámica se puede aplicar de manera "iterativa" y "recursiva" o si es una buena práctica aplicarla solo de una de las maneras. Cualquier buen ejemplo/enlace sería útil.Programación dinámica recursiva o iterativa
Sí, DP se puede aplicar a ambos.
Comience aquí: http://en.wikipedia.org/wiki/Dynamic_programming
Entonces usted tiene Dynamic Programming: From novice to advanced y A Tutorial on Dynamic Programming
Para el primer tutorial, encontrará enlaces a TopCoder.com problemas para la práctica (cada uno de estos problemas tienen también un Editorial explicar la idea detrás de la solución.
la programación dinámica se puede ver (en muchos casos) como una solución recursiva en marcha en sentido inverso.
N ormally, en una recursión, se calcularía x(n+1) = f(x(n)) con alguna condición de detención para n=0 (o algún otro valor).
En muchos casos, la función f es alguna función mínima/máxima, pero no tiene que ser así. Además, la función no tiene que tomar una sola variable.
La programación dinámica podría resolver este problema mediante el cálculo de f(0), entonces f(1), entonces f(2) etc.
Con más de una variable en este caso solía haber algún orden natural para calcular la función.
Un ejemplo que la programación dinámica puede resolver: Se le otorgan 3 palos de golf. Cada palo de golf puede enviar una pelota de golf x unidades de distancia hacia delante (por ejemplo, 24, 37 y 54 unidades). La pregunta es: ¿puedes golpear un agujero que está exactamente a 200 unidades de distancia? Y si puede, ¿cuál es el número mínimo de disparos que necesita?
La solución recursiva sería algo así como:
shots(200) = min(shots(200-24),shots(200-37),shots(200-54))
Esto permitiría una aplicación trivial, donde la función shot(n) devuelve 0 si n es 0, un número enorme si n es menor que 0, y la expresión arriba de lo contrario.
Sin embargo, para valores grandes de n, se presionarán los mismos valores una y otra vez, desde diferentes ramas de la expresión anterior. En ese caso, es mejor comenzar desde 0 y calcular shots(0), shots(1), shots(2), etc. Esta sería la solución de "programación dinámica" para este problema: usar tiempo lineal y espacio constante en lugar de tiempo exponencial (atravesar un árbol de 3 vías)) y espacio lineal en el mejor de los casos (para la pila de llamadas).
El enfoque de arriba hacia abajo todavía se considera programación dinámica si se agrega memoria. El DP ascendente y el DP descendente son ambos DP. – harold
@ harold, tienes razón, probablemente debería haber agregado algo sobre la memorización (es un poco más difícil de usar si quieres mantener el requisito de memoria razonable, necesitas saber cuándo puedes "olvidar" los valores mientras que con los de abajo hacia arriba está bastante claro). –
Si bien la solución recursiva con almacenamiento en caché solo contempla un pequeño subconjunto de los números 0..200, la solución iterativa tendría que mirarlos a todos (al menos no es fácil evitarlo). Entonces, parece que la solución recursiva funcionaría más rápido en este caso. – AlwaysLearning