DP 设计方法与常见模型
基于通用算法套路 · 核于 2026-07
速查
- DP 设计五步：①定义状态（
dp[...]代表什么）；②找转移方程（从「最后一步」倒推）；③定边界条件（最小的几个初始值）；④确定计算顺序（从边界往大填，保证算dp[i]时依赖项已就绪）；⑤优化空间（滚动数组 / 一维化）。 - 找转移方程的关键技巧：从「最后一步」倒推——假设已经走到终点，最后一步是怎么来的？把所有可能的「最后一步」枚举出来取最优，转移方程自然浮现。
- 爬楼梯：每次爬 1 或 2 阶，到第 n 阶的方案数。
dp[i] = dp[i-1] + dp[i-2]，边界dp[1]=1, dp[2]=2——本质是斐波那契，可滚动到 O(1) 空间。 - 打家劫舍：相邻两家不能同时偷，求最大金额。
dp[i] = max(dp[i-1], dp[i-2] + nums[i])——「不偷 i」与「偷 i」取大，是「选或不选」在一维上的经典体现。 - Kadane 最大子数组和：求连续子数组的最大和。
dp[i] = max(nums[i], dp[i-1] + nums[i])——dp[i]= 以nums[i]结尾的最大子数组和，可滚动到 O(1)。 - DP vs 贪心 vs 分治选型：能严格证明「局部最优 ⇒ 全局最优」→ 贪心（最快）；子问题独立不重叠 → 分治；子问题重叠且要最优解 → DP。
- 如何识别 DP 题：题目问「最值（最大/最小/最长/最短）」或「方案数 / 是否可行」，且能拆成「语义相同的子问题」、子问题间有重叠——基本就是 DP。
- DP 的两个隐性前提：最优子结构（子问题最优能推出全局最优）+ 无后效性（未来只依赖当前状态，不依赖到达路径）。
- 状态定义决定难度：同一个题，状态定义得好转移就简洁，定义得差可能要做高维 DP——这是 DP 最需要题感的地方。
- 进阶顺序：本文 → 参考 → DP 进阶三部曲的后续（序列区间、树/数位 DP）。
一、DP 设计五步法
任何 DP 题都可以按这五步推进，避免「拿到题懵住」：
- 定义状态：明确
dp[...]代表什么含义。这是最关键的一步。原则是「状态要包含所有影响未来的信息」——满足无后效性。爬楼梯dp[i]= 到第 i 阶的方案数；打家劫舍dp[i]= 考虑前 i 家的最大金额。 - 找转移方程：从「最后一步」倒推——「如果已经到了位置 i，最后一步是怎么来的？」枚举所有可能的「最后一步」取最优。爬楼梯最后一步要么从 i-1、要么从 i-2 来，所以
dp[i] = dp[i-1] + dp[i-2]。 - 定边界条件：最小的、不依赖转移的初始值。漏边界或写错是 DP 最常见的 bug。爬楼梯
dp[1]=1, dp[2]=2；背包dp[0][...]=0；组合数dp[0]=1。 - 确定计算顺序：保证算
dp[i]时它依赖的子问题已就绪。一维 DP 从小到大；二维背包「外层物品、内层容量」；区间 DP「先算短区间再算长区间」。 - 优化空间：如果
dp[i]只依赖前面有限几项，用滚动数组或一维化把 O(n) / O(n²) 空间压到 O(1) / O(n)。
二、爬楼梯：一维线性递推
每次可以爬 1 或 2 阶，爬到第 n 阶有多少种方法（LeetCode 70）？
按五步走：
- 状态：
dp[i]= 爬到第 i 阶的方案数。 - 转移：最后一步要么跨 1 阶（来自 i-1）、要么跨 2 阶（来自 i-2），
dp[i] = dp[i-1] + dp[i-2]。 - 边界：
dp[1] = 1, dp[2] = 2（也可定义dp[0]=1统一）。 - 顺序：
i从 3 到 n。 - 空间：只依赖前两项，滚动到 O(1)。
function climbStairs(n) {
if (n <= 2) return n;
let prev2 = 1, prev1 = 2; // dp[1], dp[2]
for (let i = 3; i <= n; i++) {
const cur = prev1 + prev2; // dp[i] = dp[i-1] + dp[i-2]
prev2 = prev1; prev1 = cur;
}
return prev1;
}爬楼梯本质就是斐波那契。若每次可跨 1~k 阶，转移改为 dp[i] = Σ dp[i-k]——一维递推的通用形态。
三、打家劫舍：选或不选
沿街排列的房屋各有金额 nums[i]，相邻两家不能同时偷，求最大金额（LeetCode 198）。
- 状态：
dp[i]= 考虑前 i 家（下标 0~i-1）能偷到的最大金额。 - 转移：对第 i 家，不偷则金额继承
dp[i-1]；偷则不能偷第 i-1 家，金额为dp[i-2] + nums[i]，取大：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。 - 边界：
dp[0] = 0（0 家），dp[1] = nums[0]。 - 空间：滚动到 O(1)。
function rob(nums) {
const n = nums.length;
if (n === 0) return 0;
let prev2 = 0, prev1 = nums[0]; // dp[0], dp[1]
for (let i = 2; i <= n; i++) {
const cur = Math.max(prev1, prev2 + nums[i - 1]);
prev2 = prev1; prev1 = cur;
}
return prev1;
}打家劫舍是「选或不选」在一维上的经典——和 0-1 背包的「不放/放」同构。环形版本（首尾相邻）拆成「偷第一家不偷最后家」和「不偷第一家可偷最后家」两个线性子问题取大即可。
四、Kadane：最大子数组和
求数组中和最大的连续子数组（LeetCode 53）。
- 状态：
dp[i]= 以nums[i]结尾的最大子数组和（注意「以 i 结尾」这个约束）。 - 转移：要么
nums[i]自己单独成段，要么接在「以nums[i-1]结尾」的最大子数组后面，取大：dp[i] = max(nums[i], dp[i-1] + nums[i])。 - 边界：
dp[0] = nums[0]。 - 答案：
max(dp[i])，不是dp[n-1]（因为状态是「以 i 结尾」，最优段不一定以最后元素结尾）。 - 空间：滚动到 O(1)。
function maxSubArray(nums) {
let cur = nums[0], best = nums[0]; // cur=dp[i], best=历史最大
for (let i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}Kadane 的精髓在状态定义：「以 i 结尾」让转移只需看 dp[i-1]，把看似要 O(n²) 枚举起点的题压到 O(n)。这是好状态定义简化转移的典范。
五、DP vs 贪心 vs 分治：怎么选
| 范式 | 适用信号 | 子问题关系 | 复杂度优势 | 典型 |
|---|---|---|---|---|
| 贪心 | 能证明「局部最优 ⇒ 全局最优」 | 不显式划分子问题 | 最快，常 O(n log n) | 区间调度、Huffman |
| 分治 | 问题能均分成独立子问题 | 独立、不重叠 | O(n log n) | 归并排序、快排 |
| DP | 有最优子结构 + 重叠子问题 | 重叠、需记忆化 | 指数降多项式 | 背包、LCS、Kadane |
选型口诀：先想能不能贪心（最快）→ 不能再想分治（子问题独立）→ 都不行用 DP（子问题重叠、要最优解）。注意三者不互斥： Kadane 既可看成 DP 也可看成贪心（每步保留「接上 vs 重开」的较大者）；分治加重叠子问题记忆化就退化成 DP（记忆化搜索）。
六、如何识别一道 DP 题
拿到题先做三个判断：
- 问什么：问「最值（最大/最小/最长/最短/最少）」或「方案数 / 是否可行 / 能否凑出」——这是 DP 的强信号。
- 能否拆成语义相同的子问题：问题规模缩小后，形式不变（爬到第 n 阶 vs 第 n-1 阶，问的都是「方案数」）。
- 子问题是否重叠：不同的求解路径会不会反复遇到同一个子问题——重叠才有记忆化收益。
满足这三条，基本就是 DP。然后按五步法推进：定义状态 → 找转移 → 定边界 → 定顺序 → 优化空间。
常见 DP 信号词：「最大/最小」「方案数」「是否可能」「凑成/组合」「恰好/至多/至少」+ 「连续 / 子序列 / 子集 / 划分」结构。
交互演示
- 0-1 背包可视化演示 —— DP 表逐格填充的过程
- 零钱兑换可视化演示 —— 最少硬币数的递推
下一步
掌握了五步法与一维模型后，可以把所有套路沉淀成一份速查手册——状态定义、转移方程、代码模板、易错点一览，见参考。后续 DP 三部曲将进入序列区间（LCS/LIS/编辑距离）与进阶（树 DP/数位 DP/换根 DP）。