页面加载中…
从爬楼梯到编辑距离，用「定状态→写转移→定边界→定遍历序」四步框架打通全部 DP 题型
动态规划是面试最高频也最令人头疼的专题。本路径从最简单的一维递推出发，逐步引入背包、二维路径、子序列、状态机等经典模型，每道题都指明它与上一题「复用或打破了哪条规律」。跟着这条线走完，你会发现所有 DP 题都在反复用同一套框架，不再觉得每道题都是全新的。
适合：被 DP 劝退、想要一套统一框架的人
建立四步框架：① 定义 dp[i] 含义；② 找转移方程；③ 确定边界；④ 确定遍历方向。从「前一项」到「前两项」，感受用已知推未知的 DP 核心思路。
DP 起点：dp[i]=dp[i-1]+dp[i-2]，边界 dp[1]=1,dp[2]=2。这是整条路径的「母框架」，后续所有题都是它的变形。
复用爬楼梯转移，叠加 cost[i] 取最小：dp[i]=min(dp[i-1],dp[i-2])+cost[i]，状态目标从方案数变最小花费。
爬楼梯去掉花费的裸版，边界改为 dp[0]=0,dp[1]=1，用来单独确认自己理解了 dp[i-1]+dp[i-2] 的状态依赖。
斐波那契依赖前 2 项，这题改成 dp[i]=dp[i-1]+dp[i-2]+dp[i-3]，「多记一格」，滚动数组优化同样适用。
在「依赖前几项」基础上引入「选或不选当前元素」的决策分支：dp[i]=max(选i, 不选i)。掌握 Kadane 算法、乘积同时维护 max/min，以及字符串分割等一维 DP 变体。
爬楼梯必须选每格，这题可选可不选：dp[i]=max(dp[i-1],dp[i-2]+nums[i])，「跳一格」来自两步转移，目标从方案数变最大金额。
打家劫舍 I 的线性数组首尾相连成环，直接跑会让首尾同选。拆成「不选首」和「不选尾」两段各跑一次打家劫舍 I，取最大值。
打家劫舍不相邻选元素；这题改选连续子数组，Kadane：dp[i]=max(nums[i],dp[i-1]+nums[i])，接前缀还是重新开始由前一状态决定。
Kadane 只维护最大值；负数×负数变正，必须同时维护 dpMax 和 dpMin，在 Kadane 框架上多挂一条最小值轨道。
打家劫舍每次跳 1 或 2 格，这题取 1 位或 2 位解码：dp[i]=dp[i-1]+dp[i-2]（两位合法时），本质仍是爬楼梯转移，加字符范围校验。
解码方法每次取固定 1/2 位；这题单词长度不固定，枚举所有切点 j：若 s[j..i] 在字典中且 dp[j]=true，则 dp[i]=true。
背包 DP 的核心区别：0-1 背包每件只用一次（逆序遍历容量），完全背包可重复用（正序遍历容量）。掌握遍历方向的本质后，硬币、分割、计数等一大类题目迎刃而解。
word-break 判「能否」到达；这题改为「最少枚数」：dp[j]=min(dp[j],dp[j-c]+1)，硬币可重复取故正序遍历，完全背包第一例。
零钱兑换 I 求最少件数，这题求组合方案数：dp[j]+=dp[j-c]，完全背包正序遍历不变，只换了目标函数从最优化改为计数。
零钱兑换 I 的硬币换成预生成的完全平方数（1,4,9,…），「最少枚数」转移方程完全一致，完全背包框架直接复用。
完全背包可重复取；这题每个数只用一次，目标「恰好装满 sum/2」——0-1 背包，容量倒序遍历防止同一元素被取两次。
分割等和子集判「能否装满」，这题统计「有多少种方案装满」：dp[j]+=dp[j-num]，逆序遍历保留 0-1 约束，目标从布尔变计数。
dp 升级到二维，dp[i][j] 表示处理到位置 (i,j) 或两个前缀 s1[0..i]/s2[0..j] 时的最优解。掌握路径 DP 和双序列对齐 DP 两大原型，以及三向依赖转移的处理方式。
一维递推扩到二维网格：dp[i][j]=dp[i-1][j]+dp[i][j-1]，只向右或向下走，边界全为 1，最简二维 DP 入门。
不同路径统计方案数（加法），这题叠加格子权重求最小：dp[i][j]=min(上,左)+grid[i][j]，二维路径 DP「换目标函数」的典型演示。
最小路径和在矩形走；三角形每行宽度递增只走相邻两格，自底向上：dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+tri[i][j]。
二维路径沿固定方向走；LIS 跳到任意更小值：dp[i]=max(dp[j]+1)（j<i,nums[j]<nums[i]），首次出现不连续 O(n²) 转移。
LIS 是单序列 DP；LCS 是双序列：dp[i][j] 表示 s1 前 i 个与 s2 前 j 个的最长公共子序列，字符相等则 +1，否则取两向最大值。
LCS 只有匹配/跳过；编辑距离加「替换」变三向取最小：删 dp[i-1][j]+1、插 dp[i][j-1]+1、替 dp[i-1][j-1]+cost。
编辑距离三方向取最优；这题「右下角 (i,j) 的最大正方形边长」同样依赖三格但取最小：dp[i][j]=min(上,左,左上)+1，三向依赖换了方向含义。
状态机 DP 给每个位置定义多个「状态维度」（如持股/空仓/冷冻），转移在状态间跳转；区间 DP 枚举分割点，按区间长度从小到大遍历。两类模型是 DP 的高阶收官。
打家劫舍的二态「选/不选」；股票冷冻期升级为三态：持股、空仓可买、冷冻，三组转移方程同步更新——状态机 DP 标准范式。
冷冻期靠三态状态机约束；树形 DP 把状态搬到树节点，后序 DFS 每节点返回 (选,不选) 二元组，父节点按打家劫舍逻辑取最优。
树形 DP 后序返回二元组来传递子树最优；这题在状态机基础上增加交易次数 k 维：dp[i][k][0/1]，把次数约束纳入状态定义。
树形 DP 合并子树；区间 DP 枚举「最后戳的气球 k」：dp[l][r] 由两段子区间加边界乘积推出，按区间长度从小到大填表。