动态规划从状态定义到转移方程构建可复用的解题思维框架一、动态规划的玄学困境为什么你总是定义不出状态动态规划是算法面试中通过率最低的题型之一。不是因为代码难写而是因为状态定义这一步卡住了大多数人。看到题目知道要用 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] 长度为 i1 的递增子序列的最小末尾元素 时间: O(nlogn), 空间: O(n) if not nums: return 0 import bisect tails [] # tails[i] 长度i1的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 (i1, j-1) 边界: dp[i][i1] 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 的核心不是背模板而是掌握识别问题性质 → 选择状态定义模式 → 推导转移方程这条思维链路。状态定义错了一切白费状态定义对了转移方程就是数学推导。