Introducción a la Programación Dinámica

La esencia de la programación dinámica es evitar el cálculo repetido. A menudo, los problemas de programación dinámica se resuelven de forma natural por recursión. En esos casos, lo más fácil es escribir la solución recursiva y después guardar los estados repetidos en una tabla de lookup. Este proceso se conoce como programación dinámica top-down con memoización. Se lee “memoización” (como si escribiéramos en un memo pad), no memorización.

Uno de los ejemplos clásicos más básicos de este proceso es la sucesión de Fibonacci. Su formulación recursiva es $f(n) = f(n-1) + f(n-2)$ donde $n \ge 2$ y $f(0)=0$ y $f(1)=1$ . En C++, se expresaría así:


int f(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return f(n - 1) + f(n - 2);
}

El tiempo de ejecución de esta función recursiva es exponencial: aproximadamente $O(2^n)$ , ya que una llamada a la función ( $f(n)$ ) produce 2 llamadas de tamaño similar ( $f(n-1)$ y $f(n-2)$ ).

Acelerar Fibonacci con Programación Dinámica (memoización)

Nuestra función recursiva actualmente resuelve Fibonacci en tiempo exponencial. Eso significa que solo podemos manejar valores de entrada chicos antes de que el problema se vuelva demasiado difícil. Por ejemplo, $f(29)$ produce más de 1 millón de llamadas a la función.

Para aumentar la velocidad, reconocemos que la cantidad de subproblemas es solo $O(n)$ . Es decir, para calcular $f(n)$ solo necesitamos conocer $f(n-1),f(n-2), \dots ,f(0)$ . Por lo tanto, en lugar de recalcular estos subproblemas, los resolvemos una vez y guardamos el resultado en una tabla de lookup. Las llamadas posteriores usarán esa tabla y devolverán un resultado de inmediato, ¡eliminando así el trabajo exponencial!

Cada llamada recursiva consulta una tabla de lookup para ver si el valor ya se calculó. Esto se hace en $O(1)$ . Si ya lo calculamos, devolvemos el resultado; si no, calculamos la función de forma normal. El tiempo total es $O(n)$ . ¡Es una mejora enorme respecto del algoritmo exponencial anterior!


const int MAXN = 100;
bool found[MAXN];
int memo[MAXN];
 
int f(int n) {
    if (found[n]) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;
 
    found[n] = true;
    return memo[n] = f(n - 1) + f(n - 2);
}

Con nuestra nueva función recursiva memoizada, $f(29)$ , que antes producía más de 1 millón de llamadas, ahora produce solo 57 llamadas, ¡casi 20.000 veces menos! Irónicamente, ahora nos limita el tipo de dato. $f(46)$ es el último número de Fibonacci que entra en un entero con signo de 32 bits.

Típicamente intentamos guardar estados en arreglos, si es posible, porque el tiempo de lookup es $O(1)$ con overhead mínimo. Sin embargo, de forma más genérica, podemos guardar estados como queramos. Otros ejemplos incluyen árboles binarios de búsqueda (map en C++) o tablas hash (unordered_map en C++).

Un ejemplo de esto podría ser:


unordered_map<int, int> memo;
int f(int n) {
    if (memo.count(n)) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;
 
    return memo[n] = f(n - 1) + f(n - 2);
}

O análogamente:


map<int, int> memo;
int f(int n) {
    if (memo.count(n)) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;
 
    return memo[n] = f(n - 1) + f(n - 2);
}

Ambos serán casi siempre más lentos que la versión basada en arreglo para una función recursiva memoizada genérica. Estas formas alternativas de guardar estado son útiles principalmente cuando hay que guardar vectores o strings como parte del espacio de estados.

La forma informal de analizar el tiempo de ejecución de una función recursiva memoizada es:

$\text{work per subproblem} * \text{number of subproblems}$

Usar un árbol binario de búsqueda (map en C++) para guardar estados da técnicamente $O(n \log n)$ , porque cada lookup e inserción toma $O(\log n)$ de trabajo y con $O(n)$ subproblemas únicos tenemos $O(n \log n)$ de tiempo.

Este enfoque se llama top-down, porque podemos llamar a la función con un valor de consulta y el cálculo empieza desde arriba (el valor consultado) hacia abajo (los casos base de la recursión), y toma atajos vía memoización en el camino.

Programación Dinámica bottom-up

Hasta ahora solo viste programación dinámica top-down con memoización. Sin embargo, también podemos resolver problemas con programación dinámica bottom-up. Bottom-up es exactamente lo opuesto de top-down: empezás abajo (casos base de la recursión) y lo extendés a cada vez más valores.

Para crear un enfoque bottom-up para los números de Fibonacci, inicializamos los casos base en un arreglo. Después, simplemente usamos la definición recursiva sobre el arreglo:


const int MAXN = 100;
int fib[MAXN];
 
int f(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) fib[i] = fib[i - 1] + fib[i - 2];
 
    return fib[n];
}

Por supuesto, tal como está escrito, esto es un poco tonto por dos razones: Primero, hacemos trabajo repetido si llamamos a la función más de una vez. Segundo, solo necesitamos usar los dos valores anteriores para calcular el elemento actual. Por lo tanto, podemos reducir la memoria de $O(n)$ a $O(1)$ .

Un ejemplo de una solución de programación dinámica bottom-up para Fibonacci que usa $O(1)$ de memoria podría ser:


const int MAX_SAVE = 3;
int fib[MAX_SAVE];
 
int f(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i % MAX_SAVE] = fib[(i - 1) % MAX_SAVE] + fib[(i - 2) % MAX_SAVE];
 
    return fib[n % MAX_SAVE];
}

Nótese que cambiamos la constante de MAXN a MAX_SAVE. Esto es porque la cantidad total de elementos a los que necesitamos acceder es solo 3. Ya no escala con el tamaño de la entrada y es, por definición, $O(1)$ de memoria. Además, usamos un truco común (el operador módulo) para mantener solo los valores que necesitamos.

Eso es todo. Esos son los fundamentos de la programación dinámica: no repitas el trabajo que ya hiciste.

Uno de los trucos para mejorar en programación dinámica es estudiar algunos de los ejemplos clásicos.

Problemas clásicos de Programación Dinámica

Nombre	Descripción/Ejemplo
Mochila 0-1	Dados $N$ ítems con pesos $w_i$ y valores $v_i$ y peso máximo $W$ , ¿cuál es el máximo $\sum_{i=1}^{k} v_i$ para cada subconjunto de ítems de tamaño $k$ ( $1 \le k \le N$ ) asegurando $\sum_{i=1}^{k} w_i \le W$ ?
Subset Sum	Dados $N$ enteros y $T$ , determinar si existe un subconjunto del conjunto dado cuyos elementos sumen $T$ .
Subsecuencia creciente más larga (LIS)	Se da un arreglo con $N$ enteros. La tarea es determinar la LIS en el arreglo, es decir, una subsecuencia donde cada elemento es mayor que el anterior.
Contar caminos en un arreglo 2D	Dados $N$ y $M$ , contar todos los caminos distintos posibles de $(1,1)$ a $(N, M)$ , donde cada paso es de $(i,j)$ a $(i+1,j)$ o a $(i,j+1)$ .
Subsecuencia común más larga	Se dan strings $s$ y $t$ . Encontrar la longitud del string más largo que es subsecuencia de $s$ y de $t$ .
Camino más largo en un grafo dirigido acíclico (DAG)	Encontrar el camino más largo en un grafo dirigido acíclico (DAG).
Subsecuencia palindrómica más larga	Encontrar la subsecuencia palindrómica más larga (LPS) de un string dado.
Corte de varilla	Dada una varilla de longitud $n$ unidades y un arreglo de enteros cuts donde cuts[i] denota una posición en la que hay que cortar. El costo de un corte es la longitud de la varilla a cortar. ¿Cuál es el costo total mínimo de los cortes?
Distancia de edición	La distancia de edición entre dos strings es el número mínimo de operaciones necesarias para transformar uno en el otro. Las operaciones son [“Add”, “Remove”, “Replace”]

Introducción a la Programación Dinámica

Acelerar Fibonacci con Programación Dinámica (memoización)

Programación Dinámica bottom-up

Problemas clásicos de Programación Dinámica

Temas relacionados

Problemas de práctica

Contests de DP