Solución:
Considere calcular la secuencia de fibonacci:
Recursividad pura:
int fib(int x)
{
if (x < 2)
return 1;
return fib(x-1) + fib(x-2);
}
da como resultado un número exponencial de llamadas.
Recursividad con memorización / DP:
int fib(int x)
{
static vector<int> cache(N, -1);
int& result = cache[x];
if (result == -1)
{
if (x < 2)
result = 1;
else
result = fib(x-1) + fib(x-2);
}
return result;
}
Ahora tenemos un número lineal de llamadas la primera vez y constante a partir de entonces.
El método anterior se llama “perezoso”. Calculamos los términos anteriores la primera vez que se solicitan.
Lo siguiente también se consideraría DP, pero sin recursividad:
int fibresult[N];
void setup_fib()
{
fibresult[0] = 1;
fibresult[1] = 1;
for (int i = 2; i < N; i++)
fibresult[i] = fibresult[i-1] + fibresult[i-2];
}
int fib(int x) { return fibresult[x]; }
Esta forma puede describirse como “ansiosa”, “almacenamiento en caché” o “iterativa”. Es más rápido en general, pero tenemos que averiguar manualmente el orden en que se deben calcular los subproblemas. Esto es fácil para fibonacci, pero para problemas de DP más complejos se vuelve más difícil, por lo que recurrimos al método recursivo perezoso si es rápido. suficiente.
Además, lo siguiente no es ni recursividad ni DP:
int fib(int x)
{
int a = 1;
int b = 1;
for (int i = 2; i < x; i++)
{
a = a + b;
swap(a,b);
}
return b;
}
Utiliza espacio constante y tiempo lineal.
También mencionaré en aras de la integridad que hay una forma cerrada para fibonacci que usa recursividad inferior ni DP que nos permite calcular en tiempo constante el término de fibonacci usando una fórmula matemática basada en la proporción áurea:
http://www.dreamincode.net/forums/topic/115550-fibonacci-closed-form/
Bien, recursividad + memorización es precisamente un “sabor” específico de programación dinámica: programación dinámica según De arriba hacia abajo Acercarse.
Más precisamente, no es necesario utilizar recursividad específicamente. Cualquier solución de divide y vencerás combinada con la memorización es una programación dinámica de arriba hacia abajo. (La recursividad es el estilo LIFO de divide y vencerás, mientras que también puedes usar FIFO divide y vencerás o cualquier otro tipo de divide y vencerás).
Entonces es más correcto decir que
divide & conquer + memoization == top-down dynamic programming
Además, desde un punto de vista muy formal, si implementa una solución de divide y vencerás para un problema que no genera soluciones parciales repetitivas (lo que significa que no hay beneficio en la memorización), entonces puedes afirmar que esta solución de divide y vencerás es una ejemplo degenerado de “programación dinámica”.
Sin embargo, programación dinámica es un concepto más general. La programación dinámica puede utilizar un enfoque de abajo hacia arriba, que es diferente de dividir y conquistar + memorización.
Estoy seguro de que puede encontrar una definición detallada en Internet. Aquí está mi intento de simplificar las cosas.
La recursividad se vuelve a llamar a sí misma.
La programación dinámica es una forma de resolver problemas que exhiben una estructura específica (subestructura óptima) donde un problema se puede dividir en subproblemas que son similares al problema original. Claramente, se puede invocar la recursividad para resolver un DP. Pero no es necesario. Se puede resolver un DP sin recursividad.
La memorización es una forma de optimizar los algoritmos de DP que se basan en la recursividad. El punto es no volver a resolver el subproblema que ya ha sido resuelto. Puede verlo como un caché de soluciones a subproblemas.