Estaba leyendo notes on Dynamic programming, y me encontré con el siguiente comentario.Programación dinámica y Dividir y conquistar
Si los subproblemas no son independientes, es decir subproblemas compartir subsubproblems, a continuación, un algoritmo divideand vencerás resuelve en repetidas ocasiones los comunes subsubproblems. Por lo tanto, hace más trabajo de lo necesario
¿Qué significa esto? ¿Me puede dar ejemplos para aclarar el punto anterior?
El autor se refiere al hecho de que muchos algoritmos de división y conquista tienen subproblemas que se superponen entre sí. Consideremos, por ejemplo, esta muy simple aplicación de Fibonacci:
int Fibonacci(int n) {
if (n <= 1) return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Si se desplaza por las llamadas realizadas para calcular Fibonacci (4), obtenemos
En otras palabras, se realizan 9 llamadas a funciones totales, pero solo hay cinco llamadas únicas aquí (Fibonacci de 0 a 4, inclusive). Este algoritmo podría ser mucho más eficiente si las llamadas recursivas se compartieran a través de los subproblemas en lugar de volver a calcular desde cero cada vez. Esta es una de las ideas clave detrás de la programación dinámica.
Para calcular F n (el número Fibonacci n-ésimo), el código de seguridad hará que un total de 2F n + 1 - 1 llamadas recursivas. Dado que los números de Fibonacci crecen exponencialmente rápidamente, esto requiere mucho trabajo exponencial. Sin embargo, es posible utilizar el hecho de que muchas llamadas recursivas son idénticas para simplificar esto dramáticamente. En lugar de comenzar en Fibonacci (4) y trabajar, comencemos en Fibonacci (0) y avancemos. En concreto, vamos a construir una tabla (vamos a llamarlo FTABLE) de longitud 5 y llenará en la forma siguiente:
Ahora, supongamos que queremos calcular FTable [2]. Esto requiere que sepamos FTable [0] y FTable [1], pero ya lo sabemos porque están en la tabla.Así, podemos establecer
Usando una lógica similar, podemos calcular FTABLE [3] a partir de FTABLE [2] y FTABLE [1]:
y FTABLE [4] de FTABLE [2] y FTABLE [3]:
Observe cómo evitamos hacer un montón de superposición de llamadas recursivas con sólo la construcción de ellos en el orden inverso! Esto ahora calcula los números de Fibonacci en el tiempo O (n), que es exponencialmente más rápido que antes. Usando algunas matemáticas más avanzadas podemos hacerlo incluso mejor que esto, pero esto ilustra por qué la programación dinámica puede tomar problemas imposibles y hacerlos de repente factibles.
Espero que esto ayude!