动态规划从状态定义到转移方程：构建可复用的解题思维框架
一、动态规划的"玄学"困境：为什么你总是定义不出状态？
动态规划是算法面试中通过率最低的题型之一。不是因为代码难写，而是因为状态定义这一步卡住了大多数人。看到题目，知道要用 DP，但 dp[i] 到底代表什么？是"以 i 结尾的最大值"还是"前 i 个元素的最大值"？这两个定义差一个字，转移方程完全不同。
更深层的问题是：很多人把 DP 当作"背模板"，遇到新题就套不上。实际上，DP 的核心不是模板，而是最优子结构和重叠子问题的识别。一旦识别出这两个性质，状态定义和转移方程就是水到渠成的事。本文的目标是建立一套从题目特征到状态定义的映射规则，让 DP 不再靠灵感。
二、动态规划的核心机制：从暴力搜索到记忆化递归
2.1 DP 的三要素与推导链
flowchart TD A[原问题] --> B{能否分解为子问题?} B -->|否| C[不适用DP] B -->|是| D{子问题是否重叠?} D -->|否| E[用分治法] D -->|是| F{是否具有最优子结构?} F -->|否| G[用记忆化搜索/暴力] F -->|是| H[动态规划] H --> I[定义状态 dp i] I --> J[推导转移方程] J --> K[确定边界条件] K --> L[选择遍历顺序] L --> M[空间优化] I --> N[状态定义规则] N --> N1[结尾型: 以i结尾的最优解] N --> N2[前缀型: 前i个元素的最优解] N --> N3[区间型: 区间i到j的最优解] N --> N4[状态机: 处于状态k的最优解]2.2 四种经典状态定义模式
模式一：结尾型——dp[i] 表示"以位置 i 结尾"的最优解。适用于连续子序列问题（最大子数组和、最长递增子序列）。转移时只关心 dp[i-1] 与当前元素的关系。
模式二：前缀型——dp[i] 表示"前 i 个元素"的最优解。适用于选择问题（0-1 背包、爬楼梯）。转移时考虑"选或不选"第 i 个元素。
模式三：区间型——dp[i][j] 表示"区间 [i,j]"的最优解。适用于矩阵链乘法、回文子串、戳气球。转移时枚举分割点 k。
模式四：状态机型——dp[i][k] 表示"处理到第 i 个位置，处于状态 k"的最优解。适用于股票买卖（持有/不持有）、打家劫舍（偷/不偷）。
2.3 转移方程的推导方法
转移方程的本质是：当前状态如何由更小的子状态组合而来。推导步骤：1）明确 dp 的语义；2）枚举当前决策的所有选择；3）对每个选择，写出对应的前置状态；4）取所有选择中的最优值。
三、生产级实现：DP 解题框架与经典题解
from typing import List, Tuple, Optional from dataclasses import dataclass from enum import Enum import time class DPType(Enum): """DP 类型""" ENDING = "ending" # 结尾型 PREFIX = "prefix" # 前缀型 INTERVAL = "interval" # 区间型 STATE_MACHINE = "state_machine" # 状态机型 @dataclass class DPSolution: """DP 解法描述""" problem_name: str dp_type: DPType state_definition: str transition: str base_case: str time_complexity: str space_complexity: str code: str class DPSolver: """ 动态规划解题框架 提供标准化的状态定义、转移和验证流程 """ @staticmethod def max_subarray(nums: List[int]) -> int: """ LeetCode 53: 最大子数组和 状态定义(结尾型): dp[i] = 以nums[i]结尾的最大子数组和 转移方程: dp[i] = max(dp[i-1] + nums[i], nums[i]) 边界: dp[0] = nums[0] 时间: O(n), 空间: O(1) 滚动优化 """ if not nums: raise ValueError("输入数组不能为空") # 滚动变量优化空间 prev = nums[0] max_sum = nums[0] for i in range(1, len(nums)): # 核心转移：要么接上前面的子数组，要么从自己重新开始 curr = max(prev + nums[i], nums[i]) max_sum = max(max_sum, curr) prev = curr return max_sum @staticmethod def longest_increasing_subsequence(nums: List[int]) -> int: """ LeetCode 300: 最长递增子序列 状态定义(结尾型): dp[i] = 以nums[i]结尾的LIS长度 转移方程: dp[i] = max(dp[j] + 1) for all j < i and nums[j] < nums[i] 边界: dp[i] = 1 时间: O(n^2), 空间: O(n) 进阶: 二分+贪心可优化到 O(nlogn) """ 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]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) @staticmethod def lis_binary_search(nums: List[int]) -> int: """ LIS 的 O(nlogn) 解法：贪心 + 二分 维护一个严格递增的 tails 数组 tails[i] = 长度为 i+1 的递增子序列的最小末尾元素 时间: O(nlogn), 空间: O(n) """ if not nums: return 0 import bisect tails = [] # tails[i] = 长度i+1的LIS的最小末尾 for num in nums: # 在 tails 中找到第一个 >= num 的位置 pos = bisect.bisect_left(tails, num) if pos == len(tails): tails.append(num) # num 可以扩展最长子序列 else: tails[pos] = num # 用更小的值替换，为后续留更多空间 return len(tails) @staticmethod def coin_change(coins: List[int], amount: int) -> int: """ LeetCode 322: 零钱兑换 状态定义(前缀型): dp[i] = 凑成金额i所需的最少硬币数 转移方程: dp[i] = min(dp[i - coin] + 1) for coin in coins if coin <= i 边界: dp[0] = 0, dp[i] = INF for i > 0 时间: O(amount * len(coins)), 空间: O(amount) """ if amount < 0: return -1 if amount == 0: return 0 if not coins: return -1 INF = float('inf') dp = [INF] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for coin in coins: if coin <= i and dp[i - coin] != INF: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != INF else -1 @staticmethod def stock_max_profit(prices: List[int]) -> int: """ LeetCode 121: 买卖股票的最佳时机（只能交易一次） 状态定义(状态机型): dp_hold = 第i天持有股票时的最大利润 dp_cash = 第i天不持有股票时的最大利润 转移方程: dp_hold = max(dp_hold, -prices[i]) # 买入 dp_cash = max(dp_cash, dp_hold + prices[i]) # 卖出 边界: dp_hold = -prices[0], dp_cash = 0 时间: O(n), 空间: O(1) """ if not prices or len(prices) < 2: return 0 hold = -prices[0] # 第一天买入 cash = 0 # 第一天不操作 for i in range(1, len(prices)): # 状态机转移：注意要用前一天的值，所以同时更新 new_hold = max(hold, -prices[i]) new_cash = max(cash, hold + prices[i]) hold, cash = new_hold, new_cash return cash @staticmethod def burst_balloons(nums: List[int]) -> int: """ LeetCode 312: 戳气球（区间DP经典题） 状态定义(区间型): dp[i][j] = 戳破开区间(i,j)内所有气球获得的最大硬币 转移方程: dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) for k in (i+1, j-1) 边界: dp[i][i+1] = 0 (区间内无气球) 时间: O(n^3), 空间: O(n^2) """ # 添加边界气球，值为1 arr = [1] + nums + [1] n = len(arr) # dp[i][j] = 戳破开区间(i,j)内所有气球的最大收益 dp = [[0] * n for _ in range(n)] # 区间长度从3开始（至少包含一个可戳的气球） for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 # 枚举最后戳破的气球 k for k in range(i + 1, j): dp[i][j] = max( dp[i][j], dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j], ) return dp[0][n - 1] # ===== 验证与复杂度论证 ===== if __name__ == "__main__": solver = DPSolver() # 最大子数组和 assert solver.max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6 assert solver.max_subarray([1]) == 1 assert solver.max_subarray([-1]) == -1 print("最大子数组和: 全部测试通过") # LIS assert solver.longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18]) == 4 assert solver.lis_binary_search([10, 9, 2, 5, 3, 7, 101, 18]) == 4 print("LIS: O(n^2) 和 O(nlogn) 解法结果一致") # 零钱兑换 assert solver.coin_change([1, 2, 5], 11) == 3 assert solver.coin_change([2], 3) == -1 assert solver.coin_change([1], 0) == 0 print("零钱兑换: 全部测试通过") # 股票买卖 assert solver.stock_max_profit([7, 1, 5, 3, 6, 4]) == 5 assert solver.stock_max_profit([7, 6, 4, 3, 1]) == 0 print("股票买卖: 全部测试通过") # 戳气球 assert solver.burst_balloons([3, 1, 5, 8]) == 167 print("戳气球: 测试通过") # 性能验证 import random large = [random.randint(-100, 100) for _ in range(100000)] start = time.time() solver.max_subarray(large) elapsed = time.time() - start print(f"\n最大子数组和 10^5 规模: {elapsed*1000:.1f}ms (应 < 100ms)")四、动态规划的陷阱与适用边界
4.1 状态定义的常见错误
最典型的错误是状态定义与转移方程不匹配。例如，把 LIS 定义为"前 i 个元素的 LIS 长度"（前缀型），但转移时需要知道"以哪个元素结尾"，前缀型定义无法提供这个信息。这就是为什么 LIS 必须用结尾型定义。
另一个常见错误是遗漏状态维度。股票问题如果只用一维 dp[i] 表示"第 i 天的最大利润"，就无法区分"持有"和"不持有"两种状态，导致转移方程错误。
4.2 DP vs 贪心 vs 分治
| 特征 | DP | 贪心 | 分治 |
|---|---|---|---|
| 子问题重叠 | 有 | 无 | 无 |
| 最优子结构 | 需要 | 需要 | 不需要 |
| 全局最优 | 保证 | 不保证 | 不适用 |
| 时间复杂度 | 通常高于贪心 | 通常最低 | O(nlogn) |
| 典型问题 | 背包、LCS | 活动选择、Huffman | 归并排序 |
4.3 DP 的禁用场景
- 子问题不重叠：用分治更高效，如归并排序
- 无最优子结构：如最长简单路径（路径不能重复经过节点）
- 状态空间爆炸：维度过高（> 3 维）时，DP 的时间和空间都不可接受
- 在线算法：输入逐个到来，无法回溯，DP 需要全局信息
五、总结
本文建立了动态规划的系统化解题框架：从最优子结构和重叠子问题的识别出发，到四种状态定义模式（结尾型、前缀型、区间型、状态机型），再到转移方程的推导方法。五道经典题的完整实现覆盖了所有模式，每道题都包含状态定义、转移方程、边界条件和复杂度论证。DP 的核心不是背模板，而是掌握"识别问题性质 → 选择状态定义模式 → 推导转移方程"这条思维链路。状态定义错了，一切白费；状态定义对了，转移方程就是数学推导。
