---
tags: dp
---

# DP
La *programación dinámica* o *dynamic programming* es un paradigma de resolución de problemas que se basa en reutilizar respuestas previamente calculadas en alguna función recursiva.

Para resolver un problema con DP, necesitamos conocer algunas propiedades:
- **Problemas que se traslapan:** la programación dinámica, al igual que *divide y vencerás*, combina soluciones a subproblemas. Se basa en que vamos a ir guardando en memoria las soluciones que ya tenemos calculadas para que, en caso de que algún otro subproblema las requiera, no tenga que volver a calcularlas.
- **Subestructura óptima:** la solución óptima de un problema puede obtenerse a través de las soluciones óptimas de sus subproblemas. Por ejemplo, en el problema del camino más corto en grafos.

Por ejemplo: sea $f_0=0$, $f_1=1$ y $f_n=f_{n-1}+f_{n-2}$ para $n \geq 2$. Para programar esta función directamente, tendríamos que:

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

Así como está programada la función recursiva, tiene una complejidad exponencial, pues estamos recalculando muchas veces valores que ya tenemos. Ejemplo para $n=5$:
Vemos que el valor de $f(3)$ se calculó dos veces. Entonces, la forma de solucionar esto va a ser guardar las respuestas de subproblemas que ya tenemos.

vector<int> mem(100, -1); // Inicializa un arreglo de tamaño 100 con todas sus entradas igual a -1

int f(int n){
	// Casos base que no necesitan recursión
	if(n == 0) return 0;
	if(n == 1) return 1;
	if(mem[n] != -1){
		// Ya lo tengo calculado, simplemente lo regreso
		return mem[n];
	}
	// No lo tengo calculado, lo hallamos usando la definición de la función recursiva y lo guardamos para usos futuros
	mem[n] = f(n-1) + f(n-2);
	return mem[n];
}

int main(){
	int n;
	cin >> n;
	// memset(mem, -1, sizeof(mem)); // Inicializar un arreglo al estilo C
	cout << f(n) << "\n";
	return 0;
}

Entonces, de forma general, vemos que una DP tiene las siguientes propiedades:
- **Casos base:** son los valores de nuestra función que se pueden devolver directamente sin llamar de forma recursiva a la función.
- **Estados:** son los argumentos que describen de forma única al subproblema que estamos resolviendo. Es decir, los argumentos con los que llamamos a la función recursiva.
- **Transiciones:** nos describe cómo se relacionan los estados entre sí. Esta la parte más difícil y de pensar de un problema de DP, pues depende totalmente del problema. Es decir, es la definición de la función recursiva.
- **Memoización**: Guardar las respuestas que ya tenemos calculadas para uso futuro.

## Problema: [cut ribbon](https://codeforces.com/problemset/problem/189/A)
Dado un listón de tamaño $n$, queremos cortarlo en listones más pequeños cuyos tamaños solo pueden ser igual a $a$, $b$ o $c$. Queremos maximizar el número de listones que puedo obtener.

Primero veamos la función de recursividad que resuelve el problema. Sea $f(n)$ el número máximo de listones que podemos obtener con las restricciones dadas. Vemos que:
- Si tengo un listón de tamaño $n$, puedo decidir cortarlo de las siguientes formas:
- Hacer un corte de tamaño $a$ ($n \geq a$), quedándome con un listón de tamaño $a$ y otro de tamaño $n-a$.
- Hacer un corte de tamaño $b$ ($n \geq b$), quedándome con un listón de tamaño $b$ y otro de tamaño $n-b$.
- Hacer un corte de tamaño $c$ ($n \geq c$), quedándome con un listón de tamaño $c$ y otro de tamaño $n-c$.
- Intentaremos hacer los tres cortes y ahora hay que seguir cortando el listón con el tamaño que nos quedó, y al final quedarnos con la opción que maximice el número de listones obtenidos.

$$
\begin{align}
f(n) &= \begin{cases}
1 + \max(f(n-a), f(n-b), f(n-c)) & \mbox{si $n \geq a$, $n \geq b$ o $n \geq c$} \\
0 & \mbox{si $n=0$} \\
-\infty & \mbox{si $n < a$, $n < b$ y $n < c$}
\end{cases}
\end{align}
$$
Es decir, mientras pueda seguir cortando el listón de al menos una forma, lo hago e incremento el número de cortes en 1. Si tengo un listón vacío, obtuve cero listones. Y si ya no puedo hacer ningún corte, devuelvo $-\infty$, pues esto va a representar que este subproblema no tiene solución.

#include <bits/stdc++.h>
using namespace std;

const int MX = 4000;
vector<int> mem(MX + 1);
vector<bool> calc(MX + 1);
int a, b, c;
int infinity = 1e9;

int f(int n){
	if(n == 0) return 0;
	if(n < a && n < b && n < c) return -infinity;
	if(calc[n]){
		return mem[n];
	}
	int ans = -infinity;
	if(n-a >= 0) ans = max(ans, f(n-a));
	if(n-b >= 0) ans = max(ans, f(n-b));
	if(n-c >= 0) ans = max(ans, f(n-c));
	mem[n] = 1 + ans;
	calc[n] = true;
	return mem[n];
}

int main(){
	int n;
	cin >> n >> a >> b >> c;
	cout << f(n) << "\n";
	return 0;
}

## Problema: [mochila](https://www.spoj.com/problems/KNAPSACK/)
Tenemos $n$ objetos con cierto valor y cierto peso, digamos que el $i$-ésimo objeto pesa $w_i$ unidades y tiene un valor de $v_i$. Tenemos una mochila con una capacidad de $W$ y queremos empacar algunos objetos sin exceder su capacidad, tal que maximicemos la suma de los valores de los objetos que introduzcamos. Cada objeto solo lo podemos usar una vez y no los podemos "partir", es decir, lo usamos todo o no lo usamos.

**Solución:** por cada objeto puedo decidir tomarlo o no tomarlo. Si lo tomo, tengo que cuidar que no exceda el peso de la mochila que llevo hasta ahora y sumo su valor al valor acumulado; y si no lo tomo, no hay cambio.

Esto nos sugiere que nuestra función podría ser: sea $f(i, cap)$ la función que nos devuelve el valor máximo que podemos alcanzar usando los primeros $i$ objetos, donde la capacidad de nuestra mochila al momento es de $cap$. La llamaríamos como $f(n, W)$.

Las transiciones quedan de la siguiente manera:
$$
\begin{align}
f(i, cap) &= \begin{cases}
0 &\mbox{si $i = 0$} \\
\max(\underbrace{v_i + f(i-1, cap - w_i)}_\text{siempre que $cap \geq w_i$}, f(i-1, cap)) &\mbox{si $i \geq 1$}
\end{cases}
\end{align}
$$
Cuando decido sí tomar el objeto, tengo que cuidar que la mochila tenga la capacidad suficiente al momento, es decir, $cap \geq w_i$.

#include <bits/stdc++.h>
using namespace std;

int value[2010], weight[2010];
int mem[2010][2010];

int f(int i, int cap){
	if(i == 0){
		return 0;
	}
	if(mem[i][cap] != -1) return mem[i][cap];
	int tomar = 0;
	if(cap >= weight[i]){
		tomar = value[i] + f(i-1, cap - weight[i]);
	}
	int no_tomar = f(i-1, cap);
	mem[i][cap] = max(tomar, no_tomar);
	return mem[i][cap];
}

int main(){
	int s, n;
	cin >> s >> n;
	memset(mem, -1, sizeof(mem));
	for(int i = 1; i <= n; ++i){
		cin >> weight[i] >> value[i];
	}
	cout << f(n, s) << "\n";
	return 0;
}

## Calcular la complejidad
Para calcular la complejidad en tiempo de un problema de DP, hay que multiplicar la cantidad de estados posibles por la complejidad de calcular cada estado. Esto nos da una muy buena aproximación. Y la complejidad en memoria es solamente el número de estados.

Por ejemplo, en el problema **Cut ribbon** tenemos $n$ estados y cada uno me cuesta $O(1)$, por lo tanto la complejidad total temporal es $O(n)$.

En el problema anterior, tenemos $nW$ estados y cada uno me cuesta $O(1)$, por lo tanto la complejidad total temporal es $O(nW)$.

## Problema: [concierto](https://omegaup.com/arena/problem/Concierto-de-Dr-Lira)
Dado un valor inicial $y_0$ y un arreglo de cambios $A=[x_1, x_2, \ldots, x_n]$ ($1 \leq x_i \leq 1000$, $1 \leq n \leq 50$), definimos a $y_i=y_{i-1} \pm x_i$ para $1 \leq i \leq n$, es decir, en cada paso decidimos sumarle o restarle $x_i$ a $y_{i-1}$ para obtener el nuevo valor de $y_i$. Tenemos que cuidar que $0 \leq y_i \leq M$. El objetivo es maximizar $y_n$.

Sea $f(i, v)$ el máximo posible valor de $y_n$ comenzando con la $i$-ésima canción y con un valor inicial de volumen $v$. La mandamos llamar como $f(1, y_0)$. En cada paso, puedo sumar o restar $y_i$ cuidando no sobrepasar los líimtes establecidos. Entonces:
$$
\begin{align}
f(i, v) &= \begin{cases}
\max(\underbrace{f(i+1, v-y_i)}_{\text{decido restar si $v-y_i \geq 0$}}, \underbrace{f(i+1, v+y_i)}_{\text{decido sumar si $v+y_i \leq M$}}) &\mbox{si $1 \leq i \leq n$} \\
v &\mbox{si $i=n+1$}
\end{cases}
\end{align}
$$

Gráfica del caso de ejemplo:

La complejidad de hallar $f(1, y_0)$ es $O(nM)$, tanto en tiempo como en memoria.
Código:

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;

int main(){
	int n;
	cin >> n;
	vector<int> A(n);
	for(int & ai : A){
		cin >> ai;
	}
	int b, m;
	cin >> b >> m;

	vector<vector<int>> mem(n+1, vector<int>(m+1));
	vector<vector<bool>> calc(n+1, vector<bool>(m+1));

	function<int(int, int)> f = [&](int i, int v){
		// f() es una función lambda adentro del main
		// que se declara de la siguiente forma:
		// function<U(T1, T2, ..., Tn)> f = (T1 v1, T2 v2, ..., Tn vn)
		// donde U es el tipo de dato de retorno y
		// todas las T1, T2, ..., Tn son los tipos de dato de los argumentos
		// y todas las v1 v2, ..., vn son los nombres de los argumentos
		if(i == n+1){
			return v;
		}else{
			if(calc[i][v]){
				return mem[i][v];
			}
			int decido_restar = -inf;
			if(v - A[i-1] >= 0){
				decido_restar = f(i+1, v - A[i-1]);
			}
			int decido_sumar = -inf;
			if(v + A[i-1] <= m){
				decido_sumar = f(i+1, v + A[i-1]);
			}
			calc[i][v] = true;
			mem[i][v] = max(decido_restar, decido_sumar);
			return mem[i][v];
		}
	};

	int respuesta = f(1, b);
	if(respuesta < 0){
		cout << "-1\n";
	}else{
		cout << respuesta << "\n";
	}

	return 0;
}

## Problema: [coin change](https://leetcode.com/problems/coin-change/)
Dadas unas denominaciones de monedas $A=[a_1, a_2, \ldots, a_m]$ y un precio $n$, queremos formar $n$ usando algunas de las monedas dadas las veces que queramos, y por cada tipo de moneda tenemos una cantidad ilimitada. El problema es minimizar el número de monedas para formar el precio $n$.

Por ejemplo: si $n=11$ y $A=[1,2,5]$, entonces algunas formas de formar el precio son:
- $n=\underbrace{1+1+\ldots+1}_{\text{11 monedas}}$, aquí usé 11 monedas.
- $n=1+2+2+2+2+2$, aquí usé 6 monedas.
- $n=2+2+2+5$, aquí usé 4 monedas.
- $n=1+5+5$, aquí use 3 monedas.

Sea $f(n)$ el número mínimo de monedas que requiero para formar el precio $n$. Una estrategia es ir de reversa: a partir de $n$ llegar a $0$ usando las monedas disponibles. En cada estado tengo que tomar una decisión: ver, a partir de las monedas que tengo disponibles, cómo puedo llegar a mi precio $n$: esto me incrementará en 1 el número de monedas usadas, y me quedo con la mínima respuesta de cada decisión. Entonces tenemos que:
$$
\begin{align}
f(n) &= \begin{cases}
1 + \min_{a_i \in A}(\underbrace{f(n - a_i)}_\text{siempre que $n -a_i \geq 0$}) &\mbox{si $n \geq 1$} \\
0 &\mbox{si $n = 0$}
\end{cases}
\end{align}
$$

Ejemplo paso a paso para $n=11$:
- $f(0) = 0$
- $f(1) = 1 + \min(f(1-1)) = 1 + \min(f(0)) = 1 + \min(0) = 1 + 0 = 1$
- $f(2) = 1 + \min(f(2-1), f(2-2)) = 1 + \min(f(1), f(0)) = 1 + \min(1, 0) = 1 + 0 = 1$
- $f(3) = 1 + \min(f(3-1), f(3-2)) = 1 + \min(f(2), f(1)) = 1 + \min(1, 1) = 1 + 1 = 2$
- $f(4) = 1 + \min(f(3), f(2)) = 1 + 1 = 2$
- $f(5) = 1 + \min(f(4), f(3), f(0)) = 1 + 0 = 1$
- $f(6) = 1 + \min(f(5), f(4), f(1)) = 1 + 1 = 2$
- $f(7) = 1 + \min(f(6), f(5), f(2)) = 1 + 1 = 2$
- $f(8) = 1 + \min(f(7), f(6), f(3)) = 1 + 2 = 3$
- $f(9) = 1 + \min(f(8), f(7), f(4)) = 1 + 2 = 3$
- $f(10) = 1 + \min(f(9), f(8), f(5)) = 1 + 1 = 2$
- $f(11) = 1 + \min(f(10), f(9), f(6)) = 1 + 2 = 3$

Código:

class Solution {
private:
    int inf = 1e9;
    vector<int> mem;
public:
    int f(vector<int>& coins, int amount) {
        if(amount == 0){
            return 0;
        }
        int & ans = mem[amount];
        if(ans != -1) return ans;
        ans = inf;
        for(int coin : coins){
            if(amount >= coin){
                ans = min(ans, f(coins, amount - coin));
            }
        }
        ans += 1;
        return ans;
    }
    int coinChange(vector<int>& coins, int amount){
        mem.resize(amount+1, -1);
        int ans = f(coins, amount);
        if(ans >= inf){
            return -1;
        }else{
            return ans;
        }
    }
};

## Problema: [path sum (1)](https://projecteuler.net/problem=81), [path sum (2)](https://leetcode.com/problems/minimum-path-sum/)
Tenemos una matriz $A$ de $m \times n$ con números enteros positivos en sus celdas. Queremos hallar un camino que comience en la esquina superior izquierda y que termine en la esquina inferior derecha, tal que solo podemos movernos a la derecha o hacia abajo. Queremos encontrar el camino que minimice la suma de las casillas usadas.

Sea $f(m, n)$ el mínimo camino que puedo obtener en la submatriz que comienza en la esquina superior izquierda y termina en la casilla $(m, n)$. De forma similar, trataremos de llegar desde $(m, n)$ hasta $(1, 1)$ moviéndonos de reversa, es decir, con movimientos hacia arriba o hacia la izquierda. Es decir, tenemos dos decisiones por cada celda, y me quedo con la que me de la mínima suma. Entonces:
$$
\begin{align}
f(m, n) &= \begin{cases}
A[1][1] &\mbox{si $m=n=1$} \\
A[m][n] + \min(\underbrace{f(m-1, n)}_\text{arriba, si $m > 1$}, \underbrace{f(m, n-1)}_\text{izquierda, si $n > 1$}) &\mbox{en otro caso}
\end{cases}
\end{align}
$$

## Problema: Longest Common Subsequence (LCS)
Tarea