当前位置：首页 > news >正文

动态规划从入门到精通：状态定义与转移方程的设计方法论

news 2026/6/29 10:50:05

动态规划从入门到精通：状态定义与转移方程的设计方法论

一、动态规划为什么这么难——从"看懂题解但不会做新题"说起

动态规划（DP）是算法面试中公认最难的题型之一。很多人的学习路径是：看题解 → 觉得有道理 → 自己做新题 → 完全没有思路。这个困境的根源在于：题解只给了"这道题的状态定义和转移方程"，但没有解释"为什么这样定义状态"以及"怎么从题目描述推导出状态定义"。

DP 的核心不是背模板，而是掌握一套从问题到状态定义再到转移方程的推导方法论。本文将拆解这套方法论，并通过三道经典 DP 题展示从零推导的完整过程。

二、DP 求解的四步方法论

2.1 四步法流程

flowchart TD A[Step 1: 识别最优子结构] --> B[Step 2: 定义状态] B --> C[Step 3: 推导转移方程] C --> D[Step 4: 确定边界与遍历顺序] A --> A1["原问题的最优解<br/>包含子问题的最优解"] B --> B1["状态 = 子问题的描述<br/>通常用 dp[i] 或 dp[i][j]"] C --> C1["dp[i] 如何从更小的子问题<br/>递推得到"] D --> D1["初始条件 + 遍历方向<br/>确保依赖已计算"]

2.2 Step 1：识别最优子结构

最优子结构是 DP 的前提。判断标准：原问题的最优解是否可以由子问题的最优解组合而成。

有最优子结构：最短路径、最大子数组和、最长递增子序列
无最优子结构：最长简单路径（因为子路径可能共享节点，不满足独立性）

2.3 Step 2：定义状态

状态定义是 DP 最关键也最难的一步。常见策略：

问题类型	状态定义模式	示例
线性序列	dp[i] = 以 i 结尾的最优值	最长递增子序列
区间问题	dp[i][j] = 区间 [i,j] 的最优值	戳气球
背包问题	dp[i][w] = 前 i 个物品、容量 w 的最优值	0-1 背包
路径问题	dp[i][j] = 从起点到 (i,j) 的最优值	最小路径和

状态定义的检验标准：

状态能唯一描述子问题
转移方程能从更小的状态推出更大的状态
最终答案能从某个状态直接得出

2.4 Step 3：推导转移方程

转移方程的本质是：当前状态可以从哪些更小的状态转移而来？每种转移的代价/收益是什么？

2.5 Step 4：确定边界与遍历顺序

边界条件是 DP 的"地基"。遍历顺序必须保证：计算 dp[i] 时，它依赖的所有子状态已经计算完毕。

flowchart LR A[一维 DP] --> B["从左到右遍历<br/>dp[0] 为边界"] C[二维 DP - 路径] --> D["从上到下、从左到右<br/>dp[0][0] 为边界"] E[二维 DP - 区间] --> F["先枚举区间长度<br/>再枚举左端点"] G[二维 DP - 背包] --> H["外层物品、内层容量<br/>0-1 背包逆序遍历"]

三、三道经典 DP 题的完整推导

3.1 最长递增子序列（LeetCode 300）

Step 1 - 最优子结构：以 nums[i] 结尾的 LIS，其前驱一定是某个以 nums[j] 结尾的 LIS（j < i 且 nums[j] < nums[i]）。

Step 2 - 状态定义：dp[i] = 以 nums[i] 结尾的最长递增子序列的长度。

Step 3 - 转移方程：

dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

Step 4 - 边界：dp[i] = 1（每个元素自身构成长度为 1 的子序列）。

def length_of_lis(nums: list[int]) -> int: """ 最长递增子序列 - O(n^2) DP 解法。 dp[i] 表示以 nums[i] 结尾的 LIS 长度。 时间复杂度 O(n^2)，空间复杂度 O(n)。 """ if not nums: return 0 n = len(nums) dp = [1] * n # 每个元素自身构成长度为 1 的子序列 for i in range(1, n): for j in range(i): if nums[j] < nums[i]: # 如果 nums[j] 可以作为 nums[i] 的前驱，尝试更新 dp[i] = max(dp[i], dp[j] + 1) return max(dp)

3.2 0-1 背包问题

Step 1 - 最优子结构：前 i 个物品在容量 w 下的最大价值，取决于第 i 个物品选或不选。

Step 2 - 状态定义：dp[i][w] = 前 i 个物品、容量为 w 时的最大价值。

Step 3 - 转移方程：

dp[i][w] = max( dp[i-1][w], # 不选第 i 个物品 dp[i-1][w-weight[i]] + value[i] # 选第 i 个物品 ) (前提: w >= weight[i])

def knapsack_01( weights: list[int], values: list[int], capacity: int, ) -> int: """ 0-1 背包问题 - 二维 DP 解法。 dp[i][w] 表示前 i 个物品、容量 w 时的最大价值。 时间复杂度 O(n*W)，空间复杂度 O(n*W)。 """ n = len(weights) # 初始化 (n+1) x (capacity+1) 的 DP 表 dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(capacity + 1): # 不选第 i 个物品 dp[i][w] = dp[i - 1][w] # 选第 i 个物品（如果容量足够） if w >= weights[i - 1]: dp[i][w] = max( dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1], ) return dp[n][capacity]

空间优化：由于 dp[i] 只依赖 dp[i-1]，可以压缩为一维数组，但内层循环必须逆序遍历：

def knapsack_01_optimized( weights: list[int], values: list[int], capacity: int, ) -> int: """ 0-1 背包 - 一维空间优化版。 内层逆序遍历保证每个物品只选一次。 时间复杂度 O(n*W)，空间复杂度 O(W)。 """ dp = [0] * (capacity + 1) for i in range(len(weights)): # 逆序遍历：防止同一物品被重复选取 for w in range(capacity, weights[i] - 1, -1): dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) return dp[capacity]

3.3 编辑距离（LeetCode 72）

Step 1 - 最优子结构：将 word1[0:i] 变成 word2[0:j] 的最少操作，取决于最后一个字符的操作选择。

Step 2 - 状态定义：dp[i][j] = word1 前 i 个字符变成 word2 前 j 个字符的最少操作数。

Step 3 - 转移方程：

if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] # 字符相同，无需操作 else: dp[i][j] = min( dp[i-1][j] + 1, # 删除 word1[i-1] dp[i][j-1] + 1, # 插入 word2[j-1] dp[i-1][j-1] + 1, # 替换 word1[i-1] 为 word2[j-1] )

def min_distance(word1: str, word2: str) -> int: """ 编辑距离 - 二维 DP 解法。 dp[i][j] 表示 word1[:i] 变为 word2[:j] 的最少操作数。 时间复杂度 O(m*n)，空间复杂度 O(m*n)。 """ m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] # 边界：空串变成长度为 j 的串需要 j 次插入 for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: # 字符相同，继承前一个状态 dp[i][j] = dp[i - 1][j - 1] else: # 取三种操作的最小值加一 dp[i][j] = min( dp[i - 1][j] + 1, # 删除 dp[i][j - 1] + 1, # 插入 dp[i - 1][j - 1] + 1, # 替换 ) return dp[m][n]