企业官网建设流程全解析

做 LeetCode 刷题，很多同学都有一个共同体验：动态规划看题解时全懂，关上答案自己写，还是不知道 dp 数组怎么开、转移怎么写。更常见的做法是去背状态转移方程，结果 LeetCode 上一换题就废。这篇笔记想换一个顺序来写 DP：不背公式，而是从你本来就会的递归出发，一步步把递归改成记忆化搜索，再改成递推 DP。只要走完这三步，背包、LIS、LCS 这些经典题就不再是“玄学”，而是一套可以重复使用的思考方法。

先给一个明确判断：动态规划不是靠背转移方程学会的，它是把暴力递归中的重复计算缓存起来，再把递归改成填表。所以真正的入口不是 DP 公式，而是递归。读完这篇文章，你会拿走三样东西：一套“暴力递归 → 记忆化 → 递推 DP”的通用推导流程；背包、LIS、LCS 三类高频题的最小可运行代码；以及自己遇到新题时判断“该不该用 DP、状态怎么定义”的思考清单。

1. 动态规划到底在解决什么问题

很多教程一上来就甩定义：动态规划是“把原问题拆成若干子问题，保存子问题结果避免重复计算”。这个解释没有错，但大多数小白听完仍然不会做题，因为它缺少最关键的一步：你怎么知道哪些问题能拆？拆完之后状态怎么表示？

动态规划本质上是递归的优化。先用一个最简单的视角理解：

• 原问题可以拆成若干规模更小的子问题。
• 子问题和原问题结构相同，只是输入更小。
• 不同的拆分路径会大量碰到同一个子问题，造成重复计算。

第一点对应“最优子结构”，第三点对应“重叠子问题”。这两个词不需要背，你只要在写递归时看到了重复计算，就说明这道题有机会用 DP 优化。

另一个容易让新人迷惑的概念是“无后效性”。通俗地解释：当我们已经算出第 i 个子问题的答案后，后面更大的状态只需要直接使用这个结果，不需要关心这个结果是怎么选出来的。比如你算出到达第 10 级台阶的方法数是 dp[10]，之后算 dp[11] 时只需要 dp[10] 这个数字，不用再问“你是先迈了一步还是迈了两步才到第 10 级”。如果状态被定义成这样，就能写成 DP；如果当前结果还依赖此前完整选择路径，那说明状态设计有问题。

有了这个基础，我们再统一术语。动态规划里经常出现三个词：

• 状态：dp[i] 或 dp[i][j] 表示什么含义。
• 转移：当前状态由哪些更小的状态推导出来。
• 初始化：边界子问题的答案，也就是 dp 的起点。

动态规划还有两种实现方向，后面会反复用到：

这篇文章的核心观点很简单：自顶向下和自底向上的代码虽然长得不同，但它们推导同一个状态转移方程。你只要熟练地从暴力递归开始，自然能写出记忆化搜索，再把它翻译成递推 DP。下面用一个最经典的题走通这个流程。

2. 从递归到递推的最小闭环：先做爬楼梯

LeetCode 70 题“爬楼梯”是练习这个流程成本最低的题目，因为它的状态转移方程只有一个维度，没有数组选择和字符串比较的干扰。

题目描述很直接：你正在爬楼梯，每次可以爬 1 级或 2 级台阶，问爬到第 n 级台阶有多少种不同方法。

2.1 先写暴力递归

遇到这种题，先别想 dp 数组，只想一个问题：到达第 n 级台阶前，你最后一步做了什么？

只可能是两种情况：

• 从第 n-1 级跨 1 级上来。
• 从第 n-2 级跨 2 级上来。

所以，到达第 n 级的方法总数 = 到达第 n-1 级的方法数 + 到达第 n-2 级的方法数。这是典型的递归思想：把大问题缩小成两个更小的子问题。

接下来写出暴力递归：

#include <iostream> using namespace std; // 到达第 n 级台阶的方法数 int climbStairsRecursive(int n) { if (n <= 1) return 1; // 第 0 级和第 1 级都只有 1 种理解方式 return climbStairsRecursive(n - 1) + climbStairsRecursive(n - 2); } int main() { int n = 10; cout << climbStairsRecursive(n) << endl; return 0; }

这段代码在 n 较小时能算出答案，但 n=45 时已经非常慢了。原因是它把大量重复的子问题反复计算了一遍：算 f(10) 需要算 f(9) 和 f(8)，算 f(9) 又需要算 f(8) 和 f(7)。这里的 f(8) 在递归树里出现了很多次，每次出现都会重新执行整棵子树，这就是“重叠子问题”。

2.2 加一个 memo，变成记忆化递归

先画出递归树，你会发现大量相同节点。既然同一个 f(k) 算一次就够了，我们用一个数组存结果，下次再需要时直接返回，这就是记忆化搜索，也叫自顶向下 DP。

#include <iostream> #include <vector> using namespace std; int dfs(int n, vector<int>& memo) { if (n <= 1) return 1; if (memo[n] != -1) return memo[n]; // 已经算过，直接返回 memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo); return memo[n]; } int climbStairs(int n) { vector<int> memo(n + 1, -1); return dfs(n, memo); } int main() { int n = 10; cout << climbStairs(n) << endl; return 0; }

到这里，代码已经足够通过 LeetCode。相比暴力递归，它只是把中间结果存下来，时间复杂度从指数级降到了 O(n)。

2.3 改成自底向上的递推 DP

观察递归代码可以发现，递归从 n 一路向下问到边界，再逐层返回。既然栈会把结果返回给上层，我们不如直接从边界开始向上填表，避免递归本身的额外开销。

先定义 dp[i] 表示爬到第 i 级台阶的方法数，初始化 dp[0] = 1，dp[1] = 1，然后从 i=2 循环到 n：

#include <iostream> #include <vector> using namespace std; int climbStairs(int n) { if (n <= 1) return 1; vector<int> dp(n + 1, 0); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; ++i) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } int main() { int n = 10; cout << climbStairs(n) << endl; // 输出 89 return 0; }

运行这段代码，当 n=10 时输出 89，n=1 时输出 1。至此，你已经完成了一次完整的推导闭环：暴力递归 → 记忆化递归 → 递推 DP。后面所有动态规划题，思考顺序都应该是这样的。背下来的状态转移方程只是最终结果，而你真正需要学会的是“为什么状态能这样转移”的推导过程。

3. 01背包问题，其实就是“选还是不选”的递归

爬楼梯足够简单，但它只包含一维状态。真正让很多小白在 DP 上第一次受挫的，往往是 01背包问题。我们先不看“背包”这个名词包装，直接看它的递归本质。

问题描述：有 n 件物品，每件物品有重量 weight[i] 和价值 value[i]，背包容量是 capacity，问怎么选物品能让装入背包的总价值最大，且每件物品最多选一次。

这是一个典型的最优化问题。用递归去想时，你只需要站在某一件物品面前做一个决定：拿还是不拿。

3.1 从选择的角度写暴力递归

假设我们用一个函数 dfs(i, rest) 表示：从第 i 件物品开始往后考虑，背包还剩 rest 容量时，能获得的最大价值。那么对第 i 件物品，只有两种可能：

• 不拿它，结果等于 dfs(i + 1, rest)。
• 拿它，前提是 rest >= weight[i]，结果等于 dfs(i + 1, rest - weight[i]) + value[i]。

最后取这两种选择的最大值。这个思路完全不需要背任何背包公式，它就是一个“选与不选”的枚举。

#include <iostream> #include <vector> #include <algorithm> using namespace std; // 从 index 开始考虑，背包剩余容量为 rest int dfs(int index, int rest, const vector<int>& weight, const vector<int>& value) { if (index == (int)weight.size()) return 0; // 没有物品可选 int res = dfs(index + 1, rest, weight, value); // 不选当前物品 if (rest >= weight[index]) { // 能选才选 res = max(res, dfs(index + 1, rest - weight[index], weight, value) + value[index]); } return res; } int main() { vector<int> weight = {2, 1, 3, 2}; vector<int> value = {3, 2, 4, 2}; int capacity = 5; cout << dfs(0, capacity, weight, value) << endl; // 输出 7 return 0; }

示例数据中，最优选择是物品 2（重量 1 价值 2）、物品 3（重量 3 价值 4）、物品 4（重量 2 价值 2），总重量 6？这里容量是 5，选物品2+3+4 总重量是 1+3+2=6，超过容量 5，所以不是这个选择。正确最优选是物品 0（重量2 价值3）、物品1（重量1 价值2）、物品3（重量2 价值2），总重量5，总价值7。上面代码会输出 7。

3.2 看到重复子问题：加 memo 改成记忆化

在递归过程中，可能出现“不同选择路径最后都进入同一个 (index, rest) 状态”的情况。例如先不选第一件再选第二件，和先选第二件再遇到剩余容量相同，后续的决策空间完全相同。为了不重复计算，用二维 memo 记录答案：

#include <iostream> #include <vector> #include <algorithm> using namespace std; int dfs(int index, int rest, const vector<int>& weight, const vector<int>& value, vector<vector<int>>& memo) { if (index == (int)weight.size()) return 0; if (memo[index][rest] != -1) return memo[index][rest]; int res = dfs(index + 1, rest, weight, value, memo); if (rest >= weight[index]) { res = max(res, dfs(index + 1, rest - weight[index], weight, value, memo) + value[index]); } memo[index][rest] = res; return res; } int main() { vector<int> weight = {2, 1, 3, 2}; vector<int> value = {3, 2, 4, 2}; int capacity = 5; vector<vector<int>> memo(weight.size() + 1, vector<int>(capacity + 1, -1)); cout << dfs(0, capacity, weight, value, memo) << endl; // 7 return 0; }

3.3 自底向上填二维表

当你能写出记忆化递归，递推 DP 就只是把递归倒过来。观察递归函数，可变参数只有 index 和 rest，所以 dp 数组也应该是二维的。

定义 dp[i][c] 表示：考虑前 i 件物品，背包容量为 c 时能获得的最大价值。则转移公式为：

• 不选第 i 件：dp[i][c] = dp[i-1][c]。
• 选第 i 件：如果 c >= weight[i-1]，dp[i][c] = max(dp[i][c], dp[i-1][c-weight[i-1]] + value[i-1])。

注意代码中用到 weight[i-1]，因为数组下标从 0 开始，但 dp 的第 i 行代表前 i 件物品。这是新手最容易下标错位的地方。

#include <iostream> #include <vector> #include <algorithm> using namespace std; int knapsack01(const vector<int>& weight, const vector<int>& value, int capacity) { int n = weight.size(); vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0)); for (int i = 1; i <= n; ++i) { int w = weight[i - 1]; int v = value[i - 1]; for (int c = 0; c <= capacity; ++c) { dp[i][c] = dp[i - 1][c]; // 第 i 件物品不放入背包 if (c >= w) { dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v); } } } return dp[n][capacity]; } int main() { vector<int> weight = {2, 1, 3, 2}; vector<int> value = {3, 2, 4, 2}; int capacity = 5; cout << knapsack01(weight, value, capacity) << endl; // 输出 7 return 0; }

运行这段程序会输出 7，对应选择物品 1（重量 2 价值 3）、物品 2（重量 1 价值 2）、物品 4（重量 2 价值 2），总重量 5，总价值 7。

3.4 一维滚动数组：为什么要倒序更新

很多题解会把 01背包 压缩成一维数组：

vector<int> dp(capacity + 1, 0); for (int i = 0; i < n; ++i) { for (int c = capacity; c >= weight[i]; --c) { dp[c] = max(dp[c], dp[c - weight[i]] + value[i]); } }

这里真正容易踩坑的地方是：容量必须倒序循环。原因是 dp[c-weight[i]] 如果在本轮物品中被先更新了，就会导致同一件物品被重复选择，这不符合 01背包“每件最多选一次”的约束。倒序更新可以保证 dp[c-weight[i]] 仍然是上一轮循环的结果。

一维数组并不是初级学习者必须马上掌握的，但它能帮助你理解背包问题的本质：只有“选”和“不选”两种状态，而倒序更新是在防止同一个物品被重复拿。

4. 最长递增子序列 LIS：为什么 dp[i] 要定义成“以 i 结尾”

LeetCode 300 题求最长递增子序列 lengthOfLIS，它的难点是状态下定义很容易走偏。先区分一个概念：子数组是连续的，子序列可以不连续。例如 [10,9,2,5,3,7,101,18]，最长递增子序列是 [2,3,7,101] 或 [2,5,7,101]，长度是 4。

4.1 从递归视角定义状态

假设我们想求“以第 i 个元素结尾的最长递增子序列长度”，记为 f(i)。那么序列的倒数第二个元素应该在前面的某个位置 j，并且满足：

• j < i
• nums[j] < nums[i]

如果找到了这样的 j，那么以 nums[i] 结尾的递增子序列长度，至少是以 nums[j] 结尾的最长递增子序列长度再加 1。如果前面没有任何元素小于 nums[i]，那么以 nums[i] 结尾的递增子序列长度就是 1。

这个递归描述可以轻易写成递推：

dp[i] = 1 for j in [0, i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1)

为什么 dp[i] 要定义成“以 nums[i] 结尾”？因为递增子序列需要一个明确的“当前最后一个值”，才能判断后续能不能继续接。如果只定义成“前 i 个元素里的最长递增子序列长度”，你无法知道最后一个数是多少，也就无法继续比较大小，这就是最常见的最初状态设计错误。你要的答案是所有 dp[i] 中的最大值，而不是 dp[n-1]。

4.2 LIS 的完整可运行代码

#include <iostream> #include <vector> #include <algorithm> using namespace std; int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; vector<int> dp(n, 1); int ans = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } return ans; } int main() { vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18}; cout << lengthOfLIS(nums) << endl; // 输出 4 return 0; }

4.3 进阶提醒：还有 O(n log n) 的解法

LIS 还有一个常见优化：用贪心加二分维护“递增子序列的最小末尾元素”。它的做法是：遍历数组时，如果当前数比维护数组末尾大就追加；否则用 lower_bound 找到第一个不小于当前数的位置并替换掉。这个方法常常在面经中出现，但对于刚学 DP 的小白，建议先把 O(n^2) 的朴素递推吃透。你只要理解“dp[i] 以 i 结尾是为了支持后续比较”，就已经解决了这道题最重要的思维难点，二分优化是后面水到渠成的事情。

5. 最长公共子序列 LCS：二维 DP 的经典入门

LeetCode 1143 题求两个字符串的最长公共子序列长度。例如 text1 = "abcde"，text2 = "ace"，最长公共子序列是 "ace"，长度是 3。注意这里的子序列也不需要连续，只需要保持相对顺序一致。

5.1 二维状态的递归推导

两个字符串互相比较，只用一个下标很难表示进度，于是自然会想到用两个下标。定义 dp[i][j] 表示：text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。

比较两个串的末尾字符时有两种情况：

• 如果 text1[i-1] == text2[j-1]，这两个字符相等，它俩可以作为公共子序列的最后一个字符。长度至少是 dp[i-1][j-1] + 1。反证法理解：如果最优公共子序列不用这一对相等的末尾字符，那把它接到公共子序列末尾也不会破坏顺序，只会更长，所以最优解一定可以包含它。
• 如果 text1[i-1] != text2[j-1]，末尾字符不相等，那么当前公共子序列不可能同时以这两个字符结尾。它要么等于 text1 去掉末尾字符后的结果 dp[i-1][j]，要么等于 text2 去掉末尾字符后的结果 dp[i][j-1]，取两者最大值。

这个递推式不需要背，它是你比较“两个串当前末尾”时自然产生的逻辑分支。

5.2 LCS 的完整代码

#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int longestCommonSubsequence(string text1, string text2) { int n = text1.size(); int m = text2.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (text1[i - 1] == text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[n][m]; } int main() { string a = "abcde"; string b = "ace"; cout << longestCommonSubsequence(a, b) << endl; // 输出 3 return 0; }

当输入为 "abcde" 和 "ace" 时，运行结果输出 3。如果你在本地调试时把 i、j 从 1 开始循环，并且比较时使用 text1[i-1] 和 text2[j-1]，就不会出现越界问题。常见的错误是把字符比较写成 text1[i] 和 text2[j]，导致访问越界或漏掉首字符。

5.3 LCS 的延伸价值

LCS 不止是一道题，它是很多字符串 DP 的基础。例如编辑距离题目中，Word A 变成 Word B 的最少操作数，会用到和 LCS 类似的二维状态转移。如果你能把 LCS 的推导流程想清楚，后面学编辑距离会轻松很多。

6. 遇到新题，怎么判断它是不是动态规划

讲了几个经典模型之后，你很自然会问：考试或面试时拿到一道从没见过的题，怎么知道该用 DP？

我的判断标准是三个信号：

• 题目问的是“最大/最小/最长/最短/方案数”，而不是要求输出具体选择路径。
• 原问题可以拆成若干相同结构的子问题，且子问题之间重叠。
• 决策只影响当前状态和未来可选择的范围，但不影响已经被计算过的信息。

第一条最直观：求最长递增子序列、最长公共子序列、最小编辑距离、达到目标金额的最少硬币数，这类极值问题天然适合 DP。如果题目要求输出具体路径，通常需要额外记录选择前驱，但第一步判断仍然是 DP。

第二条可以用来做递归测试。你先尝试写一个暴力递归函数，看函数的参数里有没有反复出现的相同状态。如果有，就能用记忆化或递推优化。比如 01背包 的 dfs 参数是 index 和 rest，爬楼梯的递归参数就只是 n，LCS 的递归参数是 i 和 j。递归函数中会变化的参数，基本就是之后 dp 数组的维度。

第三条要重复一遍“无后效性”的含义：当你写出 dp[i] 时，它只作为数值参与后续转移，不需要知道内部是怎么选出来的。如果你发现自己需要“知道第 i 次选择之后还剩多少容量”或“当前子序列最后一个元素的值”，就把这些信息放进状态里。LIS 的“以 i 结尾”、背包的“剩余容量 rest”，都是在补充这种必要信息。

一个实用的操作步骤是：

做判断题时最忌讳的是“感觉像 DP 就硬套背包模板”。更好的策略是先把暴力递归写在草稿纸上，哪怕复杂度很差，也能帮你理解状态。状态想清楚了，DP 就是递归的缓存加顺序遍历。

7. 动态规划常见错误与排查思路

很多小白刷 DP 题时是在“背答案”，所以遇到 WA 或 TLE 很难自己定位问题。下面是几个高频错误，建议保存成自己的排查清单：

这里特别提醒：LIS 的答案不是 dp[n-1]，因为最长递增子序列不一定以数组最后一个元素结尾，需要在填表过程中不断取 max。类似的陷阱在“最大子数组和”里也出现过，这类泛化最优问题要单独维护全局答案。

8. 下一步练习路线：按模型而不是按题号堆积

掌握了“递归 → 记忆化 → 递推”这一套，接下来要做的不是一口气刷几十道题，而是把经典模型练到能凭直觉推导出来。下面是按模型划分的练习顺序，从今天讲的三类题开始：

第一梯队（1-2 天）：爬楼梯、斐波那契数、使用最小花费爬楼梯。这些题适合反复练“暴力递归 → 记忆化 → 递推”的三步转换，形成肌肉记忆。

第二梯队（3-5 天）：01背包 与它的变体。先做 416. 分割等和子集，因为它本质上是“从数组中选一些数，能否凑出总和的一半”，是一个 01背包 的判定版本。再做 322. 零钱兑换，注意这题是“每一种硬币可以用无限次”，属于完全背包，和一维 01背包 的遍历顺序正好相反。做这两道题时，重点观察“物品能用几次”如何影响循环方向。

第三梯队（1-2 天）：LIS 和 LCS。除了 LeetCode 300 和 1143，可以再做 674. 最长连续递增序列，这题能帮你区分“连续”和“不连续”的状态转移差异。之后再挑战 72. 编辑距离，你会看到二维 DP 的威力。

第四梯队（选做）：多维背包、分组背包等。当 01背包 和完全背包都比较熟练后，可以去看一下“分组背包至少选一个”“多维背包”这类进阶模型。它们不是全新的算法，而是给了 dp 数组更多维度，把背包问题的“选择模型”推广到真实约束中。从输入材料里的高频词看，这类变体在竞赛题和 LeetCode 周赛里都很常见，但你没必要一开始就啃。

建议每天只做一道 DP 题，做完后不看答案，在纸上用今天的方法重新推一遍。如果你能做到“不选：dp[i-1][c]；选：dp[i-1][c-w]+v”不是背出来的，而是从递归函数现场翻译出来的，那 DP 就算入门了。

9. 最后想强调的：别把 DP 学成记忆题库

这篇文章真正想解决的问题不是“让你会做三道题”，而是纠正一个学习顺序：不要一上来就背状态转移方程。背包、LIS、LCS 这三个词往往被包装成“模板题”，但模板只能帮你应对原题，真正帮你应对变体的是你从递归推到 DP 的能力。

以后刷题时，建议给自己定一条规则：遇到动态规划题，先写一个返回答案的递归函数，哪怕它很慢。只要你写出了 dfs 的参数，状态定义就自然出来了；只要发现参数相同的调用会被重复计算，记忆化方案就出来了；只要把递归的执行顺序倒过来从边界开始填表，递推 DP 就出来了。这三步走完，代码的每一行都有了来源。

动态规划不是靠灵感的算法，它是一套有章可循的建模方法。下个阶段可以往区间 DP、树形 DP、状态压缩 DP 扩展，但所有延伸题型都建立在同一个基本功上：理解递归拆解、理解状态含义、理解重复子问题。把这几道经典题按“递归到 DP”的顺序再过一遍，比囫囵吞枣刷五十道题更值得。建议把本文收藏起来，当刷题卡住时回到这个推导流程，它会比记忆中的某个方程更可靠。