Dynamic programming has a reputation for being hard to spot. In contests it is mostly not: a small number of shapes recur, and recognising the shape is most of the work.
Every program below is complete, was run on .NET 10, and its output is pasted from the run.
Pattern 41 — Linear DP, and the rolling array
Houses in a row, each with money in it, and you cannot rob two adjacent ones.
At each house there are two choices, and both are already answered by earlier entries: skip it and keep dp[i-1], or take it and add to 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");It prints:
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 -> 2The second half is the habit worth forming. Only dp[i-1] and dp[i-2] are ever read, so the whole table is two ints. Six cells becomes two here; at n = 10⁶ it is 4MB becoming 8 bytes, and that is sometimes the difference between fitting in the memory limit and not.
Write the table version first, get it right, then look at how far back it actually reaches. If the answer is “two”, roll it.
Cost: O(n) time, O(1) space after rolling.
Reach for it when each position depends on a fixed number of earlier positions — climbing stairs, house robber, decode ways, maximum subarray.
Pattern 42 — Knapsack, and the loop that changes the question
Items with weights and values, a bag with a capacity, and each item may be taken once.
This is the pattern with the trap in it, and the trap is one word.
Same array, same expression, same items. One for counts up and the other counts down, and they answer two different questions. Nothing in the code says which one you meant.
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.");It prints:
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.Two different answers. Same array, same expression, same items — the only difference is whether the capacity loop counts up or down.
Going up, dp[c - w] has already been updated by this item during this pass. So the item gets added on top of itself, and 2 + 2 + 2 fills a capacity-6 bag for 9. That is the unbounded knapsack.
Going down, dp[c - w] is still holding the value from before this item was considered. Each item contributes at most once, and the answer is 8. That is the 0/1 knapsack.
Both loops compile, both run, both produce a plausible number. Nothing in the code records which problem you meant.
If you only remember one thing from this part: 0/1 counts down. And when a knapsack answer comes out too high, check the loop direction before checking anything else.
Cost: O(items × capacity) time, O(capacity) space.
Reach for it when you are choosing a subset under a budget — subset sum, partition into equal halves, coin change, target sum.
Pattern 43 — Longest increasing subsequence in O(n log n)
The O(n²) version — for each element, look back at everything before it — is easy and often too slow.
The faster version keeps an array where tails[k] is the smallest value that can end an increasing subsequence of length k+1. Each new value either extends the array or replaces the first entry that is at least as large.
Each slot holds the smallest value that can end a run of that length. Replacing never shortens anything — it only makes future extensions easier — which is why the array’s length is the answer even though its contents may not be a real subsequence.
// 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.");It prints:
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.Replacing never shortens anything. It lowers the ceiling for extending a run of that length, which can only help later. That is why tails.Count is the answer.
The second example is there because the caveat is easy to state and easy to disbelieve. For [3, 4, 5, 1, 2], tails ends up [1, 2, 5] — the right length, but not a subsequence of the input at all, since 5 occurs before 1 and 2. If you need the actual subsequence, record a predecessor index per element and walk back.
List<T>.BinarySearch returns ~insertionPoint on a miss, which is pattern 16 from part 4 doing real work here.
Cost: O(n log n) time, O(n) space.
Reach for it when the problem is about increasing or decreasing runs — box stacking, Russian dolls, patience sorting. For non-strictly increasing, switch to an upper-bound search.
Pattern 44 — Grid DP
Two sequences, one table, and each cell answers “what does it cost to reconcile these two prefixes”.
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.");It prints:
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.The first row and column are the base cases and they carry real meaning: turning something into the empty string costs one delete per character. Get them wrong and every other cell inherits it.
Each interior cell looks at exactly three neighbours — diagonal for substitute, up for delete, left for insert — and the diagonal is free when the characters match. The answer is the bottom-right corner, and the path back through the table is the actual edit script if you need it.
Only the previous row is ever read, so this rolls to two rows the same way pattern 41 rolled to two ints.
Cost: O(n × m) time, O(min(n, m)) space after rolling.
Reach for it when two sequences are being compared or aligned — edit distance, longest common subsequence, or paths through a grid.
Pattern 45 — Bitmask DP
When the state is “which subset have I already used”, and the set is small, the subset is the array index.
An int is 32 bits. Bit i set means item i is used. So dp[mask][i] indexes directly, with no dictionary and no 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}");
}It prints:
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,520The table at the end is the justification. At n = 12, checking every route is 40 million; the table is 49 thousand. At n = 20 it is a hundred and twenty quadrillion against twenty million.
Note also how quickly 2^n × n itself grows. This is a technique for n up to about 20. At 25 it is already 800 million entries, and there is no clever way around it — the exponential moved, it did not go away.
The three bit operations are all you need: mask & (1 << i) tests, mask | (1 << i) adds, and (1 << n) - 1 is the full set.
Cost: O(2ⁿ × n²) time, O(2ⁿ × n) space.
Reach for it when n ≤ 20 and the state is a subset — travelling salesman, assignment problems, “cover everything at minimum cost”. A small n in the constraints, when n is a count of things to choose among, is close to an announcement.
What to remember
-
Write the full table, then roll it. Get it right, see how far back it reaches, and shrink. Rolling first is how you end up debugging two things at once.
-
0/1 knapsack counts the capacity DOWN. Counting up reuses the item and silently solves the unbounded version instead. This is the most common DP bug and it produces a plausible number.
-
tailsin the LIS algorithm is a length, not an answer. Its contents need not be a subsequence of the input at all. -
Base rows and columns carry meaning. In edit distance they are the cost of deleting or inserting everything. Getting them wrong poisons the whole table.
-
A bitmask is an array index, not a set object.
mask & (1 << i),mask | (1 << i),(1 << n) - 1. -
Bitmask DP works to about n = 20 and no further. It converts a factorial into an exponential, which is progress, not a cure.
Part 10 is the last one, and it is the part you only care about after a correct solution has already timed out: fast input, Span<T>, overflow, modular arithmetic, and buffered output.