企业官网建设流程全解析

拿到一道动态规划的题，最痛苦的不是写代码，而是根本不知道从哪下手。状态怎么定义？为什么要这么转移？初始化为什么是 0 和 INF 而不是别的数？这些卡点我当年学的时候全都经历过。网上讲动态规划的文章不少，但大多要么堆概念，要么直接上题解，看完还是一头雾水。我写这篇的思路很明确：把动态规划从“看到题→想出状态→推出方程→写出 C++ 代码”这条链路完整走一遍，给你一套能直接套用的思维模板，再配合代码模板，让你以后再见到这类题，心里有个清晰的底。

这篇文章适合正在准备算法面试的开发者、参加 OJ/竞赛的学生，也适合自学数据结构与算法、卡在动态规划这道坎上的朋友。我会尽量用大白话把原理讲透，再用 C++ 把模板写出来，你拿过去就能用。

1. 先分清能做的和不能做的题型：DP 的识别信号与排除法

很多人一看到“求最值”“求方案数”就条件反射觉得是 DP，结果做半天发现根本推不出状态转移。这里有一个非常关键的认知误区：动态规划不是所有最优问题都能解，它的成立有严格前提。

1.1 动态规划成立的两个硬性前提

第一个前提叫最优子结构。大白话就是：整个问题的最优解，可以由子问题的最优解拼出来。这就像期末复习，你打算在三天内让总分最高，如果每天只能复习一科，那最后一天选哪科，取决于前两天复习完剩下的科目后，哪科提分空间最大。整体最优由局部最优递推出来，这就叫最优子结构。

第二个前提叫重叠子问题。如果每个子问题都是全新的，答案之间没有任何复用价值，那 DP 就没意义。比如归并排序，每次划分出来的区间都不一样，子问题几乎不重叠，用 DP 表去存反而浪费内存。实际上动态规划能比暴力快，核心就在于“把已经算过的结果存下来重复使用”。

这两个前提在题目里的典型表现是：题目明确要求“最大/最小/方案总数”，而且你在草稿纸上从最后一步往前推时，会发现“前 N-1 步的某类结果”被反复用到。

1.2 识别 DP 题的几个信号，以及什么时候要主动放弃

我刷题的时候会先问自己三个问题，能快速排除掉一批“伪 DP”题：

• 这个决策是不是只依赖前一个状态？如果是，而且不形成环，大概率是 DP。
• 每一步的选择会不会受更早步骤的“后效性”影响？比如状态里只保留当前阶段的某个值就够，不需要回溯前两步完整路径，这就是无后效性。像求最短路里的“路径具体经过哪些点”就带后效性，不能用简单 DP 硬套。
• 直接搜会不会爆炸？如果暴力枚举是 2^n 或者 n! 级别，而题目数据范围在 10^5 左右，基本可以确定要用 DP 或者贪心优化。

有一个反直觉的经验要分享下：如果题目里每一步的选择和之前的选择强相关，导致必须记录完整路径，那多半不是 DP 题，而是搜索/回溯题的范畴。比如求“从起点到终点的所有路径”，虽然也是递推能算的，但真正输出路径时你需要额外维护前驱节点数组，这已经属于 DP 加路径还原的进阶技巧了。

1.3 把 DP 的题型地图先在脑子里建起来

我习惯把 DP 题分成几大族，见到题目先归个类，状态设计的思路会清晰很多：

这张表是帮我快速定“状态维度”的。如果你能做题时先在脑子里过一遍这个表，就不会出现“上来就不知道数组开几维”的尴尬了。

2. 状态定义和转移方程的诞生过程：从直觉到模板的关键一跃

很多教材一上来就甩状态定义，仿佛那是从天上掉下来的。实际上状态设计是有方法论的，我自己总结了一个思考链条，按照这个链条走，能搞定八成常规 DP 题。

2.1 状态设计的三步提问法

拿到题以后，不要先想“状态转移方程怎么写”，先做这几步：

1. 把题目要求的结果用一句话写下来。比如“最多能偷到的金额”“最长递增子序列的长度”“凑到 amount 的最少硬币数”。
2. 问自己：为了得到这个结果，我需要知道哪些阶段性的信息？这些“阶段性信息”就是状态的参数。比如打家劫舍里，关键在于“当前偷到第几家”，以及“上一家偷了没偷”。后者可以用一维数组存两种状态，也可以直接把“偷/不偷”编进第二维。
3. 让状态的维度尽量小。能一维就不二维，能二维就不三维。每多加一维，时间复杂度和空间复杂度都上一个大台阶。如果发现一维状态推不出来，再往二维想，这是很正常的过程。

2.2 “最后一步”思维：写转移方程的万能钥匙

状态定义清楚了，转移方程怎么出？我的习惯是：盯着当前状态，问自己——如果这是最终答案的最后一步，那么上一步有哪些可能？

用“打家劫舍”这个最经典的例子讲解。题目是：一排房子，不能偷相邻两家，问最大可偷金额。设 dp[i] 表示“偷前 i 间房子能得到的最大金额”，然后考虑第 i 间房子：

• 不偷第 i 间：那么前 i-1 间怎么偷都行，dp[i] = dp[i-1]。
• 偷第 i 间：那第 i-1 间绝对不能偷，收益是第 i 间的钱 nums[i] 加上前 i-2 间的最优结果，dp[i] = dp[i-2] + nums[i]。

两者取最大，就是答案。你看，整个过程根本没有“硬想”，只是把最后一步的所有可能性枚举出来，然后取最优。这个思路几乎能解决所有线性 DP。做最长递增子序列时也是同理：以 nums[i] 结尾作为最后一步，上一步是“所有值比 nums[i] 小的 nums[j]（j < i）”结尾的子序列。

2.3 初始化为什么不是 0 就是 INF：边界条件的本质

初始化是新手最容易崩的地方。我当年就犯过把“最大”问题初始化为 0，导致全负数数组直接算出 0 的错。这里有个通行的判断逻辑：

• 如果求的是最大值，而且数值可能为负，dp 数组初始化为负无穷（比如 -1e9），保证任何从真实状态转移来的结果都能覆盖初值。
• 如果求的是最小值，初始化为正无穷（1e9 或 0x3f3f3f3f）。
• 如果求的是方案数，边界状态初始化为 1，其他为 0。
• 如果 dp[0] 有明确的物理意义（比如“前 0 个物品的最大价值自然是 0”），就直接赋值 0。

“0x3f3f3f3f”这个 C++ 里常用的正无穷常量有个好处：它大概等于 10 亿多一点，两个这样的数相加不会溢出 int，而真正的 INT_MAX 相加会溢出，所以写 INF = 0x3f3f3f3f 比用 INT_MAX 更安全。

2.4 计算顺序：为什么大多数是正着循环，区间 DP 却要按长度来

状态定义好了，方程也有了，还有一个容易被忽略的点：计算顺序必须保证当前状态依赖的子状态已经算完。线性 DP 一般从前往后循环就行，因为 dp[i] 依赖的一定是 dp[i-1]、dp[i-2] 这类“更小下标”的状态，正序天然满足依赖。

但区间 DP 就不一样了。比如 dp[i][j] 表示合并第 i 堆到第 j 堆石子的最小代价，它的转移依赖于 dp[i][k] 和 dp[k+1][j]，其中 k 在 i 和 j 之间。如果你按 i 从小到大循环，会出现“dp[i][j] 还没算，但后面某个大区间已经想用它”的情况。所以区间 DP 的惯用写法是外层枚举区间长度 len，内层枚举左端点 i，然后计算右端点 j = i + len - 1。这样所有短区间都先算完，长区间直接取用，不会出现依赖未完成的状态。

3. 一套 C++ 模板框架走天下：线性、背包与区间 DP 的统一写法

状态设计和转移方程这关过了，代码其实非常机械。我把自己常用的模板整理如下，你可以直接背下来，再根据题目微调。

3.1 线性 DP 模板：一维与二维的基础写法

一维线性 DP 最典型的骨架：

#include <bits/stdc++.h> using namespace std; // 以打家劫舍为例 int rob(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; if (n == 1) return nums[0]; vector<int> dp(n, 0); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i < n; i++) { dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[n - 1]; }

这里几个细节值得注意：dp[1] 为什么是 max(nums[0], nums[1])？因为前两个房子不能同时偷，所以最优解只能二选一。这种“边界前两三个状态需要单独赋值”的情况在 DP 题里非常常见，千万别在循环里从 i=0 开始直接套转移方程，会越界或者语义错误。

二维线性 DP 的模板以“最长公共子序列”为例，dp[i][j] 表示 A 的前 i 个字符和 B 的前 j 个字符的最长公共子序列长度：

int longestCommonSubsequence(string a, string b) { int n = a.size(), m = b.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 (a[i - 1] == b[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]; }

二维 DP 我习惯把 i 和 j 从 1 开始遍历，下标 0 那一整行和整列留作边界，这样能省去大量if (i > 0 && j > 0)的判断，代码干净很多。

3.2 背包问题模板：01 背包与完全背包的循环方向差异

背包问题是 DP 里最需要“背模板”的题型之一，但它背后的道理挺简单。

01 背包：每个物品只能选一次。设 dp[j] 表示容量为 j 的背包能装下的最大价值。

int knapsack01(vector<int>& weight, vector<int>& value, int capacity) { int n = weight.size(); vector<int> dp(capacity + 1, 0); for (int i = 0; i < n; i++) { // 注意倒序遍历容量 for (int j = capacity; j >= weight[i]; j--) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } return dp[capacity]; }

为什么容量要倒序遍历？因为如果正序遍历，dp[j - weight[i]] 可能已经在本轮 i 更新过了，那就会变成“同一件物品被装多次”，恰好是完全背包想要的效果。所以 01 背包倒序、完全背包正序，这个区别是很多面试官喜欢问的点，其实原理就这么朴素。

完全背包模板只需要把上面内层循环改成正序：

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

3.3 区间 DP 模板：按长度枚举是灵魂

以石子合并为例，dp[i][j] 表示把第 i 堆到第 j 堆石子合并成一堆的最小代价：

int mergeStones(vector<int>& stones) { int n = stones.size(); if (n == 0) return 0; vector<int> prefix(n + 1, 0); for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + stones[i - 1]; } vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0)); // len 表示区间长度，从 2 开始（长度为 1 时不需合并，代价为 0） for (int len = 2; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; dp[i][j] = INT_MAX; for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefix[j] - prefix[i - 1]); } } } return dp[1][n]; }

区间 DP 的核心就一句话：大区间由两个小区间拼起来，代价是合并两堆的体力（这里用前缀和快速求出区间和）。前缀和数组必须提前预处理，否则每次计算区间和都要 O(n)，整体复杂度直接上一个量级。

3.4 树形 DP 模板：父子状态的递归转移

树形 DP 通常配合 DFS 后序遍历实现。经典例子“打家劫舍 III”：二叉树结构，不能同时偷父子节点，求最大金额。

struct TreeNode { int val; TreeNode *left, *right; }; // 返回 [不偷当前节点最大收益, 偷当前节点最大收益] pair<int, int> dfs(TreeNode* root) { if (!root) return {0, 0}; auto left = dfs(root->left); auto right = dfs(root->right); int notRob = max(left.first, left.second) + max(right.first, right.second); int rob = root->val + left.first + right.first; return {notRob, rob}; } int rob(TreeNode* root) { auto res = dfs(root); return max(res.first, res.second); }

这个模板的精髓在于每个节点返回两个状态值，父节点只要看子节点的两个值就能做决策，完全不需要额外的记忆化数组。树形 DP 写起来最像递归题，但本质上依然是“状态 + 转移”。

4. 空间优化：从二维数组到滚动数组再到原地覆盖

很多初学者会困惑：网上那些题解为什么 dp 是一维的？是不是做了不同的状态定义？其实大部分情况是空间优化后的结果。理解这个过程，对彻底吃透 DP 非常有帮助。

4.1 滚动数组：把 O(n^2) 压到 O(n)

先看一个最简单的场景。斐波那契数列的递推是 f(n) = f(n-1) + f(n-2)，理论上你可以开一个一维数组存下所有值，但如果只需要最后一个结果，那后边算出来的值直接把前面不用了的覆盖掉就行，这就是“滚动数组”的思想。

在二维 DP 里，如果第 i 行的状态只依赖第 i-1 行，完全不需要保留更早的行，那么数组可以从dp[n][m]压成dp[2][m]：

vector<vector<int>> dp(2, vector<int>(m + 1, 0)); for (int i = 1; i <= n; i++) { int cur = i % 2, prev = (i - 1) % 2; for (int j = 1; j <= m; j++) { // 使用 dp[prev][...] 计算 dp[cur][...] } }

用 i % 2 而不是写死 0 和 1，是为了让代码能泛化到任意多行的场景。这里的开销很小，但压缩效果非常显著。

4.2 背包问题为什么可以直接降成一维

再回到 01 背包的代码。二维写法是dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。你会发现第 i 行只由第 i-1 行推出，所以优化成一维后，dp[j]在更新前保存的其实是“上一轮 i-1 的 dp[j]”。如果正序遍历 j，dp[j-w[i]]可能已经被当前物品更新过，再拿去用，就相当于重复装入同一物品了。只有倒序遍历，dp[j-w[i]]才确保是上一轮的旧值，正好符合 01 背包“每个物品至多选一次”的语义。

这就是为什么很多人背了“01 背包倒序、完全背包正序”却总记反的原因——你只要理解了它在防止什么，就永远不会忘。

4.3 空间优化的边界检查：什么情况下不能强行降维

空间优化看起来很美，但有一个大坑：当转移不仅依赖上一行，还依赖更早的行时，一维滚动就直接崩了。比如某些状态定义里dp[i][j]依赖dp[i-2][j]，如果你只保留上一行，数据早就被覆盖掉了。这时候要么回到二维，要么用两个一维数组交替存储。

还有一个容易踩的坑：降到一维后，如果你想做“路径还原”，也就是不仅要最大价值，还要知道选了哪些物品，那么必须把完整的二维表存下来。因为一维数组覆盖了历史选项，还原时就拿不到足够信息了。我实际写题时经常遇到这种情况，所以会提醒自己：空间优化别上头，先保证功能正确，再考虑省内存。

5. 从暴力到记忆化再到递推：看清 DP 的本质

很多教程直接给你 DP 公式，导致你只会套模板，遇到灵活题就懵。其实动态规划不是凭空出现的，它是暴力搜索的“升级版”。理解这条进化链，能让你面对新题时心里更有底气。

5.1 暴力递归为什么会慢：以“凑零钱”为例

假设你有一堆不同面值的硬币，要凑出 amount 元，每种硬币可以用无限次，求最少硬币数。最直观的做法是递归：f(amount) = min(f(amount - coin) + 1)，对所有 coin 遍历。这样会生成一棵巨大的递归树，因为f(10)可能要分别算f(9)、f(8)、f(5)，而这些调用的子树又有大量重叠，重复计算量呈指数级爆炸。

5.2 记忆化搜索：加一个缓存就行

优化的第一步很简单：把已经算过的 f(x) 存下来，下次用到直接返回。

int dfs(vector<int>& coins, int amount, vector<int>& memo) { if (amount == 0) return 0; if (amount < 0) return -1; if (memo[amount] != 0) return memo[amount]; int res = INT_MAX; for (int coin : coins) { int sub = dfs(coins, amount - coin, memo); if (sub != -1) res = min(res, sub + 1); } memo[amount] = (res == INT_MAX ? -1 : res); return memo[amount]; }

记忆化搜索本质上已经是一种 DP，只不过它是“自顶向下”的递归形式。你觉得递归难理解时可以先写记忆化版本，跑对了以后再翻译成递推，这对新手非常友好。

5.3 从记忆化到双层循环递推

把递归改成递推后：

int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, 0x3f3f3f3f); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (i >= coin) { dp[i] = min(dp[i], dp[i - coin] + 1); } } } return dp[amount] == 0x3f3f3f3f ? -1 : dp[amount]; }

这个例子还能很直观地看出完全背包和线性 DP 的统一性：dp[i] 只依赖 i-coin 这个更小的状态，coin 是外层可枚举的“物品”，本质就是完全背包的一维正序写法。当你把各种类型的 DP 都还原为“从暴力到缓存到递推”这个过程后，会发现它们在底层是同一件事。

6. 实战排错：初始化、循环边界和整数溢出

最后分享一些我在实际写题中踩过、也帮别人定位过的坑。这些问题在 OJ 上报错往往不直观，但你只要掌握规律，一眼就能找到病根。

6.1 初始化错误：最大问题的初始值不是 0

我见过最多的错误是把求最大值的 dp 数组全部初始化为 0，然后对全负数数组照样跑出 0。比如求“最大子数组和”时，如果数组都是负数，正确结果是最大的那个负数，而不是 0。解决办法很简单：dp[0] 或答案变量直接初始化为 nums[0]，或者用负无穷初始化后再转移。

6.2 循环下标越界/边界状态缺失

写数组类 DP 时，最容易出问题的是i-1、i-2这类下标。比如打家劫舍里 dp[1] 不初始化就进循环，直接越界。我的习惯是写完后先人工跑一遍长度为 0、1、2 的极端样例，三个样例全过再提交，省得在 OJ 上反复试错。

6.3 整数溢出：INF 与加法顺序

在求值的 DP 里，dp[i][k] + dp[k+1][j] + cost三个数相加很容易溢出 int，尤其是当 dp 存的是极大值（0x3f3f3f3f）时，再加一个正数就直接变成奇怪的小负数。解决方案有两个：一是把 dp 的类型改成 long long；二是在相加前判断 dp[i][k] 或 dp[k+1][j] 是否已经等于 INF，如果是就跳过这个转移。我个人做题时偏向直接用 long long，省心，回头发草稿再优化精度也来得及。

6.4 状态设计不对导致“推出来是错的但不报错”

这类问题最隐蔽。程序不崩，样例全过，提交却 WA。最常见的场景是：无后效性被破坏了。举个例子，如果状态里只存“当前节点能跳多远”，但你转移时偷偷用了“上一次是从哪跳过来的”这个信息，那方程看着合理，实际却藏了一个隐形依赖，小数据没问题，数据一大就错。遇到这种情况，我建议回到 2.2 节的“最后一步”提问法，把所有可能性重新枚举一遍，多数时候能发现状态里缺了一维。

7. 训练路线：从零到竞赛/面试水平的节奏建议

动态规划光看不练等于白学。但盲目乱刷效率太低了，我建议按下面的路线阶梯式推进。

7.1 第一阶段：线性 DP 入门（1-2 周）

先刷爬楼梯、最大子数组和、打家劫舍、最长递增子序列、最长公共子序列。这个阶段的目标不是记住代码，而是练熟“最后一步推导”的思维。我强烈建议每道题自己先在纸上写出状态定义、转移方程和边界条件，再动手敲代码，写不出来也没关系，但要先想。

7.2 第二阶段：背包问题专项（1 周）

背包是面试和国际竞赛的高频考点，种类多但套路固定。先做 01 背包、完全背包，然后是多维费用背包、分组背包。务必自己推一遍“01 背包为什么倒序、完全背包为什么正序”，这个理解了，背包这一族几乎就拿下了。

7.3 第三阶段：区间 DP 与树形 DP（2 周）

区间 DP 刷石子合并、矩阵链乘、最长回文子序列；树形 DP 刷二叉树最大路径和、树的直径、打家劫舍 III。这个阶段你会发现，只要掌握了“按长度枚举区间”和“后序遍历 + 多状态返回”这两个套路，题目之间的差别真的不大。

7.4 第四阶段：进阶与综合（长期）

状态压缩 DP、数位 DP、概率 DP 都属于进阶内容。如果目标是算法竞赛，建议学状态压缩 DP 里最常见的 TSP 问题；如果目标是面试，可以先放一放，反而建议把前面几个 DP 类型的题目做到脑子里能立刻浮现出状态定义和转移方程的程度。

训练时我还有一个习惯：每做完一道题，在代码注释里写一行“这题的状态是什么、为什么这样定义、转移想表达什么”。过两周翻出来看时，这行注释比任何题解都管用，因为那是你当时的真实思考路径。

动态规划这个专题说到底是“带着逻辑地暴力”：把所有可能枚举出来，用缓存避免重复计算，再用状态把问题拆小。每个人都会经历“面对题目大脑空白”的阶段，这不是智商问题，只是还没建立起状态设计的直觉。按照这篇文章的思路反复练上两周，再回头看那些曾经把你卡住的题，你会发现自己已经能自然地问出“当前状态依赖哪些子状态”这种问题了。