企业官网建设流程全解析

"HAO的DP"？先解释一下：这里的DP，是 Dynamic Programming，也就是动态规划，不是显示器上那个 DP（DisplayPort）接口，也不是"更新DP固件"的那个 DP。每次我发这种标题，都有人问是不是写错了。动态规划这东西，网上已经有一堆教程和题解，但大多数人的状态是这样的：题解看得懂，换一道题又不会；模板背得下来，一但题目数据范围变大、加上优化要求，立刻懵。这篇就是把我自己整理"HAO的DP"这套笔记时沉淀下来的东西梳理一遍——从最底层的状态设计，到线性DP、树形DP、数位DP，再到单调队列、四边形不等式、wqs二分这类优化手段，最后是调试DP代码时最容易坑人的细节。

适合谁看？准备笔试面试的、打算法竞赛的、自学DP卡了一周以上的，都可以。我会尽量用"为什么这样想能想通"的方式来讲，而不是贴一堆题解让你自己悟。重点不是我抄了什么模板，而是每个模板到底在解什么题、什么时候能用、什么时候不能硬套。

1. 写DP之前先把三件事想清楚：状态是什么，转移怎么写，循环怎么走

很多DP题做不出来，不是因为不懂状态压缩、不懂优化，而是连最基础的状态定义都没想明白就开始写转移方程，写一半发现推不出来，又回去改状态。实际上，一道DP题拿到手，你只需要依次回答三个问题：

1. 状态是什么？
2. 转移方程是什么？
3. 计算的顺序是什么？

1.1 本质是DAG上的路径规划

理解动态规划，最有用的一句话是：DP本质是在一张有向无环图（DAG）上做路径规划。

把每个状态当成一个节点，每次转移当成一条有向边。比如经典的斐波那契数列，状态就是"第i个数"这个节点；边就是f[i] = f[i-1] + f[i-2]这条从 i-1、i-2 指向 i 的边。因为每个节点只依赖它前面的节点，图上没有环，所以我们可以按照拓扑序把答案逐一算出来。

为什么强调"无环"？因为你一旦在图上绕了圈，就会鬼打墙，dp[i]要等dp[i]自己才能算出来，永远没有尽头。这也是"无后效性"的本质：当前状态一旦确定，之后的决策就再也不需要关心当前状态是怎么来的。有向无环保证了这一点。

我拿通勤举个生活化的例子。你早上从家出发去公司，路上要经过若干个地铁站，每个站可以换乘不同线路。你只关心"到达下一站的时间最早是多少"，而不需要关心"我前一条路是怎么走来的"。这就是无后效性。最优子结构则是"如果到达每一站的时间都是最早，那最终到达公司的组合起来也是最最早"。DP能成立，依赖的就是这两条性质。

1.2 状态设计的一个抓手：看数据和看约束

新手最迷茫的就是"状态怎么设计"。我的经验是，状态通常藏在两个地方：

• 题目给的数据维度。数组长度、剩余次数、当前走到的位置、当前选了哪些物品，这些都是天然的状态维度。
• 题目里的约束条件。比如"不能连续偷两家"，那你就得在状态里记录"上一家偷了没"；比如"最多交易K次"，那你就得把交易次数作为一个维度。

举个例子，打家劫舍这题，数组nums[i]表示第i家的金额，约束是"相邻两家不能同时偷"。如果不记录上一家的状态，你没法判断第i家能不能偷，所以状态至少得是dp[i][0/1]，表示偷到第i家，且第i家不偷/偷时的最大收益。这比dp[i]直接表示"偷到第i家的最大收益"要清晰得多，因为后者没法回答"第i-1家偷没偷"这个关键问题。

1.3 填表、刷表、记忆化搜索，到底用哪种

同样是DP，写法上有三种流派：填表法、刷表法、记忆化搜索。

• 填表法：考察当前状态dp[i]是哪些状态转移来的，主动查前面的格子把它填上。
• 刷表法：从当前状态dp[i]出发，去更新它能到达的所有未来的状态。
• 记忆化搜索：直接用递归函数写转移，加一个缓存数组。本质上和填表法等价，但是书写顺序符合直觉，而且天然解决拓扑序。

我的判断标准很简单：当转移顺序不好找、或者状态维度很多时，用记忆化搜索；当转移形式规整、可以套滚动数组优化时，用填表法。举个典型例子，数位DP几乎人人都用记忆化搜索，就是因为它的状态里有"是否贴住上界""是否有前导零"这种枚举顺序带来的标记，用递推写又丑又容易错，用递归加缓存写则一气呵成。后面第五部分我会给数位DP的完整模板。

也有人会说，记忆化搜索有递归栈开销，超大规模状态会不会慢？实际上在竞赛环境下，只要不是状态量上亿的极端情况，差距远没有你想象中大。很多时候，记忆化搜索被诟病慢，不是因为递归本身，而是因为你的状态设计里混入了大量用不到的转移。真到了需要极致性能时，自然会去写递推加滚动数组，但你一开始根本不必为了省那点常数去牺牲可读性。

2. 线性DP与状态机DP：笔试面试里最常出现的两类

线性DP是入门必做，状态转移只沿着某个一维方向推进。它本身不难，但很多经典算法本质都是线性DP，值得你停下来重新审视。

2.1 LIS从O(n²)到O(nlogn)：二分解法到底优化了什么

最长上升子序列（LIS）是线性DP的必修课。暴力 DP 写法很直白：

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; vector<int> dp(n, 1); // dp[i]: 以 a[i] 结尾的最长上升子序列长度 int ans = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (a[j] < a[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } cout << ans << "\n"; return 0; }

复杂度 O(n²)，n 到 1e5 就撑不住了。这时候需要"二分解法"。它维护的不是 dp 数组，而是一个单调递增的辅助数组tails，其中tails[k]表示长度为 k+1 的上升子序列中，结尾元素可以取到的最小值。这个"最小结尾"思路非常关键——同样是长度3的子序列，结尾是 5 的肯定比结尾是 9 的更有潜力，因为 9 后面能接上的数，5 一定也能接。于是每读到一个数x，就在 tails 里二分找到第一个大于等于 x 的位置，把它替换成 x。

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; vector<int> tails; // tails[k]: 长为 k+1 的上升子序列的最小结尾 for (int x : a) { auto it = lower_bound(tails.begin(), tails.end(), x); if (it == tails.end()) { tails.push_back(x); } else { *it = x; } } cout << tails.size() << "\n"; return 0; }

注意，tails.size()给出的是长度，不是那个具体的子序列。如果你需要还原整个子序列，得额外开一个数组记录每个数在 tails 里的位置，然后从后往前回溯。这个细节很多人忽略，面试官如果追问，你答不上来就露馅了。这个二分的写法，本质上就是把DP转移里"在所有 j<i 且 a[j]<a[i] 的状态中选择最优"这一步，利用单调性加速到了 O(logn)。

2.2 最大连续子段和：Kadane算法也是DP

最大连续子段和（Maximum Subarray）很多人直接当贪心背模板了，其实它就是最朴素的线性DP：

dp[i] = max(a[i], dp[i-1] + a[i])

dp[i]表示以a[i]结尾的连续子段的最大和。如果前面一堆数加起来还不如我自己大，那就果断从a[i]重新开始。这题提醒我们一件事：DP 不一定要写成表格的样子，Kadane算法在形式上只有一两个变量，但骨子里还是一个标准DP。面试的时候如果能主动说一句"这题本质是一个线性DP，当前状态只依赖前一个状态"，会比直接甩代码给面试官印象深刻得多。

2.3 状态机DP：股票买卖和打家劫舍的统一写法

状态机DP是线性DP的进阶，特征是状态本身就代表"目前处于什么情况"。最典型的例子是买卖股票系列的"最多完成一笔交易"：

vector<vector<int>> dp(n, vector<int>(2, 0)); // dp[i][0]: 第 i 天结束，手里没有股票的最大收益 // dp[i][1]: 第 i 天结束，手里持有一支股票的最大收益 dp[0][1] = -prices[0]; for (int i = 1; i < n; ++i) { dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]); // 卖出或在观望 dp[i][1] = max(dp[i-1][1], -prices[i]); // 一直持有，或今天买入 }

为什么买入时的收益是-prices[i]？因为你只能交易一次，买入那一刻的收益就是负的股价，不能再叠加之前的什么收益。这就是"状态机"的约束所在。

打家劫舍大同小异，状态就是"上一家抢没抢"。其实这种状态机DP可以用滚动数组压掉一维，每次只需要保留上一天的几个状态变量。题目一旦出现"最多完成K笔交易"这种限制，只需把状态改成dp[i][k][0/1]，这就同时考察了状态设计里"增加约束维度"的能力。

到这里你会发现，线性DP的题虽然变化多，但解法骨架是固定的：搞清楚状态维度，想明白当前状态可以从哪些前置状态来，再确定遍历顺序。真正容易翻车的反而是后面的树形DP和优化算法。

3. 树形DP和树上背包：能玩明白DFS，DP就成功了一半

树形DP，顾名思义，是在树上做DP。树的天然递归结构，几乎意味着你都要依赖DFS来遍历。听到"树形DP模板"，很多人的第一反应是背代码，但我建议先理解一个底层逻辑：树的子树天然把问题分解成了若干子问题，所以自底向上的回溯过程，就是填表过程。

3.1 基本套路：先递归子树，再回溯更新父节点

最经典的入门题是"没有上司的舞会"或者叫"树上最大权独立集"：每个节点有一个权重，选了一个节点就不能选它的直接子节点，问能选到的最大权重和。

#include <bits/stdc++.h> using namespace std; const int N = 200005; vector<int> g[N]; long long dp[N][2]; int w[N]; void dfs(int u, int fa) { // 初始化：选 u 的收益是 w[u]，不选 u 的收益先当 0 dp[u][0] = 0; dp[u][1] = w[u]; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); // 回溯时利用子树结果更新当前节点 dp[u][0] += max(dp[v][0], dp[v][1]); // 我不选，孩子可以选也可以不选 dp[u][1] += dp[v][0]; // 我选，孩子只能不选 } } int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> w[i]; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); cout << max(dp[1][0], dp[1][1]) << "\n"; return 0; }

这里的核心是：父节点状态的计算，必须等到所有孩子节点都算完。DFS 天然保证了这一点——先递归深入，再在函数返回后进行状态合并。很多树形DP做错，是因为在进入孩子节点之前就去更新父节点状态，顺序反了，后面的孩子还没算完，父节点已经被污染了。

3.2 换根DP：一锤子DFS算不出来的问题，就做两次

有些树上DP问题，要求你对每一个节点都计算答案。比如"树上每个点到其他所有点的距离之和"。如果你对每个点都做一次DFS然后求距离和，复杂度是 O(n²)，n 稍微一大就爆炸。换根DP就是为了把这类问题压成 O(n)。

思路是两轮DFS：

1. 第一轮，随便选个根（比如节点1），DFS一遍，算出一个基准答案——比如以1为根时，每个节点的子树大小，以及所有点到1的距离之和。
2. 第二轮，利用父节点的答案推导子节点的答案。假设我们已知所有节点到 u 的距离和，现在要把根从 u 换到儿子 v。那么 v 的"子树"里的节点每个都离 v 近了 1，其他节点每个都远了 1。如果令sz[v]为 v 子树的大小，n - sz[v]就是其余节点数，那么：

ans[v] = ans[u] - sz[v] + (n - sz[v])

这公式一眼看穿，比背模板强得多。换根DP最容易错的地方，是第二轮需要时刻记得，此时dp数组存的已经不是"以某个点为根的子树状态"了，而是"以全树为根、当前点作为新的根时的全局答案"。概念不清晰，公式推着推着就乱了。

3.3 树上背包：容量循环别写反

树上背包是从树形DP延伸出来的，典型题是"选课"：每门课可能有先修课，选一门课之前必须选它的先修课，给定总选课门数限制，问最大总学分。

状态定义为dp[u][j]：在以 u 为根的子树里，恰好选了 j 门课，能获得的最大学分。对于当前节点 u，你可以决定选几个孩子里的课程。合并孩子 v 时的转移：

for (int j = size[u]; j >= 1; --j) { // 枚举当前已经合并的课程数量，倒序 for (int k = 1; k <= size[v]; ++k) { // 枚举从孩子 v 里选 k 门课 if (j - k >= 0) { dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]); } } }

两个易错点。第一，合并孩子的循环要倒序枚举j，不然当前孩子 v 的dp[v][k]可能会被外层循环的新值覆盖，导致同一棵子树被选多次。第二，循环上界记得用当前子树的实际大小size[u]、size[v]而不是直接用总容量m，否则会白白引入无数无效转移，复杂度也会退化成 O(nm²)。

4. 优化三板斧：单调队列、四边形不等式、二分，到底分别解决什么问题

DP 题做到一定量，你就会碰到"状态定义很简单，但转移复杂度爆炸"的题目。这时候需要优化。"单调队列优化DP""四边形不等式优化DP""二分答案/带权二分"是三类最常见的优化思路。它们的共同点是：不是改变状态定义，而是让每次找最优转移的速度更快。

4.1 单调队列优化：当转移来源像一个滑动窗口时

单调队列优化的适用场景非常具体：状态转移方程形如

dp[i] = min/max ( dp[j] + cost(i, j) )

且j的取值范围是一个连续区间[i - k, i - 1]，这个区间随着 i 的增大单调向右滑动。最经典的例子是"滑动窗口取最大值"。

单调队列里保存的是下标，不是值。队列里边的人，下标递增，对应的 dp 值也保持单调。每次转移之前，做三件事：

1. 把队头中已经滑出窗口的过期下标弹出；
2. 把当前新下标按"值更优"的原则从队尾挤掉；
3. 取队头作为最优转移来源。

我见过太多人栽在第 1 步上。顺序必须是先弹过期下标，再维护单调性，然后取队头。很多人先取队头，发现取出来的已经过期，然后又忘记回去检查下一个，直接导致答案错误。标准模板长这样：

deque<int> q; // 存下标 for (int i = 1; i <= n; ++i) { while (!q.empty() && q.front() < i - k) q.pop_front(); // 1. 弹出过期下标 // 这时队头就是合法区间内的最优转移来源 if (!q.empty()) dp[i] = dp[q.front()] + w[i]; while (!q.empty() && dp[q.back()] <= dp[i]) q.pop_back(); // 2. 维护单调性 q.push_back(i); // 3. 入队 }

这个模板你要是能背下来，并且真正理解队头弹出、队尾维护的顺序，基本就到手了。要注意的是，不是所有看起来像滑动窗口的题都能用单调队列。要求窗口中每个元素的"参与方式"是统一的，如果 cost 里还混着和当前 i 有关的二次项，那可能是斜率优化而非单调队列的适用范围。

4.2 四边形不等式与决策单调性：区间DP的降维魔法

区间DP的经典转移长这样：

dp[i][j] = min( dp[i][k] + dp[k+1][j] + cost(i, j) ) // i <= k < j

这个转移本身就要枚举 k，加上区间枚举，整体 O(n³)。n 到 2000 以上就承受不住了。这时候四边形不等式如果能用，就可以大砍一刀。

四边形不等式的含义，用通俗的话说：当区间变宽时，最优决策点不会往左退，只会往右走。体现在代码上：

• 我们开一个数组opt[i][j]记录 dp[i][j] 取得最优解时 k 的位置；
• 如果满足四边形不等式，会有opt[i][j-1] <= opt[i][j] <= opt[i+1][j]；
• 于是枚举 k 时，不需要从 i 到 j-1 全扫，只需要在[opt[i][j-1], opt[i+1][j]]里扫。

这就是为什么四边形不等式优化也叫"决策单调性优化"。用它之前，你得确认代价函数cost(i, j)满足四边形不等式和单调性，最经典的判定是区间DP里的"石子合并"一类问题，合并代价满足四边形不等式。实操中我一般会先写一个朴素版，用小数据验证opt数组是不是单调的，确认单调了再上优化——这样能避免背错条件白忙活。

另外，如果最优决策点是单调的，还有一种配套优化叫分治法。它适合的状态定义更复杂、不适合存opt二维数组的场景，思路是把需要计算的状态按下标区间分治，每次递归只需要尝试一半以内的决策点。分治法和决策单调性通常是绑定出现的，遇到"dp[i][j] = min(dp[i-1][k] + cost(k+1, j))"这类长得很像的两段式DP，分治优化往往是最优选。

4.3 wqs二分（带权二分）：解决"恰好选 K 个"的最优化问题

二分和DP的关系不只出现在LIS那种"在有序数组里找插入位置"的场景。有很多DP题，答案是"恰好选 K 个时的最优值"，直接作为一个维度放进状态里会太大，但暴力枚举数量又不行。

如果这个问题满足一个性质：答案关于数量 K 的图像是一个凸函数（或凹函数），那么你可以给每次选择增加一个"惩罚项" price。这样原问题变成一个不限制数量的新问题，每次只需通过DP求出在附加了 price 之后的最优方案和最优数量，然后二分 price，让最优数量逼近 K。

打个比方：你本来要恰好买10个苹果，现在商家说买一个苹果额外收x元，你重新算"怎么买最划算"，如果最优购买数是8，说明x罚得太重，应该减小x；如果最优购买数是15，说明罚得不够，应该增大x。二分x，直到最优购买数是10。最终答案就是"附加x时DP算出的最优值减去 K*x"。

这套技巧在竞赛里叫wqs二分或带权二分。最容易踩的坑是，题目答案函数并不真的是凸函数，或者你在二分边界上差一个单位。我建议正式提交前，先在小数据上暴力验证几个 K 对应的最优值，确认凸性，再上wqs二分。

5. 数位DP与动态DP：当你觉得"普通DP不够用"的时候

线性DP和树形DP解决的是"状态结构清晰、转移方式固定"的题目。但有两类DP，它们的难点不在转移优化，而在状态设计本身：数位DP和动态DP。

5.1 数位DP：记忆化搜索比递推好写一百倍

数位DP解决的是"统计一个区间内满足某种数字性质的数的个数"这类问题。例如统计[L, R]中有多少个数不包含数字 4 和 7。直接枚举每个数再检查，R 一上来就超时；数位DP按"每一位"来做DP。

核心状态是pos（当前枚举到哪一位）、limit（前面是否已经和上界完全相等，能否自由填数字）、以及题目要求的性质状态。用记忆化搜索写十分直接：

long long dfs(int pos, bool limit, bool lead, ...) { if (pos < 0) return 1; // 所有位都填完了，且没违反约束 if (!limit && !lead && memo[pos] != -1) return memo[pos]; int up = limit ? digit[pos] : 9; long long res = 0; for (int d = 0; d <= up; ++d) { if (d == 4 || d == 7) continue; // 不能包含 4 和 7 res += dfs(pos - 1, limit && d == up, lead && d == 0, ...); } if (!limit && !lead) memo[pos] = res; return res; }

两个关键点。第一，memo只在!limit && !lead时才缓存。因为一旦limit和lead为真，这组状态是特殊的、和其他数位组合并不等价，不能通用缓存；如果你强行缓存，会导致上下界不同的情况互相污染，答案错得莫名其妙。第二，dfs的答案是从低位到高位递归的，初始化调用时，limit=true, lead=true。数位DP的区间[L,R]答案，分别算cal(R)-cal(L-1)即可。

5.2 动态DP：把转移过程喂给线段树

动态DP（Dynamic DP，简称DDP）听起来高大上，但核心思想一句话：把DP的每一步转移写成矩阵乘法，然后用线段树等数据结构对"连续转移"做批处理。

为什么可以这么搞？因为矩阵乘法虽然不满足交换律，但满足结合律。所以如果一次DP转移能被写成"左乘一个矩阵"，那么连续若干步的DP就等价于"左乘这些矩阵的乘积"。于是，当你需要支持"修改某一个位置的权值，并快速重算整条链上的DP答案"时，线段树就能在 O(logn) 时间更新矩阵乘积。

树上的动态DP，比如"动态维护树上最大权独立集，支持单点修改权值"，需要用到树链剖分把树变成若干条链，每条链内维护转移矩阵。这块我坦白说，学起来难度陡增，适合在基础知识已经非常扎实之后再啃。如果你刚把普通树形DP弄明白，建议先把常规树形DP的代码敲熟，再来碰DDP，否则很容易被矩阵化和树剖两头夹击。

5.3 学习路径建议：别让优化技巧成为空中楼阁

我见过不少朋友，一上来就学动态DP，结果连普通树上背包都写错。我的个人建议是，学习DP的路线应该是：

• 先把线性DP、区间DP、树形DP的朴素解法写熟；
• 再补状态机、数位DP这类"状态定义有花样"的模型；
• 然后才轮到单调队列、四边形不等式、wqs二分这些优化；
• 最后再去碰动态DP这类"模型组合"的高级玩法。

每层都配合"能指出这道题考的是哪个模型、哪种优化"的自我训练。没有前面几层地基，学再炫的优化也是一碰就碎。

6. HAO自己踩过的DP坑：七个看起来小、实际上能卡一整天的错误

最后这部分，是纯实战经验。DP题错得最多的往往不是思路，而是实现细节。下面七个坑，我全都在板子上踩过，每一个都至少卡了我两个小时以上。

6.1 循环顺序：背包为什么必须倒着循环容量

滚动数组优化01背包时，容量循环要倒序。原因是dp[j] = max(dp[j], dp[j - w[i]] + v[i])，如果正序，dp[j - w[i]]可能已经在当前这一轮被更新过，相当于同一个物品被使用了多次。倒序则保证每个物品最多被选一次。我建议你想清楚这个过程，而不是只记"倒序"。如果你做的是完全背包，那才需要正序。这个“正倒序之争”背后是物品可重用的次数，理解了就不会出死记硬背导致的笑话。

6.2 INF取值：不是越大约好

很多人初始化dp用0x7fffffff，但转移里有加法，两个大的INF一加就溢出变成负值，然后 min 的结果完全错误。我在写"矩阵连乘"这类区间DP时，就吃过这个亏。推荐用0x3f3f3f3f，约等于 10^9，两个相加也不会爆 int，而且 memset 对 0x3f3f3f3f 有快速的字节填充方式。如果是 long long 的DP，用0x3f3f3f3f3f3f3f3f。

6.3 long long 和中间溢出：乘法比结果更早爆炸

计数类DP里，即便答案保证在 int 范围，中间状态也可能经过dp[u][j] + dp[u][j-k] * dp[v][k]这种组合。乘法过程一旦溢出，后面再怎么取模都没用了。判断是否用long long，不要只看题目说最终答案取模，要看中间乘积会不会超过 2^31。这个习惯，我是在LeetCode和牛客上百度和优化题里反复栽跟头之后才彻底养成。

6.4 记忆化搜索的缓存冲突：0到底代表"可行方案"还是"没有方案"

数位DP或计数DP里记忆化数组初始化成 -1 表示"还没算过"，这是为了防止"方案数恰好为0"被当成"没算过"而反复递归。我犯过的错误：初始化数组为 0，然后判断if (dp[...] != 0) return dp[...];结果合法方案数为0的路径永远没法缓存，同一个子问题被重复算几千次，直接超时。记住：要么初始化成 -1，要么开一个vis布尔数组单独标记。

6.5 单调队列优化：队头过期下标要先弹，再取最优

这个我在 4.1 里强调过，但值得再单独拉出来说一次：先弹队头过期下标，再取队头，再往队尾插新元素。三个操作顺序一旦错，单调队列守不住窗口边界，答案就会混入范围外的状态。新手最容易漏掉第一步，拿了个过期状态当最优解，调试半天还觉得是方程的问题。

6.6 树形DP的递归栈溢出：当n到20万时怎么办

树形DP如果直接递归，在链状树上深度达到 20 万，C++ 默认栈会爆掉。我的处理办法有几种：一是手动用stack模拟DFS，先序和后序分开处理；二是先把树递归改成非递归遍历，按进栈顺序记录一个操作序列，再逆序做状态合并。在比赛环境下，实在不行也可以换编译器参数，但我不建议依赖这个。对于面试场景，只要你能指出"递归在链状树上会栈溢出"并说出迭代解法思路，面试官往往就满意了。

6.7 边界初始化：dp[0][0]=1和dp[0][0]=0之间，隔了一场事故

计数类DP里，求"凑成总金额X有多少种方式"时，dp[0] = 1是条件反射。但在"从一堆数里选若干个数，使和恰好等于X"这类01背包计数题里，dp[0] = 1依然成立，然而很多人在循环里把dp[j] += dp[j - a[i]]的容量循环写成正序，导致同一个数被选了多次。计数DP的初始化和转移顺序，是最容易同时踩中"6.1"和"6.4"两个坑的地方。

老实说，我整理"HAO的DP"这套笔记的初衷，就是因为上述这些坑每个都让我痛过一次。把错误记录下来，比单纯记录正确模板更有价值。你自己刷DP题时，也可以照着这个思路，每做错一题，就补进一个"为什么会错"的条目。久而久之，你会形成一种直觉：看到题目先问状态有哪些维度，再看转移有没有优化空间，最后在写代码前，把循环顺序、INF、缓存初始化这些坑在脑子里提前过一遍。这样下来，DP题对你就不再是玄学，而是一套有章可循的工程实践了。