Programação dinâmica tem fama de ser difícil de reconhecer. Em maratonas quase nunca é: um número pequeno de formas se repete, e reconhecer a forma é quase todo o trabalho.
Todo programa abaixo está completo, rodou no .NET 10, e a saída está colada da execução.
Padrão 41 — DP linear, e o array rolante
Casas em fila, cada uma com dinheiro dentro, e você não pode roubar duas vizinhas.
Em cada casa há duas opções, e as duas já foram respondidas por entradas anteriores: pular a casa e ficar com dp[i-1], ou pegar e somar em 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");Ele 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 -> 2A segunda metade é o hábito que vale a pena criar. Só dp[i-1] e dp[i-2] são lidos, então a tabela inteira vira dois ints. Aqui seis células viram duas; com n = 10⁶ são 4MB virando 8 bytes, e isso às vezes é a diferença entre caber no limite de memória e não caber.
Escreva primeiro a versão com tabela, acerte ela, e depois veja quanto ela realmente olha para trás. Se a resposta for “dois”, role a tabela.
Custo: O(n) de tempo, O(1) de espaço depois de rolar.
Use quando cada posição depender de um número fixo de posições anteriores — subir escadas, o ladrão de casas, formas de decodificar, subarray de soma máxima.
Padrão 42 — Mochila, e o laço que muda a pergunta
Itens com pesos e valores, uma mochila com capacidade, e cada item pode ser levado uma vez.
Esse é o padrão que tem a armadilha, e a armadilha é uma palavra só.
O mesmo array, a mesma expressão, os mesmos itens. Um for conta para cima e o outro conta para baixo, e eles respondem duas perguntas diferentes. Nada no código diz qual delas você queria.
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.");Ele 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.Duas respostas diferentes. O mesmo array, a mesma expressão, os mesmos itens — a única diferença é se o laço da capacidade conta para cima ou para baixo.
Indo para cima, dp[c - w] já foi atualizado por este item nesta mesma passada. Então o item é somado em cima de si mesmo, e 2 + 2 + 2 enche uma mochila de capacidade 6 por 9. Essa é a mochila ilimitada.
Indo para baixo, dp[c - w] ainda guarda o valor de antes de este item ser considerado. Cada item contribui no máximo uma vez, e a resposta é 8. Essa é a mochila 0/1.
Os dois laços compilam, os dois rodam, os dois produzem um número plausível. Nada no código registra qual problema você quis resolver.
Se você só lembrar de uma coisa desta parte: 0/1 conta para baixo. E quando uma resposta de mochila sai alta demais, confira a direção do laço antes de conferir qualquer outra coisa.
Custo: O(itens × capacidade) de tempo, O(capacidade) de espaço.
Use quando você estiver escolhendo um subconjunto dentro de um orçamento — soma de subconjunto, partição em metades iguais, troco de moedas, soma alvo.
Padrão 43 — Subsequência crescente mais longa em O(n log n)
A versão O(n²) — para cada elemento, olhar tudo que veio antes dele — é fácil e muitas vezes lenta demais.
A versão rápida mantém um array onde tails[k] é o menor valor que pode terminar uma subsequência crescente de tamanho k+1. Cada valor novo ou estende o array ou substitui a primeira entrada que é pelo menos tão grande quanto ele.
Cada casa guarda o menor valor que pode terminar um trecho desse tamanho. Substituir nunca encurta nada — só facilita as extensões futuras — e é por isso que o tamanho do array é a resposta mesmo que o conteúdo dele não seja uma subsequência 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.");Ele 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.Substituir nunca encurta nada. Isso baixa o teto para estender um trecho desse tamanho, o que só ajuda depois. É por isso que tails.Count é a resposta.
O segundo exemplo está aí porque a ressalva é fácil de dizer e fácil de não acreditar. Para [3, 4, 5, 1, 2], tails termina como [1, 2, 5] — o tamanho certo, mas não é subsequência nenhuma da entrada, já que 5 aparece antes de 1 e 2. Se você precisa da subsequência de verdade, guarde um índice de predecessor por elemento e volte por ele.
List<T>.BinarySearch devolve ~insertionPoint quando não acha, que é o padrão 16 da parte 4 fazendo trabalho de verdade aqui.
Custo: O(n log n) de tempo, O(n) de espaço.
Use quando o problema for sobre trechos crescentes ou decrescentes — empilhar caixas, bonecas russas, patience sorting. Para crescente não estrito, troque por uma busca por limite superior.
Padrão 44 — DP em grade
Duas sequências, uma tabela, e cada célula responde “quanto custa conciliar estes dois prefixos”.
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.");Ele 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.A primeira linha e a primeira coluna são os casos base e carregam significado real: transformar algo na string vazia custa uma remoção por caractere. Erre nelas e todas as outras células herdam o erro.
Cada célula interna olha exatamente três vizinhas — a diagonal para substituir, a de cima para remover, a da esquerda para inserir — e a diagonal é de graça quando os caracteres batem. A resposta é o canto inferior direito, e o caminho de volta pela tabela é o roteiro de edições, se você precisar dele.
Só a linha anterior é lida, então isso rola para duas linhas do mesmo jeito que o padrão 41 rolou para dois ints.
Custo: O(n × m) de tempo, O(min(n, m)) de espaço depois de rolar.
Use quando duas sequências estiverem sendo comparadas ou alinhadas — distância de edição, subsequência comum mais longa, ou caminhos por uma grade.
Padrão 45 — DP com bitmask
Quando o estado é “qual subconjunto eu já usei”, e o conjunto é pequeno, o subconjunto é o índice do array.
Um int tem 32 bits. O bit i ligado quer dizer que o item i foi usado. Então dp[mask][i] indexa direto, sem dicionário e sem 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}");
}Ele 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,520A tabela no fim é a justificativa. Com n = 12, conferir todas as rotas dá 40 milhões; a tabela dá 49 mil. Com n = 20 são cento e vinte quatrilhões contra vinte milhões.
Repare também na velocidade com que 2^n × n cresce. Essa é uma técnica para n até uns 20. Com 25 já são 800 milhões de entradas, e não tem jeito esperto de escapar — o exponencial mudou de lugar, ele não sumiu.
As três operações de bit são tudo que você precisa: mask & (1 << i) testa, mask | (1 << i) adiciona, e (1 << n) - 1 é o conjunto completo.
Custo: O(2ⁿ × n²) de tempo, O(2ⁿ × n) de espaço.
Use quando n ≤ 20 e o estado for um subconjunto — caixeiro-viajante, problemas de atribuição, “cobrir tudo com custo mínimo”. Um n pequeno nas restrições, quando n conta coisas entre as quais escolher, é quase um anúncio.
O que lembrar
-
Escreva a tabela inteira, depois role. Acerte, veja quanto ela olha para trás, e encolha. Rolar primeiro é como você acaba depurando duas coisas ao mesmo tempo.
-
A mochila 0/1 conta a capacidade PARA BAIXO. Contar para cima reusa o item e resolve, em silêncio, a versão ilimitada. Esse é o bug de DP mais comum e ele produz um número plausível.
-
tailsno algoritmo de LIS é um tamanho, não uma resposta. O conteúdo dele não precisa ser subsequência nenhuma da entrada. -
Linhas e colunas base carregam significado. Na distância de edição elas são o custo de remover ou inserir tudo. Errar nelas envenena a tabela inteira.
-
Um bitmask é um índice de array, não um objeto de conjunto.
mask & (1 << i),mask | (1 << i),(1 << n) - 1. -
DP com bitmask funciona até uns n = 20 e não além. Ela converte um fatorial em um exponencial, o que é progresso, não cura.
A parte 10 é a última, e é a parte com que você só se importa depois que uma solução correta já estourou o limite de tempo: entrada rápida, Span<T>, overflow, aritmética modular, e saída com buffer.