Tabulación vs Memoización – Part 1

Requisito previo: programación dinámica , ¿cómo resolver problemas de programación dinámica?  
Hay dos formas diferentes de almacenar los valores para que los valores de un subproblema se puedan reutilizar. Aquí, discutiremos dos patrones para resolver problemas de programación dinámica (DP): 
 

1. Tabulación: de abajo hacia arriba
2. Memoización: de arriba hacia abajo

Antes de llegar a las definiciones de los dos términos anteriores, considere las siguientes declaraciones: 
 

• Versión 1 : estudiaré la teoría de DP de GeeksforGeeks, luego practicaré algunos problemas en DP clásico y, por lo tanto, dominaré DP.
• Versión 2 : para dominar DP, tendría que practicar problemas dinámicos y problemas de práctica: en primer lugar, tendría que estudiar algunas teorías de DP de GeeksforGeeks

Ambas versiones dicen lo mismo, la diferencia radica simplemente en la forma de transmitir el mensaje y eso es exactamente lo que hacen Bottom-Up y Top-Down DP. La versión 1 se puede relacionar con Bottom-Up DP y la versión 2 se puede relacionar con Top-Down DP. 
 

Método de tabulación: programación dinámica de abajo hacia arriba 

Como su propio nombre sugiere, comience desde abajo y acumule respuestas hasta arriba. Hablemos en términos de transición de estado. 

Describamos un estado para nuestro problema de DP como dp[x] con dp[0] como estado base y dp[n] como nuestro estado de destino. Entonces, necesitamos encontrar el valor del estado de destino, es decir, dp[n]. 
Si comenzamos nuestra transición desde nuestro estado base, es decir, dp[0] y seguimos nuestra relación de transición de estado para llegar a nuestro estado de destino dp[n], lo llamamos el enfoque de abajo hacia arriba, ya que está bastante claro que comenzamos nuestra transición desde el estado base inferior y alcanzó el estado deseado superior. 

Ahora bien, ¿por qué lo llamamos método de tabulación? 

Para saber esto, primero escribamos un código para calcular el factorial de un número utilizando un enfoque ascendente. Una vez más, como nuestro procedimiento general para resolver un DP, primero definimos un estado. En este caso, definimos un estado como dp[x], donde dp[x] es encontrar el factorial de x. 

Ahora, es bastante obvio que dp[x+1] = dp[x] * (x+1) 
 

// Tabulated version to find factorial x.
int dp[MAXN];

// base case
int dp[0] = 1;
for (int i = 1; i< =n; i++)
{
    dp[i] = dp[i-1] * i;
}

El código anterior sigue claramente el enfoque ascendente ya que comienza su transición desde el caso base más inferior dp[0] y alcanza su estado de destino dp[n]. Aquí, podemos notar que la tabla DP se completa secuencialmente y estamos accediendo directamente a los estados calculados desde la tabla misma y, por lo tanto, lo llamamos el método de tabulación. 

Método de memorización: programación dinámica de arriba hacia abajo 

Una vez más, describámoslo en términos de transición de estado. Si necesitamos encontrar el valor para algún estado, digamos dp[n] y en lugar de comenzar desde el estado base, es decir, dp[0], preguntamos nuestra respuesta de los estados que pueden alcanzar el estado de destino dp[n] siguiendo la transición de estado relación, entonces es la moda de arriba hacia abajo de DP. 

Aquí, comenzamos nuestro viaje desde el estado de destino más alto y calculamos su respuesta tomando en cuenta los valores de los estados que pueden alcanzar el estado de destino, hasta que alcancemos el estado base más bajo. 

Una vez más, escribamos el código para el problema factorial de arriba hacia abajo. 
 

// Memoized version to find factorial x.
// To speed up we store the values
// of calculated states

// initialized to -1
int dp[MAXN]

// return fact x!
int solve(int x)
{
    if (x==0)
        return 1;
    if (dp[x]!=-1)
        return dp[x];
    return (dp[x] = x * solve(x-1));
}

Como podemos ver, estamos almacenando el caché más reciente hasta un límite, de modo que si la próxima vez recibimos una llamada desde el mismo estado, simplemente la devolvemos desde la memoria. Entonces, es por eso que lo llamamos memorización ya que estamos almacenando los valores de estado más recientes. 

En este caso, el diseño de la memoria es lineal, por eso puede parecer que la memoria se está llenando de manera secuencial como el método de tabulación, pero puede considerar cualquier otro DP de arriba hacia abajo que tenga un diseño de memoria 2D como Min Cost Path , aquí el la memoria no se llena de manera secuencial. 
 

Este artículo es una contribución de Nitish Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.