第一次刷这套基础DP1的时候我还在为“为什么动态规划能比深搜快这么多”而困惑。那时我写题基本靠脑补遇到“最优解”三个字就想把所有方案枚举一遍结果在第一道数字三角形上就吃了大亏。如果你也处于这个阶段那我真心建议把这份流传已久的“带你飞”系列专题从头到尾做一遍——它不教你背板子而是逼你从一个决策的角度去思考问题。这篇总结我想按“每种DP模型到底在练什么”的方式来复盘把状态定义、转移方程、初始化和最容易翻车的地方一次说透给正在刷专题十二的同学一份能直接照着走的参考。1. 这套基础DP题单到底在训练什么1.1 它训练的不是模板而是状态建模很多人以为基础DP就是记几个经典模型会写最长上升子序列、会写01背包就算入门。但真正做完这套题你会发现题目之间几乎没有一道是“换个数字重做一遍”每道题都需要你现场回答三个问题阶段是什么状态存什么上一个状态怎么转移过来以数字三角形为例暴力递归搜每条路径是指数级的但如果你把“从顶端走到某一个格子能得到的最大和”定义成状态那就只有 \(O(n^2)\) 个状态每个状态只依赖正上方和左上方两个状态。这个过程本质上是把“所有路径”折叠成了“所有位置”用重复子问题换掉了指数枚举。这套专题前期大量题目都在反复锤炼这件事先找重复的子问题再定义状态最后写出转移。1.2 题单的整体覆盖范围与刷题节奏基础DP1覆盖了线性DP、背包、区间DP、树形DP、状压DP和数位DP几乎是后续所有DP专题的基石。我刷的时候节奏是线性DP和背包花一周区间和树形再花一周状压和数位最后用几天慢慢啃。不推荐一口气刷完DP需要沉淀今天看懂的不如明天自己写出来的。提示这套题单里的题不少有“多组输入”读题时一定要先看输入格式否则很容易WA到怀疑人生。后面我会专门列一个易错清单。2. 线性DP把“最后一个决策”当作突破口2.1 数字三角形从递归到递推先学会边界处理数字三角形是经典中的经典。设 \(dp[i][j]\) 表示从顶端走到第 \(i\) 行第 \(j\) 列的最大路径和转移只需要考虑它从哪个方向来\[dp[i][j] a[i][j] \max(dp[i-1][j], \; dp[i-1][j-1])\]但如果从上往下推你需要一来就把第1行的值塞进dp还要小心 \(j1\) 时 \(j-1\) 越界。更省心的写法是自底向上从最后一行开始往上收敛for (int i n - 1; i 1; --i) { for (int j 1; j i; j) { dp[i][j] a[i][j] max(dp[i1][j], dp[i1][j1]); } } printf(%d\n, dp[1][1]);这样最底下那一行的dp值就是原值不用额外初始化。我一开始习惯在dp数组外圈多包一圈0但自底向上写反倒不容易出问题。这种“从结果往回倒推”的思路在后面很多题里都管用。2.2 最长上升子序列O(n log n) 的二分进阶LIS的基础写法是 \(dp[i]\) 表示以第 \(i\) 个元素结尾的最长上升子序列长度每次向前扫描 \(j i\) 找转移。这个思路一定要会但题单里有些题目 \(n\) 给到五位数甚至十万必须上二分优化维护一个数组 \(d\)\(d[k]\) 表示长度为 \(k\) 的上升子序列的最小末尾值。int len 0; for (int i 0; i n; i) { int pos lower_bound(d, d len, a[i]) - d; d[pos] a[i]; if (pos len) len; } printf(%d\n, len);这里有一个特别容易踩的坑题目要求“严格上升”时用lower_bound也就是找第一个不小于当前值的元素替换如果题目允许“非严格上升”也就是相等也算上升必须用upper_bound。我第一次做变种时就在这上面WA了三次后来才明白两个函数的本质区别是“允许重复”还是“不允许重复”。2.3 最长公共子序列二维状态如何压缩LCS的转移方程是\[ dp[i][j] \begin{cases} dp[i-1][j-1] 1, s[i] t[j] \\ max(dp[i-1][j], \; dp[i][j-1]), s[i] \neq t[j] \end{cases} \]\(dp[i][j]\) 表示 \(s\) 的前 \(i\) 个字符和 \(t\) 的前 \(j\) 个字符的最长公共子序列长度。二维数组 \(O(nm)\) 的空间在 \(n,m\) 到5000时就很吃紧好在这道题的状态只用上一行滚动数组就可以压成两个一维。不过我建议初学者先把二维完整写一遍确认转移逻辑没问题再改成滚动数组否则调试时很难定位错误。线性DP这一块还有个常见的最大子段和模型用 \(dp[i]\) 表示以第 \(i\) 个元素结尾的最大连续子段和转移就是 \(dp[i] max(a[i], \; dp[i-1] a[i])\)。它和LIS一样在后期很多题目里都是“零件级”的存在值得单独写熟练。3. 背包三变种容量、价值与枚举方向3.1 01背包为什么容量必须倒序枚举01背包的状态是 \(dp[j]\) 表示容量为 \(j\) 时能获得的最大价值转移方程\[dp[j] \max(dp[j], \; dp[j - w_i] v_i)\]关键点在于内层循环必须从大到小枚举容量for (int i 1; i n; i) for (int j V; j w[i]; --j) dp[j] max(dp[j], dp[j - w[i]] v[i]);如果正序枚举\(dp[j - w[i]]\) 可能已经在同一轮i更新过等于当前物品被用了多次变成了完全背包。这个对比特别能说明“DP转移顺序本身就是在表达决策顺序”很多题目表面是算法题本质是逻辑上的一次性约束。3.2 完全背包与多重背包的演化完全背包只是把容量循环改成从小到大for (int j w[i]; j V; j) dp[j] max(dp[j], dp[j - w[i]] v[i]);逻辑上也说得通同一种物品可以反复考虑正序枚举让后更新的状态能引用本轮的结果。多重背包则介于两者之间最常规的做法是二进制拆分。把数量 \(cnt\) 拆成 \(1, 2, 4, 8, ...\) 以及剩余部分每一块作为独立的01物品处理for (int k 1; k cnt; k 1) { int count min(k, cnt); for (int j V; j count * w; --j) dp[j] max(dp[j], dp[j - count * w] count * v); cnt - count; } if (cnt 0) { for (int j V; j cnt * w; --j) dp[j] max(dp[j], dp[j - cnt * w] cnt * v); }注意具体写法因题而异关键是拆完后每个块都要当成独立物品处理并且别漏掉最后剩余的部分。这一块我第一次写时没把剩余件数单独处理答案一直偏小。3.3 三种背包的对比类型枚举方向决策含义典型标志01背包容量倒序每件物品拿一次时间、数量有限制完全背包容量正序每件物品可以拿多次无限制取用多重背包二进制拆分后按01处理有限次但次数较大每件物品有最大数量背包题在基础DP1里占比不小但基本都是这三大类绕来绕去。你要是能把“为什么倒序/正序”讲清楚背包部分就算过关了。后面那些把物品维度换成“时间”“代价”的题翻译过来仍然是这套逻辑。4. 区间DP与树形DP从线性思维到结构思维4.1 区间DP为什么必须先枚举长度区间DP处理的是“在一个区间上合并、分割、配对”的问题状态一般写成 \(dp[l][r]\)表示区间 \([l,r]\) 的某种最优值。以石子合并为例转移表达式是\[ dp[l][r] \min_{k} (dp[l][k] dp[k1][r]) sum(l, r) \]如果你按左端点l、右端点r直接双重循环你会发现 \(dp[l][k]\) 可能还没算出来因为 \(k\) 离 \(l\) 近、区间长度小而你当前枚举的区间长度是很大的。正确顺序是先枚举区间长度len再枚举左端点l这样才能保证转移依赖的更小区间已经被算过for (int len 2; len n; len) for (int l 1; l len - 1 n; l) { int r l len - 1; dp[l][r] INF; for (int k l; k r; k) dp[l][r] min(dp[l][r], dp[l][k] dp[k1][r]); dp[l][r] sum[l][r]; }区间DP的边界往往也要单独处理\len1\) 时 \(dp[i][i]\) 通常为0或某个基础值不要放进主循环里统一算否则会覆盖初始值。4.2 括号匹配类问题状态里要记录“残缺程度”另一类典型的区间DP是括号配对比如“给一个括号序列最少插入多少个括号才能让它合法”。这里的 \(dp[l][r]\) 表示让区间 \([l,r]\) 合法所需的最小插入次数。转移分两种情况如果 \(s[l]\) 和 \(s[r]\) 恰好匹配可以继承 \(dp[l1][r-1]\)然后无论是否匹配都枚举一个分割点 \(k\)把区间拆成两半分别处理\[ dp[l][r] \min(dp[l][r], \; dp[l][k] dp[k1][r]) \]这类题和石子合并的区别在于“合并代价”不是前缀和而是两种不同的转移来源必须分类讨论清楚。我在做这类题时习惯先把所有区间初始化为极大值再单独把长度为1的区间初始化成对应代价最后再跑长度循环。4.3 树形DPDFS 后序返回才是标准姿势树形DP的入门题通常是树上最大独立集每个节点有权值选了父节点就不能选子节点问能选出的最大权值和。状态定义成 \(dp[u][0]\) 表示不选u时子树u的最大值\(dp[u][1]\) 表示选u时子树u的最大值void dfs(int u, int fa) { dp[u][0] 0; dp[u][1] val[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]; } }这个写法看起来很自然但“先递归再更新”的顺序是硬性要求你必须先算完子树才能把子节点的dp值用到父节点上也就是自底向上的后序遍历。很多Windows环境下的OJ栈比较小树的深度特别大时会爆栈如果递归栈溢出可以改成显式栈或者先处理出一条dfs序再反向循环。这个“反向拓扑”的技巧后面遇到树形依赖问题还会用到。5. 状压DP与数位DP入门时最难啃的两块硬骨头5.1 状压DP用二进制位表示集合状态状压DP的基础模型是给定 \(n\) 个点\(n\) 通常不超过20要求经过每个点并回到起点的最短路径或者访问某个点集的代价。状态定义成 \(dp[mask][i]\)表示已经访问过的点集为 \(mask\)当前停在点 \(i\) 时的最小代价。转移就是枚举下一个未访问的点 \(j\)\[ dp[mask \mid (1 j)][j] \min(dp[mask \mid (1 j)][j], \; dp[mask][i] cost[i][j]) \]写代码时要注意 \(mask\) 和 \(i\) 的合法性\(i\) 必须在mask里\(j\) 不能已经在mask里。复杂度是 \(O(n^2 \cdot 2^n)\)在 \(n20\) 时大约是四百万量级勉强可行。这类题我第一次做时老是把位运算笔算错后来干脆写了个小函数判断某个点在不在集合里或者在循环前先做个if (!(mask (1i))) continue;的过滤。5.2 数位DP记忆化搜索比递推更不容易出错数位DP通常求“区间内有多少个数满足某条件”最灵活的写法是记忆化搜索。状态一般是 \(pos\)当前处理到第几位、\(state\)题目相关状态、\(limit\)是否贴上界、\(lead\)前面是否全是前导零long long dfs(int pos, int state, bool limit, bool lead) { if (pos 0) return 1; // 根据题目条件调整返回值 if (!limit !lead memo[pos][state] ! -1) return memo[pos][state]; int up limit ? digit[pos] : 9; long long res 0; for (int i 0; i up; i) { res dfs(pos - 1, next_state, limit (i up), lead (i 0)); } if (!limit !lead) memo[pos][state] res; return res; }为什么要存记忆化时要求!limit !lead因为只有在不受上界限制、且前面已经出现了非零数字时后面的状态才和前缀具体数值无关才能被复用。这个条件我一开始写漏过导致记忆化结果被错误复用答案直接翻倍。数位DP入门阶段不用急着优化到迭代写法记忆化搜索能把逻辑拆得很清楚等熟练了再考虑空间压缩也不迟。6. 做完这套题后我沉淀下来的调试锦囊6.1 拿到DP题的四步拆解法我刷基础DP1形成的固定套路是第一步读题找出“阶段”——通常是数组下标、物品数量、区间长度或者树上的递归深度第二步问自己“如果在某个阶段停下来需要记录什么信息才能继续决策”这就是状态第三步让最后一个决策与前面状态冲突最小化写出转移第四步检查初始化和最终答案取哪个值。整个过程要在草稿纸上先写一遍再上机直接动手敲代码往往会把边界条件想漏。6.2 高频踩坑点清单INF 的设置求最小值时初始化为0x3f3f3f3f约10^9求最大值时初始化为负INF或者-1再特判别拍脑袋填一个很大的数否则INF INF会溢出成负数。多组输入重置滚动数组和dp表在下一组样例前必须重新初始化特别是用memset(memo, -1, sizeof(memo))的记忆化写法忘了清空会得到离谱答案。枚举顺序01背包倒序容量、完全背包正序容量、区间DP先长度后左端点、树形DP后序更新这些顺序错一个就全错。long long路径和、方案数、数位DP这类题答案很容易超过int上限定义成long long别等到WA了再回头改。位运算优先级mask (1 i)一定要加括号的优先级高于这行经典低级错误毁掉过不少状压DP。6.3 复盘不如重写这套题单刷完之后我的建议是先放一周然后不看任何题解重新做一遍。你会发现第二遍比第一遍快很多而且会不自觉地用更优的办法替代当时的笨办法。比如我之前LIS只会 \(O(n^2)\)第二遍就自然用起了二分石子合并这题我开始只会朴素区间DP后面才理解平行四边形优化。这种进步不是看题解能带来的必须通过亲手重写来固化。我个人的体会是基础DP1这套题的价值并不在于“刷完了”这个结果而在于做题过程中反复被迫回答“状态为什么这样定义”“顺序为什么这样枚举”这类问题。每次被WA逼着回头看转移方程其实就是一次对DP本质的理解加深。希望这篇总结能帮你在刷题时少走一些我走过的弯路更重要的是能在遇到没见过的DP题时先条件反射般地思考“最后一个决策是什么”而不是急着去搜题解。