在做 DP 题时最常遇到的困境是“看题解秒懂自己写就懵尤其是那个核心的转移方程到底是怎么想出来的”今天从 LeetCode 上一道最经典的入门题——70. 爬楼梯 提炼出一套普适的动态规划解题框架。一、 引言从爬楼梯说起题目描述假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢这题看似是排列组合实际上是一道标准的动态规划题。二、 动态规划的核心状态与转移动态规划的本质是通过定义状态和状态之间的递推关系将大问题拆解为小问题并利用历史结果避免重复计算。要写出正确的代码必须回答两个问题状态定义Statedp[i]代表什么状态转移方程Transitiondp[i]和dp[i-1]、dp[i-2]等有什么关系1. 状态定义对于爬楼梯最自然的定义是dp[i]表示到达第i阶楼梯的方法总数。2. 推导状态转移方程核心难点如何从已知状态推导出dp[i]关键思考法最后一步法逆向思维想象你已经站在了第i阶楼梯上。你是怎么上来的题目规定你只能爬 1 阶或 2 阶。情况 A你是从第i-1阶爬 1 阶上来的。情况 B你是从第i-2阶爬 2 阶上来的。因为这两条路径是互斥的要么最后一步跨1阶要么跨2阶所以到达第i阶的方法总数 到达第i-1阶的方法数 到达第i-2阶的方法数。由此得出转移方程dp[i]dp[i−1]dp[i−2]注意这里用的是加法而不是max因为题目求的是“总数”不是“最大步数”。3. 边界条件与初始化dp[1] 1到第1阶只有1种方法爬1阶。dp[2] 2到第2阶有2种方法11 或 2。dp[0]理论上不需要用到但有时为了方便计算可以设为1。4. 正确的代码实现C其实就是斐波那契数列class Solution { public: int climbStairs(int n) { // 边界判断防止数组越界 if (n 2) return n; vectorint dp(n 1); dp[1] 1; dp[2] 2; for (int i 3; i n; i) { // 状态转移方程 dp[i] dp[i-1] dp[i-2]; } return dp[n]; } };进阶优化由于dp[i]只依赖前两个状态可以把空间复杂度从 O(N) 优化到 O(1)用两个变量滚动更新即可。三、 普适化如何识别不同类型的动态转移方程爬楼梯是“线性DP”的入门但在实际算法题中DP 题型千变万化。下面是 DP 常见的转移方程类型的五大模式。模式一线性递推爬楼梯型特征状态按照线性顺序如数组下标、楼梯阶数依次递推。方程形式dp[i] dp[i-1] dp[i-2]或带有权重的dp[i] min(dp[i-1], dp[i-2]) cost[i]。模式二区间 DP合并型特征状态通常定义在区间[i, j]上大区间的解由小区间合并而来。方程形式dp[i][j] min/max(dp[i][k] dp[k1][j] cost)其中k是分割点。思考技巧枚举分割点。把大问题切分成两个子问题再加合起来的代价。模式三背包 DP选择型特征给定一个容量限制背包在若干物品中选择求最大价值或方案数。方程形式0-1背包每个物品只能选一次dp[j] max(dp[j], dp[j-w[i]] v[i])注意逆序遍历j。完全背包物品无限dp[j] max(dp[j], dp[j-w[i]] v[i])正序遍历j。思考技巧“选”与“不选”。当前容量j对于物品i要么不选保持dp[j]要么选腾出空间w[i]放入。模式四双序列 DP匹配型特征涉及两个字符串或两个数组通常需要二维 DP 表。方程形式dp[i][j]表示A的前i个和B的前j个的某种关系。若A[i] B[j]则dp[i][j] dp[i-1][j-1] 1或直接继承。若不等则dp[i][j] max(dp[i-1][j], dp[i][j-1])。思考技巧画二维表格。考虑当前字符匹配时左上角怎么转移不匹配时左边或上边怎么转移。模式五树形 DP特征数据结构是树状态在递归回溯时从子节点传递给父节点。方程形式通常结合 DFSdp[node][0/1]表示节点选或不选的状态。思考技巧后序遍历。先算清楚左右子树的状态再决定当前节点的状态。四、 总结动态规划解题四步走当你面对一道新题怀疑它是 DP 时请按以下步骤操作定义状态明确dp数组的含义一维还是二维下标代表什么。找转移方程思考“最后一步”是怎么来的或者“当前状态”可以由哪些“前驱状态”推导出来。这是最关键的一步通常需要分类讨论如选/不选、匹配/不匹配。确定初始值dp[0]、dp[1]等边界是什么注意数组越界问题如爬楼梯中n1的情况。确定遍历顺序是从前往后还是从后往前是外层循环物品还是内层循环容量确保计算dp[i]时依赖的状态已经计算完毕。