不用递归，直接按顺序把每个子问题的答案填进一张表里——用两个经典问题（最长上升子序列、最长公共子序列）掌握动态规划最基本的写法。
12.4 节的记忆化搜索，本质上是自顶向下：从要求的大问题出发，递归拆成小问题，遇到算过的就查表。这一节要学的动态规划（递推式 DP），做的是完全相反的事——自底向上：不用递归，先确定"从哪个最小的子问题开始"，按一个固定的顺序，把每个子问题的答案依次填进一张表（数组）里，后面的答案直接利用表里已经算好的前面的答案，一路推到最终想要的结果。
两种写法能解决的是同一类问题，效率也一样，区别只在于"用递归查表"还是"按顺序填表"。写递推式 DP，通常需要想清楚四件事，本节和 13.2 节都会反复用到这个框架：
| 要素 | 要回答的问题 |
|---|---|
| 状态定义 | dp 数组的每一格，具体表示"什么问题的答案"？ |
| 转移方程 | 当前这一格的答案，怎么由前面已经算好的格子推出来？ |
| 初始化 | 最小的子问题（表的起点）答案是什么，需要手动设定？ |
| 填表顺序 | 按什么顺序遍历数组，才能保证算某一格时，它依赖的格子都已经算好了？ |
最长上升子序列（Longest Increasing Subsequence，简称 LIS）：给定一个数组，找出其中最长的一段子序列，使得这段子序列严格递增。这里的"子序列"不要求连续，只要求在原数组里的相对顺序不变——可以跳着选。
例如数组 [3, 1, 4, 1, 5, 9, 2, 6]，子序列 1, 4, 5, 9（下标 1、2、4、5）就是严格递增的，而且是这个数组里能找到的最长的一段——长度为 4。
状态定义：设 dp[i] 表示以 a[i] 结尾的最长上升子序列的长度（注意是"以 a[i] 结尾"，不是"前 i 个数里最长的"——这个区别很关键，见 ⑧ 的陷阱）。转移方程：
dp[i] = max{ dp[j] + 1 } ，其中 0 ≤ j < i 且 a[j] < a[i]
如果 a[i] 前面找不到任何一个比它小的 a[j]，说明 a[i] 自己单独就是一段长度为 1 的上升子序列，dp[i] = 1。含义是：枚举所有排在 i 前面、且比 a[i] 小的 a[j]，把 a[i] 接在"以 a[j] 结尾的最长上升子序列"后面，取所有接法里最长的一种。
以 [3, 1, 4, 1, 5, 9, 2, 6] 为例，按下标从 0 到 7 依次算出每个 dp[i]：
3 → 4 → 5 → 9（下标 0、2、4、5）就是一条长度为 4 的上升子序列，对应的 dp 值 1,2,3,4 逐级递增——每一步都是"接在前一个数后面，长度 +1"。a[7]=6 的 dp[7] 也是 4（比如接在 3,4,5 后面），说明最长上升子序列不止一条，但长度都是 4，也就是整个数组 dp 值里的最大值。拿 dp[5]（对应 a[5]=9）具体展开看：需要检查下标 0~4 里所有比 9 小的数，取它们 dp 值中最大的那个，再 +1：
| j | a[j] | a[j] < 9？ | 候选值 dp[j]+1 |
|---|---|---|---|
| 0 | 3 | 是 | 1+1=2 |
| 1 | 1 | 是 | 1+1=2 |
| 2 | 4 | 是 | 2+1=3 |
| 3 | 1 | 是 | 1+1=2 |
| 4 | 5 | 是 | 3+1=4（最大） |
| 1 | int a[1005], dp[1005], n; |
| 2 | |
| 3 | int LIS() |
| 4 | { |
| 5 | int ans = 0; |
| 6 | for (int i = 0; i < n; i++) // 按顺序从 0 号填到 n-1 号 |
| 7 | { |
| 8 | dp[i] = 1; // 初始化：自己单独一个，长度至少是 1 |
| 9 | for (int j = 0; j < i; j++) // 回头看前面所有已经填好的 dp[j] |
| 10 | { |
| 11 | if (a[j] < a[i]) |
| 12 | dp[i] = max(dp[i], dp[j] + 1); |
| 13 | } |
| 14 | ans = max(ans, dp[i]); // 答案不一定是 dp[n-1]，取所有 dp[i] 里最大的 |
| 15 | } |
| 16 | return ans; |
| 17 | } |
a[i] 结尾的最长上升子序列长度"；转移方程是第 11、12 行；初始化是第 8 行（每个数自己长度至少是 1）；填表顺序是"从下标 0 到 n-1 依次填"——因为算 dp[i] 要用到前面所有的 dp[j]（j<i)，必须保证填 i 时，0~i-1 都已经填好了，从左到右填正好满足这个要求。最长公共子序列（Longest Common Subsequence，简称 LCS）：给定两个字符串 X 和 Y，找出同时是两者子序列的最长字符串。同样不要求连续，只要求在各自原串里的相对顺序不变。
例如 X = "ABCD"，Y = "ACBD"，最长公共子序列是 "ABD"（长度 3）：在 X 里是第 1、2、4 个字符，在 Y 里是第 1、3、4 个字符，两边的相对顺序都保持不变。
这个问题涉及两个字符串，状态自然需要两个维度：设 dp[i][j] 表示 X 的前 i 个字符和 Y 的前 j 个字符的最长公共子序列长度。转移方程分两种情况：
若 X[i] == Y[j]： dp[i][j] = dp[i-1][j-1] + 1
两个字符匹配上了，公共子序列可以在此基础上延长一位——直接用"去掉这两个字符之前"的答案 dp[i-1][j-1] 加 1。
若 X[i] != Y[j]： dp[i][j] = max( dp[i-1][j], dp[i][j-1] )
两个字符匹配不上，说明它们里至少有一个不出现在最终的公共子序列里——要么丢弃 X[i]（答案等于 dp[i-1][j]），要么丢弃 Y[j]（答案等于 dp[i][j-1]），取两者较大的一个。
dp[0][j] 和 dp[i][0] 全部是 0——"其中一个字符串长度为 0"，公共子序列自然也是空的，长度 0。这一行、这一列就是整张表的边界起点。把 X = "ABCD"、Y = "ACBD" 的完整 dp 表画出来（第 0 行、第 0 列是初始化的边界）：
| A | C | B | D | ||
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 1 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 2 | 2 | 2 |
| D | 0 | 1 | 2 | 2 | 3 |
dp[i-1][j-1]+1 的位置，比如 X 的第 4 个字符 D 和 Y 的第 4 个字符 D 匹配，dp[4][4] = dp[3][3] + 1 = 2 + 1 = 3（右下角高亮格）。右下角 dp[4][4] = 3 就是最终答案：X、Y 的最长公共子序列长度是 3（对应 "ABD"）。其余没有高亮的格子，都是"两个字符不匹配"，取上边和左边中较大的那个抄下来。| 1 | string X, Y; // 下标从 0 开始，长度分别是 X.size()、Y.size() |
| 2 | int dp[1005][1005]; // dp[i][j]：X 前 i 个字符、Y 前 j 个字符的 LCS 长度 |
| 3 | |
| 4 | int LCS() |
| 5 | { |
| 6 | int n = X.size(), m = Y.size(); // dp[0][*] 和 dp[*][0] 全局数组默认已经是 0，无需手动初始化 |
| 7 | for (int i = 1; i <= n; i++) // 行、列都从 1 开始，方便用 i-1、j-1 对应字符串下标 0 |
| 8 | { |
| 9 | for (int j = 1; j <= m; j++) |
| 10 | { |
| 11 | if (X[i-1] == Y[j-1]) // X 的第 i 个字符是 X[i-1]（下标从 0 开始） |
| 12 | dp[i][j] = dp[i-1][j-1] + 1; |
| 13 | else |
| 14 | dp[i][j] = max(dp[i-1][j], dp[i][j-1]); |
| 15 | } |
| 16 | } |
| 17 | return dp[n][m]; // 两个字符串"全部用上"的答案，就在表的右下角 |
| 18 | } |
i、j 从 1 开始遍历到 n、m，是为了让 dp[0][*]、dp[*][0] 这一整行、一整列专门留给"空字符串"的边界情况（全局数组默认初始化为 0，正好符合"空字符串的 LCS 长度是 0"）。写 X[i-1] 而不是 X[i]，是因为字符串本身下标从 0 开始，而 dp 表的第 i 行对应的是"前 i 个字符"，第 i 个字符在字符串里的下标正是 i-1。这个"表下标从 1 开始、字符串下标减 1"的写法在字符串 DP 里很常见，需要多写几次才能熟练。回顾一下 LIS 和 LCS 各自对应的四要素：
| 要素 | LIS | LCS |
|---|---|---|
| 状态定义 | dp[i]：以 a[i] 结尾的最长上升子序列长度 | dp[i][j]：X 前 i 个、Y 前 j 个字符的 LCS 长度 |
| 转移方程 | dp[i] = max{dp[j]+1}（j<i 且 a[j]<a[i]） | 匹配则 +1，不匹配则取相邻两格较大值 |
| 初始化 | 每个 dp[i] 起始为 1 | dp[0][*]、dp[*][0] 全部为 0 |
| 填表顺序 | 下标从小到大 | 行从小到大，每行内列从小到大 |
a[i]，没法说清楚下一个数能不能接上去。必须是"以 a[i] 结尾"，转移时才能明确知道"接在谁后面"。最终答案不是 dp[n-1]，而是所有 dp[i] 里的最大值（最长的子序列不一定以最后一个数结尾）。a[j] < a[i]；如果题目允许"非递减"（可以有相等的数），转移条件要改成 a[j] <= a[i]。做题前一定要看清楚题目要求的是哪一种。dp[i][j] 依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]——都是"行更小或列更小"的格子，所以只要保证"从上到下、每行从左到右"填表，依赖的格子必然已经算好。如果把 X[i-1] 误写成 X[i]（或者忘记减 1），要么数组越界，要么对比的字符错位，算出来的答案会整体不对。