动态规划进阶：从状态定义到空间优化的系统化解题方法
一、动态规划的核心难点：状态定义比转移方程更重要
动态规划（DP）是算法面试中出现频率最高的题型之一，但大多数人的学习路径是"背转移方程"，遇到新题就无从下手。核心问题在于：转移方程只是 DP 的表象，真正的难点是状态定义。状态定义错了，转移方程不可能对；状态定义对了，转移方程通常水到渠成。
状态定义的关键原则是"无后效性"：当前状态的决策只依赖之前的状态值，不依赖到达该状态的路径。如果状态定义不满足无后效性，就需要增加维度来消除后效性。例如，0-1 背包问题中，如果状态只定义"前 i 个物品的最大价值"，无法区分"哪些物品被选了"，需要增加"容量 j"维度。
二、DP 题型的分类与状态定义模式
graph TB DP[动态规划] --> LINEAR[线性 DP] DP --> INTERVAL[区间 DP] DP --> TREE[树形 DP] DP --> STATE[状态压缩 DP] LINEAR --> L1[一维：LIS 最大子数组] LINEAR --> L2[二维：LCS 编辑距离] LINEAR --> L3[背包：0-1 完全 多重] INTERVAL --> I1[矩阵链乘法] INTERVAL --> I2[回文子串] TREE --> T1[树的最大独立集] TREE --> T2[树形背包] STATE --> S1[旅行商 TSP] STATE --> S2[棋盘覆盖]三、DP 解题框架与经典题型
from typing import List from functools import lru_cache # ========== 框架 1：0-1 背包 ========== # 状态定义：dp[i][j] = 前 i 个物品、容量 j 的最大价值 def knapsack_01(weights: List[int], values: List[int], capacity: int) -> int: n = len(weights) # 空间优化：一维数组，逆序遍历容量 dp = [0] * (capacity + 1) for i in range(n): # 逆序：保证每个物品只用一次 for j in range(capacity, weights[i] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[capacity] # ========== 框架 2：最长递增子序列 ========== # 状态定义：dp[i] = 以 nums[i] 结尾的 LIS 长度 def length_of_lis(nums: List[int]) -> int: 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) # 优化：贪心 + 二分查找 O(n log n) def length_of_lis_optimized(nums: List[int]) -> int: """贪心 + 二分：维护最小的递增序列尾部""" tails = [] # tails[i] = 长度为 i+1 的递增子序列的最小尾部 for num in nums: # 二分查找第一个 >= num 的位置 left, right = 0, len(tails) while left < right: mid = (left + right) // 2 if tails[mid] < num: left = mid + 1 else: right = mid if left == len(tails): tails.append(num) # 扩展序列 else: tails[left] = num # 替换，保持更小的尾部 return len(tails) # ========== 框架 3：编辑距离 ========== # 状态定义：dp[i][j] = word1[:i] 变为 word2[:j] 的最少操作数 def min_distance(word1: str, word2: str) -> int: m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] # 边界：空串到另一个串的操作数 for i in range(m + 1): dp[i][0] = i # 删除 i 次 for j in range(n + 1): dp[0][j] = 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] = 1 + min( dp[i-1][j], # 删除 word1[i-1] dp[i][j-1], # 插入 word2[j-1] dp[i-1][j-1], # 替换 ) return dp[m][n] # ========== 框架 4：区间 DP — 最长回文子序列 ========== # 状态定义：dp[i][j] = s[i..j] 中的最长回文子序列长度 def longest_palindrome_subseq(s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] # 单字符回文 for i in range(n): dp[i][i] = 1 # 从短区间到长区间 for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2 else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]) return dp[0][n-1] # ========== 框架 5：树形 DP — 打家劫舍 III ========== # 状态定义：每个节点返回 (rob, not_rob) — 抢/不抢该节点的最大收益 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def rob_tree(root: TreeNode) -> int: def dfs(node): if not node: return (0, 0) # (抢, 不抢) left = dfs(node.left) right = dfs(node.right) # 抢当前节点：子节点不能抢 rob = node.val + left[1] + right[1] # 不抢当前节点：子节点可抢可不抢，取最大 not_rob = max(left) + max(right) return (rob, not_rob) return max(dfs(root))四、动态规划的 Trade-offs 分析
记忆化搜索 vs 递推：自顶向下的记忆化搜索代码更直观，但递归栈深度受 Python 限制（默认 1000）。自底向上的递推没有栈溢出风险，但需要确定遍历顺序。建议先用记忆化搜索验证正确性，再转为递推优化性能。
空间优化的风险：一维空间优化（如 0-1 背包的逆序遍历）依赖遍历顺序的正确性。如果顺序写错（正序变逆序），结果完全不同。建议先写二维 DP 验证正确性，再优化空间。
状态压缩 DP 的适用范围：状态压缩只适用于状态维度小（通常 ≤ 20）的场景，因为状态空间是 2^n。超过 20 个元素时状态空间爆炸，需要考虑其他算法（如分支限界）。
DP 与贪心的区分：贪心是 DP 的特例——当每步的最优选择不依赖后续状态时，DP 退化为贪心。如果无法证明贪心的正确性，应该用 DP。贪心错误通常比 DP 超时更难发现。
五、总结
动态规划的核心是状态定义，而非转移方程。好的状态定义满足无后效性，使转移方程自然推导。线性 DP（背包、LIS、LCS）是最常见的基础题型，区间 DP 和树形 DP 是进阶方向。空间优化（一维化）是常见考点，但必须先保证正确性再优化。建议按"状态定义 → 转移方程 → 边界条件 → 空间优化"四步法系统解题，避免靠直觉写转移方程。
