La programación dinámica tiene fama de ser difícil de reconocer. En los concursos casi nunca lo es: se repite un número pequeño de formas, y reconocer la forma es casi todo el trabajo.
Cada programa de abajo está completo, se ejecutó en .NET 10, y su salida está pegada de la ejecución.
Patrón 41 — DP lineal, y el arreglo rodante
Casas en fila, cada una con dinero adentro, y no puedes robar dos casas contiguas.
En cada casa hay dos opciones, y las dos ya están resueltas por entradas anteriores: saltarla y quedarte con dp[i-1], o tomarla y sumarla a dp[i-2].
int[] money = [2, 7, 9, 3, 1];
// Full table: dp[i] is the best from the first i houses.
int[] dp = new int[money.Length + 1];
dp[1] = money[0];
for (int i = 2; i <= money.Length; i++)
{
int skip = dp[i - 1]; // do not rob house i-1
int take = dp[i - 2] + money[i - 1]; // rob it, so house i-2 is the last one allowed
dp[i] = Math.Max(skip, take);
Console.WriteLine($"house {i - 1} (${money[i - 1]}) skip={skip,2} take={take,2} -> dp[{i}]={dp[i]}");
}
Console.WriteLine($"\nfull table : [{string.Join(", ", dp)}] best = {dp[^1]}");
// Only the last two entries are ever read, so keep two ints.
int prev2 = 0, prev1 = 0;
foreach (int m in money)
{
int cur = Math.Max(prev1, prev2 + m);
(prev2, prev1) = (prev1, cur);
}
Console.WriteLine($"two ints : best = {prev1}");
Console.WriteLine($"memory : {money.Length + 1} ints -> 2");Imprime:
house 1 ($7) skip= 2 take= 7 -> dp[2]=7
house 2 ($9) skip= 7 take=11 -> dp[3]=11
house 3 ($3) skip=11 take=10 -> dp[4]=11
house 4 ($1) skip=11 take=12 -> dp[5]=12
full table : [0, 2, 7, 11, 11, 12] best = 12
two ints : best = 12
memory : 6 ints -> 2La segunda mitad es el hábito que vale la pena formar. Solo se leen dp[i-1] y dp[i-2], así que toda la tabla cabe en dos int. Aquí seis celdas se vuelven dos; con n = 10⁶ son 4MB que se vuelven 8 bytes, y a veces esa es la diferencia entre entrar en el límite de memoria o no.
Escribe primero la versión con tabla, hazla funcionar, y después mira qué tan atrás alcanza en realidad. Si la respuesta es «dos», hazla rodar.
Costo: O(n) en tiempo, O(1) en espacio después de rodarla.
Úsalo cuando cada posición dependa de un número fijo de posiciones anteriores: subir escaleras, el ladrón de casas, formas de decodificar, subarreglo de suma máxima.
Patrón 42 — La mochila, y el bucle que cambia la pregunta
Objetos con pesos y valores, una bolsa con capacidad, y cada objeto se puede tomar una sola vez.
Este es el patrón que trae trampa, y la trampa es una sola palabra.
El mismo arreglo, la misma expresión, los mismos objetos. Un for cuenta hacia arriba y el otro hacia abajo, y responden dos preguntas distintas. Nada en el código dice cuál querías.
int[] weight = [2, 3, 4];
int[] value = [3, 4, 5];
int capacity = 6;
// The two versions differ by ONE loop direction. Nothing else.
static int Knapsack(int[] weight, int[] value, int capacity, bool forwards)
{
int[] dp = new int[capacity + 1];
for (int i = 0; i < weight.Length; i++)
{
if (forwards)
for (int c = weight[i]; c <= capacity; c++)
dp[c] = Math.Max(dp[c], dp[c - weight[i]] + value[i]);
else
for (int c = capacity; c >= weight[i]; c--)
dp[c] = Math.Max(dp[c], dp[c - weight[i]] + value[i]);
}
return dp[capacity];
}
Console.WriteLine($"items: {string.Join(", ", weight.Zip(value, (w, v) => $"w={w} v={v}"))}");
Console.WriteLine($"capacity: {capacity}\n");
Console.WriteLine($"capacity descending : {Knapsack(weight, value, capacity, false)} each item used AT MOST ONCE (0/1)");
Console.WriteLine($"capacity ascending : {Knapsack(weight, value, capacity, true)} items reusable (unbounded)");
Console.WriteLine("\nascending reads dp[c - w] AFTER this same item already updated it,");
Console.WriteLine("so the item gets picked again. 2 + 2 + 2 fills the bag for 9.");
Console.WriteLine("descending reads a cell this item has not touched yet, so it stays 0/1: 2 + 4 for 8.");Imprime:
items: w=2 v=3, w=3 v=4, w=4 v=5
capacity: 6
capacity descending : 8 each item used AT MOST ONCE (0/1)
capacity ascending : 9 items reusable (unbounded)
ascending reads dp[c - w] AFTER this same item already updated it,
so the item gets picked again. 2 + 2 + 2 fills the bag for 9.
descending reads a cell this item has not touched yet, so it stays 0/1: 2 + 4 for 8.Dos respuestas distintas. El mismo arreglo, la misma expresión, los mismos objetos: la única diferencia es si el bucle de la capacidad cuenta hacia arriba o hacia abajo.
Hacia arriba, dp[c - w] ya fue actualizado por este objeto en esta pasada. Así que el objeto se suma sobre sí mismo, y 2 + 2 + 2 llena una bolsa de capacidad 6 por 9. Esa es la mochila no acotada.
Hacia abajo, dp[c - w] todavía guarda el valor de antes de considerar este objeto. Cada objeto aporta a lo más una vez, y la respuesta es 8. Esa es la mochila 0/1.
Los dos bucles compilan, los dos corren, los dos dan un número plausible. Nada en el código registra qué problema querías resolver.
Si de esta parte recuerdas una sola cosa: la 0/1 cuenta hacia abajo. Y cuando una respuesta de mochila salga demasiado alta, revisa la dirección del bucle antes que cualquier otra cosa.
Costo: O(objetos × capacidad) en tiempo, O(capacidad) en espacio.
Úsalo cuando estés eligiendo un subconjunto bajo un presupuesto: suma de subconjunto, partición en mitades iguales, cambio de monedas, suma objetivo.
Patrón 43 — Subsecuencia creciente más larga en O(n log n)
La versión O(n²) —para cada elemento, mirar hacia atrás todo lo anterior— es fácil y muchas veces demasiado lenta.
La versión rápida mantiene un arreglo donde tails[k] es el valor más pequeño que puede terminar una subsecuencia creciente de longitud k+1. Cada valor nuevo o extiende el arreglo o reemplaza la primera entrada que sea al menos igual de grande.
Cada casilla guarda el valor más pequeño que puede terminar una racha de esa longitud. Reemplazar nunca acorta nada — solo facilita las extensiones futuras —, y por eso la longitud del arreglo es la respuesta aunque su contenido no sea una subsecuencia real.
// tails[k] = the SMALLEST value that can end an increasing subsequence of
// length k+1. Only its LENGTH is meaningful; see the second example.
static List<int> Lis(int[] a, bool trace)
{
List<int> tails = [];
foreach (int x in a)
{
int pos = tails.BinarySearch(x);
if (pos < 0) pos = ~pos; // insertion point
if (pos == tails.Count)
{
tails.Add(x);
if (trace) Console.WriteLine($"{x,3} bigger than everything append tails=[{string.Join(",", tails)}]");
}
else
{
int old = tails[pos];
tails[pos] = x;
if (trace) Console.WriteLine($"{x,3} replaces {old,3} at index {pos} tails=[{string.Join(",", tails)}]");
}
}
return tails;
}
int[] a = [10, 9, 2, 5, 3, 7, 101, 18];
var t = Lis(a, true);
Console.WriteLine($"\nlongest increasing subsequence length: {t.Count}");
// Now the one that shows tails is not an answer, only a length.
int[] b = [3, 4, 5, 1, 2];
var t2 = Lis(b, false);
Console.WriteLine($"\nb = [{string.Join(", ", b)}]");
Console.WriteLine($"tails = [{string.Join(", ", t2)}] length {t2.Count} <- correct length");
Console.WriteLine($"but 1 and 2 appear at indices 3 and 4, while 5 is at index 2.");
Console.WriteLine($"so [1, 2, 5] is not a subsequence of b at all. An actual LIS is 3, 4, 5.");Imprime:
10 bigger than everything append tails=[10]
9 replaces 10 at index 0 tails=[9]
2 replaces 9 at index 0 tails=[2]
5 bigger than everything append tails=[2,5]
3 replaces 5 at index 1 tails=[2,3]
7 bigger than everything append tails=[2,3,7]
101 bigger than everything append tails=[2,3,7,101]
18 replaces 101 at index 3 tails=[2,3,7,18]
longest increasing subsequence length: 4
b = [3, 4, 5, 1, 2]
tails = [1, 2, 5] length 3 <- correct length
but 1 and 2 appear at indices 3 and 4, while 5 is at index 2.
so [1, 2, 5] is not a subsequence of b at all. An actual LIS is 3, 4, 5.Reemplazar nunca acorta nada. Baja el techo para extender una racha de esa longitud, y eso solo puede ayudar más adelante. Por eso tails.Count es la respuesta.
El segundo ejemplo está ahí porque la advertencia es fácil de decir y fácil de no creer. Para [3, 4, 5, 1, 2], tails termina como [1, 2, 5]: la longitud correcta, pero no es una subsecuencia de la entrada, porque 5 aparece antes que 1 y que 2. Si necesitas la subsecuencia real, guarda un índice predecesor por elemento y recorre hacia atrás.
List<T>.BinarySearch devuelve ~insertionPoint cuando falla, que es el patrón 16 de la parte 4 haciendo trabajo real aquí.
Costo: O(n log n) en tiempo, O(n) en espacio.
Úsalo cuando el problema trate de rachas crecientes o decrecientes: apilar cajas, muñecas rusas, patience sorting. Para creciente no estricto, cambia a una búsqueda por cota superior.
Patrón 44 — DP sobre cuadrícula
Dos secuencias, una tabla, y cada celda responde «cuánto cuesta reconciliar estos dos prefijos».
string s = "kitten", t = "sitting";
// dp[i,j] = edits to turn the first i of s into the first j of t.
int[,] dp = new int[s.Length + 1, t.Length + 1];
for (int i = 0; i <= s.Length; i++) dp[i, 0] = i; // delete everything
for (int j = 0; j <= t.Length; j++) dp[0, j] = j; // insert everything
for (int i = 1; i <= s.Length; i++)
for (int j = 1; j <= t.Length; j++)
{
dp[i, j] = s[i - 1] == t[j - 1]
? dp[i - 1, j - 1] // same letter, free
: 1 + Math.Min(dp[i - 1, j - 1], // substitute
Math.Min(dp[i - 1, j], // delete from s
dp[i, j - 1])); // insert into s
}
Console.Write(" ");
foreach (char c in t) Console.Write($"{c,4}");
Console.WriteLine();
for (int i = 0; i <= s.Length; i++)
{
Console.Write(i == 0 ? " " : $" {s[i - 1]} ");
for (int j = 0; j <= t.Length; j++) Console.Write($"{dp[i, j],4}");
Console.WriteLine();
}
Console.WriteLine($"\nedit distance(\"{s}\", \"{t}\") = {dp[s.Length, t.Length]}");
Console.WriteLine("k->s substitute, e->i substitute, insert g. Three edits.");Imprime:
s i t t i n g
0 1 2 3 4 5 6 7
k 1 1 2 3 4 5 6 7
i 2 2 1 2 3 4 5 6
t 3 3 2 1 2 3 4 5
t 4 4 3 2 1 2 3 4
e 5 5 4 3 2 2 3 4
n 6 6 5 4 3 3 2 3
edit distance("kitten", "sitting") = 3
k->s substitute, e->i substitute, insert g. Three edits.La primera fila y la primera columna son los casos base y tienen significado real: convertir algo en la cadena vacía cuesta un borrado por carácter. Si las equivocas, todas las demás celdas lo heredan.
Cada celda interior mira exactamente tres vecinas —la diagonal para sustituir, la de arriba para borrar, la de la izquierda para insertar— y la diagonal es gratis cuando los caracteres coinciden. La respuesta es la esquina inferior derecha, y el camino de vuelta por la tabla es el guion de ediciones real, si lo necesitas.
Solo se lee la fila anterior, así que esto rueda a dos filas igual que el patrón 41 rodó a dos int.
Costo: O(n × m) en tiempo, O(min(n, m)) en espacio después de rodarla.
Úsalo cuando se comparen o alineen dos secuencias: distancia de edición, subsecuencia común más larga, o caminos por una cuadrícula.
Patrón 45 — DP con máscara de bits
Cuando el estado es «qué subconjunto ya usé», y el conjunto es pequeño, el subconjunto es el índice del arreglo.
Un int tiene 32 bits. El bit i encendido significa que el objeto i está usado. Así que dp[mask][i] indexa directo, sin diccionario y sin hashing.
int[,] d =
{
{ 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 },
};
int n = 4;
// dp[mask, i] = cheapest route that starts at 0, visits exactly the cities in
// mask, and is currently standing at i. The mask IS the memo key — that is the
// whole idea, and it only works because n is small.
int[,] dp = new int[1 << n, n];
for (int m = 0; m < (1 << n); m++)
for (int i = 0; i < n; i++) dp[m, i] = int.MaxValue / 2;
dp[1, 0] = 0; // started at city 0, only 0 visited
for (int mask = 1; mask < (1 << n); mask++)
for (int i = 0; i < n; i++)
{
if ((mask & (1 << i)) == 0 || dp[mask, i] >= int.MaxValue / 2) continue;
for (int j = 0; j < n; j++)
{
if ((mask & (1 << j)) != 0) continue; // already visited
int next = mask | (1 << j);
int cost = dp[mask, i] + d[i, j];
if (cost < dp[next, j]) dp[next, j] = cost;
}
}
int full = (1 << n) - 1;
int best = int.MaxValue;
int bestEnd = -1;
for (int i = 1; i < n; i++)
{
int total = dp[full, i] + d[i, 0]; // and home again
Console.WriteLine($"visit everything, end at {i}: {dp[full, i],3} + {d[i, 0],3} home = {total}");
if (total < best) { best = total; bestEnd = i; }
}
Console.WriteLine($"\nbest tour: {best} (last city before home is {bestEnd})");
Console.WriteLine($"\ntable size 2^{n} x {n} = {(1 << n) * n} entries");
// (n-1)! distinct tours, because the starting city is fixed.
Console.WriteLine($"{"n",4} {"(n-1)! routes",24} {"2^n * n table",16}");
foreach (int k in new[] { 4, 8, 12, 16, 20 })
{
double fact = 1; for (int i = 2; i < k; i++) fact *= i;
Console.WriteLine($"{k,4} {fact,24:N0} {(long)(1L << k) * k,16:N0}");
}Imprime:
visit everything, end at 1: 70 + 10 home = 80
visit everything, end at 2: 65 + 15 home = 80
visit everything, end at 3: 75 + 20 home = 95
best tour: 80 (last city before home is 1)
table size 2^4 x 4 = 64 entries
n (n-1)! routes 2^n * n table
4 6 64
8 5,040 2,048
12 39,916,800 49,152
16 1,307,674,368,000 1,048,576
20 121,645,100,408,832,000 20,971,520La tabla del final es la justificación. Con n = 12, revisar cada ruta son 40 millones; la tabla son 49 mil. Con n = 20 son ciento veinte mil billones contra veinte millones.
Fíjate también en qué tan rápido crece 2^n × n por sí mismo. Esta es una técnica para n de hasta unos 20. En 25 ya son 800 millones de entradas, y no hay forma ingeniosa de esquivarlo: la exponencial se movió, no desapareció.
Las tres operaciones de bits son todo lo que necesitas: mask & (1 << i) prueba, mask | (1 << i) agrega, y (1 << n) - 1 es el conjunto completo.
Costo: O(2ⁿ × n²) en tiempo, O(2ⁿ × n) en espacio.
Úsalo cuando n ≤ 20 y el estado sea un subconjunto: el vendedor viajero, problemas de asignación, «cubrir todo al mínimo costo». Un n pequeño en las restricciones, cuando n cuenta cosas entre las que elegir, es casi un anuncio.
Qué recordar
-
Escribe la tabla completa, y después hazla rodar. Hazla funcionar, mira qué tan atrás alcanza, y encógela. Rodarla primero es como terminas depurando dos cosas a la vez.
-
La mochila 0/1 cuenta la capacidad HACIA ABAJO. Contar hacia arriba reutiliza el objeto y resuelve en silencio la versión no acotada. Este es el error de DP más común, y produce un número plausible.
-
tailsen el algoritmo de LIS es una longitud, no una respuesta. Su contenido no tiene por qué ser una subsecuencia de la entrada. -
Las filas y columnas base tienen significado. En la distancia de edición son el costo de borrar o insertar todo. Equivocarlas envenena la tabla entera.
-
Una máscara de bits es un índice de arreglo, no un objeto conjunto.
mask & (1 << i),mask | (1 << i),(1 << n) - 1. -
La DP con máscara de bits llega hasta n = 20 más o menos, y no más. Convierte un factorial en una exponencial, que es progreso, no una cura.
La parte 10 es la última, y es la parte que solo te importa después de que una solución correcta ya se pasó del límite de tiempo: entrada rápida, Span<T>, desbordamiento, aritmética modular, y salida con búfer.