Programación Dinámica: Formulaciones Recursivas

Un compendio de funciones recursivas para algunos problemas de DP que encontré resolviendo problemas de algoritmos. Para cada problema, planteamos el enunciado y damos la recurrencia que lleva a una solución por programación dinámica.

0-1 Knapsack

Problema. Dados $n$ objetos, cada uno con peso $w_i$ y valor $v_i$, y una mochila de capacidad $W$, maximizar el valor total sin exceder $W$.

$$\maximize \sum_{i=1}^n v_i x_i \quad \st \quad \sum_{i=1}^n w_i x_i \leq W, \quad x_i \in \{0,1\}.$$

Recurrencia. Definimos $f(i, w)$ como el valor máximo alcanzable con peso $\leq w$ usando los primeros $i$ objetos.

$$f(i, w) = \begin{cases} 0 & \text{si } i = 0, \\ f(i-1, w) & \text{si } w_i > w, \\ \max\{f(i-1, w),\ f(i-1, w - w_i) + v_i\} & \text{en otro caso.} \end{cases}$$

Respuesta: $f(n, W)$. Complejidad: $O(nW)$.

Variantes: bounded knapsack ($0 \leq x_i \leq c$), unbounded knapsack ($x_i \geq 0$).

Unbounded Knapsack

Problema. Igual que 0-1 Knapsack, pero cada objeto se puede usar ilimitadamente: $x_i \geq 0$.

Recurrencia. Definimos $f(w)$ como el valor máximo alcanzable con capacidad $w$.

$$f(w) = \max_{i \,:\, w_i \leq w} \{ f(w - w_i) + v_i \}$$

con $f(0) = 0$. Respuesta: $f(W)$. Complejidad: $O(nW)$.

Nota: iterar $w$ hacia adelante (a diferencia de 0-1 donde se itera hacia atrás).

Bounded Knapsack

Problema. Cada objeto $i$ tiene como máximo $c_i$ copias: $0 \leq x_i \leq c_i$.

Recurrencia. Usar binary lifting: dividir $c_i$ copias en grupos de $1, 2, 4, \ldots, c_i - 2^k + 1$, creando $O(\log c_i)$ objetos virtuales. Luego resolver como 0-1 Knapsack.

Complejidad: $O(W \sum_i \log c_i)$.

Coin Change

Problema (mínimas monedas). Dadas monedas de denominaciones $c_1, \ldots, c_n$ (suministro ilimitado), encontrar el mínimo número de monedas para formar el monto $W$.

Problema (contar formas). Contar el número de formas de formar el monto $W$.

Recurrencia (mínimas monedas). Definimos $f(w)$ como el mínimo de monedas para el monto $w$.

$$f(w) = \min_{c_i \leq w} \{1 + f(w - c_i)\}$$

con $f(0) = 0$. Respuesta: $f(W)$.

Recurrencia (contar formas). Definimos $g(i, w)$ como el número de formas usando los primeros $i$ tipos de moneda.

$$g(i, w) = g(i-1, w) + g(i, w - c_i)$$

con $g(i, 0) = 1$ y $g(0, w) = 0$ para $w > 0$. Respuesta: $g(n, W)$. Complejidad: $O(nW)$.

Subset Sum

Problema. Dados enteros $a_1, \ldots, a_n$ y un objetivo $T$, decidir si existe un subconjunto $S \subseteq \{1, \ldots, n\}$ tal que $\sum_{i \in S} a_i = T$.

Recurrencia. Definimos $f(i, t)$ como verdadero si el objetivo $t$ es alcanzable con los primeros $i$ objetos.

$$f(i, t) = \begin{cases} \trueval & \text{si } t = 0, \\ \falseval & \text{si } i = 0 \text{ y } t > 0, \\ f(i-1, t) \OR f(i-1, t - a_i) & \text{en otro caso.} \end{cases}$$

Respuesta: $f(n, T)$. Complejidad: $O(nT)$.

3-Partition

Problema. Dados enteros $a_1, \ldots, a_n$, determinar si $\{1, \ldots, n\}$ se puede particionar en tres subconjuntos disjuntos $I, J, K$ tales que

$$\sum_{i \in I} a_i = \sum_{j \in J} a_j = \sum_{k \in K} a_k = \frac{1}{3}\sum_{i=1}^n a_i.$$

Recurrencia. Sea $S = \sum a_i$. Si $3 \nmid S$, la respuesta es $\falseval$.

Definimos $f(i, p, q)$ como $\trueval$ si podemos encontrar $I, J \subseteq \{1, \ldots, i\}$ disjuntos con $\sum_{I} a = p$ y $\sum_{J} a = q$.

$$f(i, p, q) = \begin{cases} \trueval & \text{si } i = p = q = 0, \\ \falseval & \text{si } i = 0, \\ f(i\!-\!1,\, p - a_i,\, q) \OR f(i\!-\!1,\, p,\, q - a_i) \OR f(i\!-\!1,\, p,\, q) & \text{en otro caso.} \end{cases}$$

Respuesta: $f(n, S/3, S/3)$. Complejidad: $O(n \cdot (S/3)^2)$.

Longest Increasing Subsequence

Problema. Dada una secuencia $a_1, \ldots, a_n$, encontrar la longitud de la subsecuencia estrictamente creciente más larga.

Recurrencia. Definimos $f(i)$ como la longitud del LIS que termina en la posición $i$.

$$f(i) = 1 + \max_{\substack{j < i \\ a_j < a_i}} f(j)$$

con $f(i) = 1$ si no existe tal $j$. Respuesta: $\max_i f(i)$.

El DP naive es $O(n^2)$. Con patience sort se logra $O(n \log n)$.

Longest Common Subsequence

Problema. Dados dos strings $a = a_1 \ldots a_n$ y $b = b_1 \ldots b_m$, encontrar la longitud de su subsecuencia común más larga.

Recurrencia. Definimos $f(i, j)$ como la longitud del LCS de $a_1 \ldots a_i$ y $b_1 \ldots b_j$.

$$f(i, j) = \begin{cases} 0 & \text{si } i = 0 \text{ o } j = 0, \\ f(i-1, j-1) + 1 & \text{si } a_i = b_j, \\ \max\{f(i-1, j),\ f(i, j-1)\} & \text{en otro caso.} \end{cases}$$

Respuesta: $f(n, m)$. Complejidad: $O(nm)$.

Edit Distance

Problema. Dados dos strings $x = x_1 \ldots x_n$ y $y = y_1 \ldots y_m$, la distancia de edición (Levenshtein) es el mínimo número de inserciones, eliminaciones y sustituciones para transformar $x$ en $y$.

Recurrencia. Definimos $f(i, j)$ como el costo mínimo para transformar $x_1 \ldots x_i$ en $y_1 \ldots y_j$.

$$f(i, j) = \begin{cases} i & \text{si } j = 0, \\ j & \text{si } i = 0, \\ f(i\!-\!1, j\!-\!1) & \text{si } x_i = y_j, \\ 1 + \min\{f(i\!-\!1, j\!-\!1),\ f(i\!-\!1, j),\ f(i, j\!-\!1)\} & \text{en otro caso.} \end{cases}$$

Respuesta: $f(n, m)$. Complejidad: $O(nm)$.

Sequence Alignment

Problema. Encontrar el alineamiento de mayor puntaje de dos strings $x$ y $y$ según una matriz de scoring $\delta$ sobre el alfabeto más un carácter gap -.

Recurrencia. Definimos $f(i, j)$ como el puntaje máximo de alineamiento para los sufijos $x_i \ldots x_n$ y $y_j \ldots y_m$.

$$f(i, j) = \begin{cases} 0 & \text{si } i > n \AND j > m, \\ \max \begin{cases} \delta(x_i, y_j) + f(i\!+\!1, j\!+\!1) & \text{si } i \leq n \AND j \leq m, \\ \delta(x_i, \mathtt{-}) + f(i\!+\!1, j) & \text{si } i \leq n, \\ \delta(\mathtt{-}, y_j) + f(i, j\!+\!1) & \text{si } j \leq m \end{cases} & \text{en otro caso.} \end{cases}$$

Respuesta: $f(1, 1)$. Complejidad: $O(nm)$.

Maximum Subarray

Problema. Dada una secuencia $s_1, s_2, \ldots, s_n$ de enteros, encontrar una subsecuencia contigua con suma máxima (algoritmo de Kadane).

Recurrencia. Definimos $f(i)$ como la suma máxima de una subsecuencia contigua que termina en la posición $i$.

$$f(i) = \begin{cases} s_1 & \text{si } i = 1, \\ \max\{f(i-1) + s_i,\ s_i\} & \text{en otro caso.} \end{cases}$$

Respuesta: $\max_{1 \leq i \leq n} f(i)$. Complejidad: $O(n)$.

Matrix Chain Multiplication

Problema. Dadas matrices $A_1, \ldots, A_n$ con dimensiones $p_0 \times p_1, \ldots, p_{n-1} \times p_n$, encontrar la parentización que minimiza el total de multiplicaciones escalares.

Recurrencia. Definimos $f(i, j)$ como el costo mínimo para multiplicar $A_i \cdots A_j$.

$$f(i, j) = \begin{cases} 0 & \text{si } i = j, \\ \displaystyle\min_{i \leq k < j} \{f(i, k) + f(k\!+\!1, j) + p_{i-1} \cdot p_k \cdot p_j\} & \text{en otro caso.} \end{cases}$$

Respuesta: $f(1, n)$. Complejidad: $O(n^3)$. Con la optimización de Knuth se reduce a $O(n^2)$.

Burst Balloons

Problema. Dados $n$ globos con valores $a_1, \ldots, a_n$, reventar el globo $k$ otorga $a_{k-1} \cdot a_k \cdot a_{k+1}$ monedas (con $a_0 = a_{n+1} = 1$). Encontrar el orden que maximiza las monedas.

Recurrencia. Definimos $f(l, r)$ como las monedas máximas al reventar todos los globos estrictamente entre $l$ y $r$.

$$f(l, r) = \max_{l < k < r} \{f(l, k) + f(k, r) + a_l \cdot a_k \cdot a_r\}$$

con $f(l, r) = 0$ si $r - l \leq 1$. Respuesta: $f(0, n\!+\!1)$. Complejidad: $O(n^3)$.

Palindrome Partitioning

Problema. Dado un string $s$ de longitud $n$, encontrar el mínimo número de cortes para particionar $s$ en palíndromos.

Recurrencia. Definimos $f(i)$ como los cortes mínimos para $s_1 \ldots s_i$.

$$f(i) = \begin{cases} 0 & \text{si } s_1 \ldots s_i \text{ es palíndromo,} \\ \displaystyle\min_{\substack{1 \leq j < i \\ s_{j+1}\ldots s_i \text{ palíndromo}}} \{f(j) + 1\} & \text{en otro caso.} \end{cases}$$

Respuesta: $f(n)$. Complejidad: $O(n^2)$.

Rod Cutting

Problema. Dada una barra de longitud $n$ y precios $p_1, \ldots, p_n$ donde $p_i$ es el precio por un trozo de longitud $i$, encontrar el ingreso máximo al cortar y vender la barra.

Recurrencia. Definimos $f(l)$ como el ingreso máximo para una barra de longitud $l$.

$$f(l) = \max_{1 \leq i \leq l} \{p_i + f(l - i)\}$$

con $f(0) = 0$. Respuesta: $f(n)$. Complejidad: $O(n^2)$.

Equivalente al unbounded knapsack con objetos de peso $i$ y valor $p_i$.

Travelling Salesman Problem

Problema. Dadas $n$ ciudades y distancias $d[i][j]$, encontrar el tour de costo mínimo que visita cada ciudad exactamente una vez y regresa al inicio.

Recurrencia (bitmask DP). Definimos $f(\mathrm{mask}, i)$ como el costo mínimo para visitar exactamente las ciudades en $\mathrm{mask}$, terminando en la ciudad $i$.

$$f(\mathrm{mask} \mid (1 \ll j),\ j) = \min_{i \in \mathrm{mask}} \{f(\mathrm{mask}, i) + d[i][j]\}$$

Base: $f(1 \ll 0,\ 0) = 0$. Respuesta: $\min_i \{f(2^n - 1, i) + d[i][0]\}$. Complejidad: $O(2^n \cdot n^2)$.

Max Independent Set on Tree

Problema. Dado un árbol con $n$ nodos (cada uno con peso $w_v$), encontrar un subconjunto de nodos no adyacentes con peso total máximo.

Recurrencia. Enraizar el árbol. Definimos:

  • $f(v, 0)$: mejor valor en el subárbol de $v$ cuando $v$ se excluye.
  • $f(v, 1)$: mejor valor cuando $v$ se incluye.

$$f(v, 0) = \sum_{u \in \mathrm{children}(v)} \max\{f(u, 0),\, f(u, 1)\}$$

$$f(v, 1) = w_v + \sum_{u \in \mathrm{children}(v)} f(u, 0)$$

Respuesta: $\max\{f(\mathrm{root}, 0),\, f(\mathrm{root}, 1)\}$. Complejidad: $O(n)$.

Tree Diameter

Problema. Encontrar el camino más largo (en aristas o pesos) entre dos nodos cualesquiera de un árbol.

Recurrencia. Enraizar el árbol. Definimos $f(v)$ como la longitud del camino más largo hacia abajo desde $v$.

$$f(v) = \max_{u \in \mathrm{children}(v)} \{1 + f(u)\}$$

con $f(\mathrm{hoja}) = 0$. El diámetro se actualiza en cada nodo como la suma de los dos caminos hijos más largos:

$$\mathrm{diámetro} = \max_v \{f_1(v) + f_2(v)\}$$

Complejidad: $O(n)$.

Digit DP

Problema. Contar enteros en $[0, N]$ que satisfacen restricciones sobre sus dígitos.

Recurrencia. Estado: $(\mathrm{pos},\, \mathrm{tight},\, \ldots)$ donde $\mathrm{tight}$ indica si el prefijo actual iguala el prefijo de $N$.

$$f(\mathrm{pos}, \mathrm{tight}, \ldots) = \sum_{d=0}^{\mathrm{limit}} f(\mathrm{pos}+1,\ \mathrm{tight} \AND (d = \mathrm{limit}),\ \ldots)$$

donde $\mathrm{limit} = N[\mathrm{pos}]$ si $\mathrm{tight}$, sino $9$. Para rango $[L, R]$: $f(R) - f(L-1)$.

DP on DAG

Problema. Encontrar el camino más largo (o corto), o contar caminos, en un grafo dirigido acíclico.

Recurrencia. Procesar vértices en orden topológico.

Camino más largo: $f(v) = \max_{u \to v} \{f(u) + w(u, v)\}$

Conteo de caminos: $\mathrm{cnt}(v) = \sum_{u \to v} \mathrm{cnt}(u)$

Expected Value DP

Problema. Calcular el costo esperado o número de pasos para alcanzar un estado terminal desde un estado inicial, con transiciones probabilísticas.

Recurrencia.

$$E[s] = \sum_{s'} p(s \to s') \cdot (c(s, s') + E[s'])$$

Propiedad clave: linealidad de la esperanza — $E[X_1 + \cdots + X_n] = \sum E[X_i]$, incluso cuando los $X_i$ son dependientes.

Game Theory DP

Problema. Dos jugadores alternan movimientos en un juego imparcial. Determinar quién gana con juego óptimo.

Recurrencia (Sprague-Grundy). Toda posición $s$ de un juego imparcial tiene un valor de Grundy:

$$\mathrm{SG}(s) = \mathrm{mex}\big(\{\mathrm{SG}(s') : s \to s'\}\big)$$

donde $\mathrm{mex}$ es el mínimo excluyente. Una posición es perdedora sii $\mathrm{SG}(s) = 0$.

Nim: $n$ pilas de tamaños $a_1, \ldots, a_n$. El primer jugador gana sii $a_1 \oplus \cdots \oplus a_n \neq 0$.

Creado originalmente en octubre de 2018 en la Universidad de Bergen. Expandido en abril de 2026.