En esta sección vamos a estudiar la técnica conocida como programación dinámica. Notar que no se trata de un algoritmo en particular sino una forma de pensar soluciones.

Se mencionan los siguientes temas, que podemos llamar “Requisitos” para sacar provecho de esta sección:

• Recursión
• Divide & Conquer

De todas formas recomendamos seguir leyendo y consultar en el foro si algo no se entiende.

Ahora presentamos un primer ejemplo clásico, que inspira la técnica de Programación Dinámica. En este ejemplo utilizaremos la Sucesión de Fibonacci. Esta es una secuencia infinita de números, que se define de forma recursiva. Los primeros dos números son 0 y 1 respectivamente. Luego, cada número es igual a la suma de los dos anteriores.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Queremos escribir un programa que calcule el n-ésimo número en la sucesión de Fibonacci.

Lo primero que podemos pensar es que dado que la formulación de la sucesión es recursiva, ¡Nuestro programa también sera recursivo! Tomamos al 0 como la posición número 0.

long long fibonacci(long long n){
	if (n == 0) {
		return 0;
	} 
	if (n == 1) {
		return 1;
	}
	return fibonacci(n-1) + fibonacci(n-2);
}

Ahora, pensemos cómo ejecuta este algoritmo. ¿Qué pasa si calculo el fibonacci número 6? La función fibonacci(6) llama primero a fibonacci(5) y después a fibonacci(4). A su vez fibonacci(5) primero llamó a fibonacci(4) y fibonacci(3).

¿Qué paso acá? ¡Tenemos cálculos repetidos! El calculo de fibonacci(4) lo acabamos de repetir dos veces. Y otros números en la secuencia se calculan más veces todavía.

Referencia: Programación Dinámica

En la figura de arriba podemos visualizar lo que se conoce como “árbol de llamadas” de la función con parámetro 6. Si ejecutamos esta función con números más grandes, veríamos como empieza a tardar el programa¹⁾. Mediante un análisis más formal podemos decir que la complejidad de esta función es exponencial²⁾.

El próximo paso podría ser pensar un programa no recursivo (iterativo). La idea importante es calcular los números de fibonacci de menor a mayor, manteniendo siempre la lista de los anteriores. De esta forma, cuando quiero calcular un número, ya tengo resueltos sus dos anteriores, por lo cual solo tengo que sumarlos.

long long fibonacci(long long n){
	vector<long long> fib(n+1);
	fib[0] = 0;
	fib[1] = 1;
	for(int i = 2; i <= n; i++) {
		fib[i] = fib[i-1] + fib[i-2];
	}
	return fib[n];
}

Notar que usamos $\Theta(n)$ en complejidad temporal (y también espacial). Esto es mucho mejor que nuestro anterior algoritmo exponencial. Esta forma es la que luego denominaremos bottom-up.

¿Por qué la forma no recursiva fue mucho mejor? ¿Es la recursión algo que debemos evitar? ¡NO! La recursión es una técnica poderosísima, pero, ya lo dijo el Tío Ben, un gran poder conlleva una gran responsabilidad.

El problema que tuvimos al resolver utilizando recursión fue que repetíamos cálculos de algunos números de Fibonacci. Sin embargo, podemos evitar repetir los cálculos modificando levemente la función. En lugar de simplemente calcular, cada vez que llamemos a la función debemos verificar si el valor que deseamos utilizar ya fue calculado. En caso afirmativo, devolvemos la respuesta que ya teníamos. En caso contrario, realizamos el cálculo.

const int MAX_N = 100;
vector<long long> memo_fibo(MAX_N, -1); // -1 denota que no fue calculado
 
long long fibonacci(long long n){
	if (n == 0 or n == 1) {
		// fibo(0) = 0, fibo(1) = 1
		return n;
	}
	if (memo_fibo[n] == -1) {
		// Este fibonacci nunca se calculo
		// Me guardo el resultado
		memo_fibo[n] = fibonacci(n-1) + fibonacci(n-2);
		return memo_fibo[n];
	} else {
		return memo_fibo[n];
	}
}

Lo que esto nos garantiza es que para cada número n, fibonacci(n) se calcula EXACTAMENTE UNA VEZ. Notar que, por ejemplo, fibonacci(4) se usa varias veces. Una en fibonacci(5) y otra en fibonacci(6). Pero aún así, el cálculo del resultado se hace una vez.

Ahora miramos como se compara el arbol de llamadas de este algoritmo con la versión recursiva pura.

Con estas observaciones, podemos calcular la complejidad del algoritmo. Primero veamos que, si ignoramos la recursión, las operaciones que hace para un n fijo, son en total $O(1)$. En concreto, solo contamos una suma. Luego, como para cada n calculamos fibonacci(n) solo una vez, en total el algoritmo es $\Theta(n)$. Además es $\Theta(n)$ memoria por el arreglo que utilizamos para guardar el resultado.

Las ideas mencionadas anteriormente son la esencia la técnica de programación dinámica. Resolvemos un problema y nos guardamos resultados intermedios para no calcularlos varias veces. El algoritmo puede ser recursivo o iterativo, según sea conveniente en el problema.

Si implementamos un algoritmo recursivo, en el contexto de dinámica lo llamamos top-down. En esos casos utilizamos algun tipo de arreglo u otra estructura para memorizar los resultados intermedios. En inglés la técnica se conoce como memoization.

Si implementamos un algoritmo iterativo, en el contexto de dinámica lo llamamos bottom-up.

Ambas formas de escribir los programas son equivalentes (casi equivalentes). Por ejemplo en el Fibonacci, obtuvimos las mismas complejidades temporales y espaciales. Esto se debe a que lo importante del algoritmo era la forma de resolver mediante casos mas chicos, lo que llamamos, formulación recursiva . En este caso eso era, fibo(n) = fibo(n-1) + fibo(n-2). Y esta forma aparece repetida en todas las soluciones.

Muchas veces ocurre que si se nos ocurre una formulación recursiva elegante, la implementación recursiva es casi igual, como en este caso. ¡Simplemente llevamos esa formula a código! Entonces lo único que nos falta es hacer la memorización para tener un top-down,

Otras veces puede pasar que bottom-up sea más simple de escribir, aunque no es lo usual. Lo que si pasa es que, aunque bottom-up y top-down tengan la misma complejidad téorica, en la práctica, bottom-up sea más rápido. Otra cosa que nos podría pasar es que con bottom-up podamos usar menos memoria que con la top-down. Aún asi, en el contexto de OIA no vamos a tener ninguno de esos problemas. En síntesis: ¡¡¡TOP-DOWN LA ROMPE!!!

Tenemos M una matriz de mxn números. Podemos pensar en un camino en la matriz como una serie de pasos entre casillas. Los únicos movimientos permitidos son:

• Hacia arriba: De la casilla (i, j) a la (i+1, j)
• Hacia la derecha: De la casilla (i, j) a la (i, j+1)

Dado un camino, decimos que su largo es la suma de los números por los que pasa. ¿Cuál es el largo del camino más corto entre el origen (0,0) y la casilla superior derecha (m-1, n-1) ?

Como todos los problemas de dinámica, debemos empezar por buscar una forma de resolver recursiva. Lo que vamos a hacer va a ser pensar en f(i, j) como el camino mínimo llegando a una posición cualquiera de la matriz.

f(i, j) := “El camino mínimo desde (0,0) a (i, j)”

Proponemos esta función porque, si sabemos calcular cualquier valor de f(i,j), podemos calcular f(m-1, n-1) y ¡Obtener el resultado que buscábamos!

¿Que casos base tenemos para esta función? En concreto, ¿Qué valores sabemos calcular de antemano?

Sabemos que f(0,0) = M[0][0] porque el único camino desde (0,0) hasta (0,0) es el que solamente incluye la casilla (0, 0) (se queda en el lugar). Asi que este será un caso base.

¿Como podemos calcular el mejor camino hasta cualquier (i, j)? Supongamos que queremos llegar hasta (5,5) Lo único que sabemos es que al llegar a (5,5) vinimos, o de la izquierda o de abajo. ¡Esto ya nos da mucha información! Si sabemos que el mejor camino hasta (5, 5) viene de abajo, es decir, viene de (4, 5). Ahora, si el mejor camino hasta (5, 5) pasaba por (4, 5), ¡Tiene que llegar de la mejor forma posible! Si desde (0, 0) viajamos a (4, 5) de una forma que no es la mejor, y de ahi llegamos a (5, 5), no seria la mejor forma de llegar a (5, 5). ³⁾ Si usamos la mejor forma de llegar a (4, 5), ahi si podemos llegar de la mejor forma a (5,5)

Si entonces, llegamos de la mejor forma a (i, j) por abajo, entonces: $f(i, j) = f(i-1, j) + M[i][j]$

Porque f(i-1, j) es el subcamino hasta (i, j) óptimo que mencionamos antes.

Luego nos queda

$f(i, j) = min\{f(i-1, j) + M[i][j], f(i, j-1) + M[i][j]\}$

camino_matriz_top_down.cpp

#include <vector>
#include <iostream>
using namespace std;
 
typedef vector<vector<int> > matriz;
 
const int MAX_FILAS = 1000;
const int MAX_COLUMNAS = 1000;
 
#define forn(i, n) for(int i = 0; i < int(n); i++)
 
matriz dp(MAX_FILAS, vector<int>(MAX_COLUMNAS, -1)); 
 
int min_camino_matriz(matriz& m, int i, int j) {
	if (i == 0 and j == 0) {
		return m[0][0];
	}
 
	if (dp[i][j] != -1) {
		return dp[i][j];
	}
 
	if (i == 0 and j > 0) {
		dp[0][j] = min_camino_matriz(m, 0, j - 1) + m[0][j];
	}
	if (j == 0 and i > 0) {
		dp[i][0] = min_camino_matriz(m, i - 1, 0) + m[i][0]; 
	}
	if (i > 0 and j > 0) {
		dp[i][j] = min(min_camino_matriz(m, i - 1, j), min_camino_matriz(m, i, j - 1)) + m[i][j];
	}
	return dp[i][j];
} 
 
 
int main(){
	int filas, columnas;
	cin >> filas >> columnas;
	matriz m(filas, vector<int> (columnas, 0));
	forn(i, filas) {
		forn(j, columnas) {
			cin >> m[i][j];
		}
	}
	cout << min_camino_matriz(m, filas-1, columnas-1);
}

Al-Garin

El análisis de complejidad suele ser estándar

Para top-down es menos evidente como hacer el análisis de complejidad. El motivo de la dificultad radica es no poder precisar el orden de ejecución, por la memoization. No sabemos “en qué momento” se hace por primera vez un cálculo, solo sabemos que se hace y solo una vez.

Tenemos dos tipos de llamadas a la funciones memoizadas:

A) La primer llamada a ese subproblema (la primer llamada con esos parámetros)
B) La segunda llamada o posteriores

Cuando tomamos el costo de una llamada de tipo A), no contamos la recursión como parte del costo, tomamos cada llamada recursiva como $O(1)$ ya que las vamos a tomar como costo de otro subproblema, o de B)

Para medir la complejidad total sumamos todos los costos de resolver cada subproblema. De forma simplificada, solo contamos el costo de las llamadas de tipo A) obtieniendo

Costo total = #Subproblemas $\times$ Costo A)

¿Donde esta el costo de las llamadas de tipo B)? Cada llamada B) la hizo algún A) mientras estaba computando Luego, el costo de hacer esa llamada se lo podemos cobrar dentro del costo de resolver A) El costo total será $Subproblemas \times ( Costo(A) + llamadas recursivas \times Costo(B)) $

Asumiendo que todas las llamadas recursivas son de tipo B) para acotar peor caso Por ejemplo, en el problema de camino en la matriz queda:

$O(n^2) \times ( O(1) + O(1) \times O(1)) $

Podemos ver que la cantidad de llamadas recursivas siempre va a estar contenida en la complejidad de A). No podría ser que tengamos que hacer $O(n)$ llamadas pero costo(A) = $O(log n)$ operaciones, ya que las llamadas recursivas son parte del costo(A). Además Costo(B) suele ser O(1), por lo cual podemos simplificar y queda $Subproblemas \times ( Costo(A))$

En general lo que llamamos Costo(A) se denota como Costo por subproblema, y podemos confiar *casi ciegamente* en la fórmula:

Costo total = #Subproblemas $\times$ Costo por subproblema

Clase de la materia Algoritmos y Estructuras de Datos III del Departamento de Computación de la UBA: dp-monedas.pdf

Zapallos