不讲理论，只讲反复出现的五种动态规划模式，外加一个循环方向：写反了，其中一种模式就会悄悄变成另一个完全不同的问题。
动态规划素来以难以识别著称。在竞赛里，大多数时候并非如此：反复出现的题型就那么几种，认出题型，活就干完了一大半。
下面每个程序都是完整的，都在 .NET 10 上运行过，输出直接从运行结果里复制。
模式 41 — 线性 DP 与滚动数组
一排房子，每间都有钱，不能偷相邻的两间。
每到一间房子都有两个选择，而两种选择的答案都已经在前面的表项里：不偷，保留 dp[i-1]；偷，在 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");输出：
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 -> 2后半段是值得养成的习惯。程序只读过 dp[i-1] 和 dp[i-2]，所以整张表用两个 int 就够了。这里是 6 个格子变成 2 个；到了 n = 10⁶，就是 4MB 变成 8 字节，有时这正是能否挤进内存限制的差别。
先写完整的表，写对，再看它实际往回读了多远。如果答案是“两格”，就把它滚动起来。
代价： 时间 O(n)，滚动后空间 O(1)。
适用场景： 每个位置只依赖前面固定数量的位置，比如爬楼梯、打家劫舍、解码方法、最大子数组和。
模式 42 — 背包，以及改变问题的那个循环
一些物品，各有重量和价值；一个背包，有容量上限；每件物品只能拿一次。
这个模式里藏着陷阱，而陷阱小到只有一个词。
同一个数组，同一个表达式，同一批物品。一个 for 往上数，另一个往下数，回答的却是两个不同的问题。代码里没有任何地方写明你想要哪一个。
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.");输出：
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.两个不同的答案。同一个数组，同一个表达式，同一批物品，唯一的区别是容量循环往上数还是往下数。
往上数时，dp[c - w] 在这一轮里已经被当前物品更新过。于是物品叠加在自己身上，2 + 2 + 2 装满容量为 6 的背包，得到 9。这是完全背包。
往下数时，dp[c - w] 保存的仍是考虑当前物品之前的值。每件物品最多贡献一次，答案是 8。这是 0/1 背包。
两个循环都能编译，都能运行，都给出一个看似合理的数。代码里没有任何地方记录你想解的是哪个问题。
这一篇如果只记一件事，那就是：0/1 背包往下数。背包的答案偏大时，先查循环方向，再查别的。
代价： 时间 O(物品数 × 容量)，空间 O(容量)。
适用场景： 在预算限制下选子集，比如子集和、分割等和子集、零钱兑换、目标和。
模式 43 — O(n log n) 求最长递增子序列
O(n²) 的写法是对每个元素回头看它前面的所有元素。写起来简单，但经常太慢。
更快的写法维护一个数组，tails[k] 是能作为长度 k+1 的递增子序列结尾的最小值。每来一个新值，要么追加到数组末尾，要么替换第一个大于等于它的元素。
每个位置保存能作为该长度序列结尾的最小值。替换永远不会让任何序列变短，只会让以后更容易延长。所以即使数组的内容未必是真实的子序列，它的长度仍然是答案。
// 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.");输出：
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.替换永远不会让任何序列变短。它降低的是延长该长度序列的门槛，对后面只有好处。所以答案是 tails.Count。
第二个例子之所以放在这里，是因为这条注意事项说起来容易，却很难让人相信。对 [3, 4, 5, 1, 2]，tails 最后是 [1, 2, 5]：长度对了，却根本不是输入的子序列，因为 5 出现在 1 和 2 之前。如果需要真正的子序列，就给每个元素记录前驱索引，再倒着走回去。
List<T>.BinarySearch 没找到时返回 ~insertionPoint，这正是第 4 篇里的模式 16 在这里派上用场。
代价： 时间 O(n log n)，空间 O(n)。
适用场景： 题目涉及递增或递减的序列，比如堆箱子、俄罗斯套娃信封、耐心排序。如果是非严格递增，改用上界（upper bound）查找。
模式 44 — 网格 DP
两个序列，一张表，每个格子回答的是“让这两个前缀一致要花多少代价”。
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.");输出：
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.第一行和第一列是基准情况，它们有实际含义：把一个字符串变成空串，每个字符要删一次。这里写错，其他所有格子都会跟着错。
每个内部格子恰好看三个邻居：左上对角线表示替换，上方表示删除，左方表示插入；字符相同时，对角线不花代价。答案在右下角。如果需要具体的编辑步骤，从表里倒推回去的路径就是。
程序只读上一行，所以可以像模式 41 滚动成两个 int 那样，滚动成两行。
代价： 时间 O(n × m)，滚动后空间 O(min(n, m))。
适用场景： 比较或对齐两个序列，比如编辑距离、最长公共子序列（LCS），或者网格中的路径。
模式 45 — 状压 DP
当状态是“哪些元素已经用过”，并且集合很小时，这个子集本身就是数组下标。
一个 int 有 32 位。第 i 位为 1，表示第 i 个元素用过了。所以 dp[mask][i] 可以直接索引，不需要字典，也不需要哈希。
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}");
}输出：
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,520最后那张表就是理由。n = 12 时，逐条检查路线要 4000 万次，而表只有 4.9 万项。n = 20 时，是 12 京对 2000 万。
也要注意 2^n × n 本身涨得有多快。这个技巧适用于 n 不超过 20 左右。到 25 时已经是 8 亿项，而且没有什么巧妙的办法绕过去：指数级只是换了个位置，并没有消失。
需要的位运算只有三个：mask & (1 << i) 用来测试，mask | (1 << i) 用来加入，(1 << n) - 1 是全集。
代价： 时间 O(2ⁿ × n²)，空间 O(2ⁿ × n)。
适用场景： n ≤ 20 且状态是一个子集，比如旅行商问题、分配问题、“以最小代价覆盖全部”。约束里的 n 很小，而且 n 是可供选择的东西的个数时，这几乎就是在明说了。
要点
- 先写完整的表，再滚动。 先写对，看清它往回读多远，再压缩。一上来就滚动，结果就是同时调试两件事。
- 0/1 背包的容量循环要往下数。 往上数会重复使用物品，悄悄解成了完全背包。这是 DP 里最常见的 bug，而且给出的数看起来很合理。
- LIS 算法里的
tails代表长度，不是答案。 它的内容根本不必是输入的子序列。 - 作为基准情况的行和列有实际含义。 在编辑距离里，它们是全部删除或全部插入的代价。写错了，整张表都会被污染。
- 位掩码是数组下标，不是集合对象。
mask & (1 << i)、mask | (1 << i)、(1 << n) - 1。 - 状压 DP 最多做到 n = 20 左右，再大就不行了。 它把阶乘变成了指数，这是进步，但不是根治。
第 10 篇是最后一篇，讲的是只有在正确的解法已经超时之后你才会在意的东西：快速输入、Span<T>、溢出、取模运算和缓冲输出。