📈 复杂动态规划

动态规划像搭积木：小问题的答案先算好、记住，再一块块拼出大答案。七级要挑战更复杂的积木城堡——一张网格表（二维）、一段一段合并（区间）、找出「最长的上升/公共序列」，还要学会用滚动数组让程序少占内存。

考纲知识点：二维动态规划、动态规划最值优化
区间动态规划
求最长上升子序列（LIS）
求最长公共子序列（LCS）
基于滚动数组的动态规划空间复杂度优化

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 七级

(2)掌握复杂动态规划（二维动态规划、动态规划最值优化）。包括区间动态规划、最长上升子序列（LIS）、最长公共子序列（LCS）等内容，理解基于滚动数组等降低动态规划空间复杂度的方法。

📚

先学一学

花 6 分钟读完下面 5 课，再去闯关就不慌啦

🗺️ 二维动态规划：一张表存答案

一维 DP 用一行格子记答案，二维 DP 就要用一张表：状态有两个下标，比如 dp[i][j] 表示「走到第 i 行第 j 列时能得到的最好结果」。小勇士从网格左上角走到右下角，每次只能向右或向下，求「捡到数字最大/最小」——每个格子的答案，都从上面那格或左边那格传下来。

🏁 走格子：右边和下面，谁更好选谁

以「最大数字和」为例：走到 (i, j) 前，一定在上边 (i-1, j) 或左边 (i, j-1)。所以取两个里面较大的那个，再加上本格数字：
dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1])

第一行只能从左边来，第一列只能从上边来，要先单独填好，当作「起跑线」。

💡 口诀：表格一格一格填，先起跑线再中间；上面左边取最优，加上本格往前走。

🧪 读代码：填一张计数表

看得懂就好，不用背：下面的代码每个格子的值 = 上面 + 左边，像给路径计数。

path[0][0] = 1;
for (int i = 1; i < N; i++) path[i][0] = 1;
for (int j = 1; j < N; j++) path[0][j] = 1;
for (int i = 1; i < N; i++)
for (int j = 1; j < N; j++)
path[i][j] = path[i-1][j] + path[i][j-1];

填表顺序很重要：必须先算好被依赖的上面和左边，才能算当前格——所以一般按行从上到下、每行从左到右。

🪜 最长上升子序列 LIS：挑一段越爬越高的台阶

子序列是从原序列里按原顺序挑出来的一串数，可以跳过一些数、但顺序不能乱。上升指后一个总比前一个大。比如序列 {2,7,1,5,6,4,3,8,9} 里，{2,5,6,8,9} 和 {1,5,6,8,9} 都是长度为 5 的最长上升子序列（LIS）。

💡 LIS 的两个小陷阱

· 子序列不必连续：{2,5,6,8,9} 在原序列里是跳着挑的（跳过了 7、1、4、3）。

· 最长可能不唯一：上面序列就有两个同样长 5 的最长上升子序列，所以别说是「唯一」的。

💡 口诀：子序列能跳过，顺序不能乱；最长不唯一，别急着说「只有一个」。

🧪 读代码：LIS 的状态转移

看得懂就好，不用背：dp[i] 存「以第 i 个数结尾的最长上升子序列长度」。对每个 i，看看前面比它小的 j，谁帮它续得最长。

for (int i = 0; i < n; i++) {
  dp[i] = 1; // 只有自己也算长度 1
  for (int j = 0; j < i; j++)
    if (nums[j] < nums[i])
      dp[i] = max(dp[i], dp[j] + 1); // 把 nums[i] 接在 nums[j] 后面
}

答案 = 所有 dp[i] 里最大的那个。

🤝 最长公共子序列 LCS：两条队伍共同的最长排队方式

两个队伍（字符串或序列），都按自己的原顺序挑一些人出来，两边挑出的结果一模一样，就叫做它们的公共子序列。其中最长的那串，就是最长公共子序列 LCS。

🧪 读代码：LCS 用一张表比较

看得懂就好，不用背：用 dp[i][j] 记「A 的前 i 个和 B 的前 j 个的 LCS 长度」。

// 两个字符相同：长度 = 左上角 + 1
if (A[i] == B[j])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
// 右下角 dp[n][m] 就是 LCS 长度

LCS 长度是 5，说明 A、B 里至少有 5 个公共字符能按顺序对上号（但不一定是连续的公共子串）。

💡 口诀：相同取左上再加一，不同看上面左边谁更大；右下角一瞧，公共最长就明了。

📱 行业实际：查重和比对都用 LCS

论文查重、代码抄袭检测、DNA 序列比对，都会算「两段内容最长的公共部分」。比对软件说「这两段相似度 80%」，背后常常就是 LCS 在数共同长度。

🧩 区间动态规划：先拼小区间，再并大区间

有的问题要处理一段「连续的区间」：比如把一堆石子排成一圈、两两合并算最小力气，或者给一串括号算怎么配对。这类问题用区间 DP：状态是「从 i 到 j 这段区间」，答案靠把大区间从中间某个位置 k 切开，合并左右两个小区间的答案。

🧭 为什么从小区间开始？

因为大区间 dp[i][j] 要依赖两个更短的区间 dp[i][k] 和 dp[k+1][j]。必须先把短的算好，再算长的——就像先搭好小积木块，才能拼大城堡。

💡 口诀：区间 DP 看长度，短的先算长的后；从中间 k 一分为二，两半最优再加和。

🌟 小发现：代码里的卡特兰数也是这个味道

有一种递推把「n 个元素」拆成「前面 j 个」和「后面 n-j-1 个」相乘再累加，比如 h[n] += h[j] × h[n-j-1]。它和区间合并思想很像，算出来 1、1、2、5、14、42、132……叫卡特兰数，括号配对、出栈顺序都能用它数。

🌀 滚动数组：只用两行，省下整张表

二维 DP 常常要开一张 n × m 的大表。可观察一下：算第 i 行时，只用得到第 i−1 行（再往前的行没用了）。那就别开整张表，只保留上一行、滚动着覆盖，这叫滚动数组。空间从 O(n²) 一路省到 O(n)，时间不变。

🎒 例子：0/1 背包的滚动优化

0/1 背包：每个物品只能拿一次，问容量有限时最多能装多少价值。本来用 dp[i][c] 二维表，滚动后只剩一维 dp[c]。

看得懂就好，不用背——注意容量 c 要从大到小循环：

for (int i = 1; i <= n; i++)
for (int c = W; c >= w[i]; c--)
dp[c] = max(dp[c], dp[c - w[i]] + v[i]);

从大到小是为了保证「新算的 dp[c]」不会马上被同一个物品再用来更新一次——这样每件物品最多被选一次。若从小到大循环，物品就能被反复选，那就变成「完全背包」啦。

💡 口诀：0/1 背包一维滚，容量倒着走；LCS 两行来回滚，n² 变 n 超省内存。

🧪 读代码：LCS 的滚动数组

看得懂就好，不用背：LCS 填表时每格只依赖上一行和本行左边，所以两行数组来回倒就能算完。

for (int i = 1; i <= n; i++)
  for (int j = 1; j <= m; j++)
    if (A[i] == B[j]) cur[j] = pre[j-1] + 1;
    else cur[j] = max(pre[j], cur[j-1]);
  swap(pre, cur); // 滚动：旧行退休，新行上岗

滚动数组只省空间，不改答案；时间复杂度保持不变。

🎯

闯关小锦囊 · 考点提醒

二维 DP：状态是 dp[i][j]，先填好第一行第一列，再按「上面或左边取最优 + 本格」填中间。
走网格「求最大数字和」用 max、「求最小和」用 min，别忘了加上当前格子的值。
LIS 最长上升子序列：子序列可以跳着挑但不能乱顺序；上升指后一个更大；最长可能不唯一。
LCS 最长公共子序列：字符相同取左上 +1；不同取上、左较大者；LCS 长为 5 说明至少有 5 个公共字符能按顺序对上。
区间 DP：状态是一段区间 [i, j]，先算短区间再拼长区间，中间用 k 切开合并。
滚动数组：算第 i 行只用第 i−1 行，空间从 O(n²) 降到 O(n)；0/1 背包一维滚动时容量从大到小循环。
DP 填表顺序：被依赖的子状态必须先算好，父状态再算。

🎮

学完了？来闯关！

下面 16 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。