动态规划题型分类与解题套路总结从入门到工程思维的跃迁一、深度引言与场景痛点为什么 DP 题一看就会一写就废动态规划是算法面试的过滤器。几乎所有大厂的面试DP 题的出现频率仅次于数据结构的应用题。但 DP 又是最让人有挫败感的方向——看题解觉得逻辑通畅自己写总是在状态定义或转移方程上卡壳。7 月我把 LeetCode 上的 DP 题按题型做了系统分类和集中训练。一个关键发现是DP 题做不出来的核心原因不是不聪明而是没有建立从题目特征到 DP 类型的映射直觉。换句话说你看完题目后无法快速判断它是背包还是区间 DP还是状态压缩这就导致每次都要从零开始推导。本篇文章的目标是建立一个可操作的 DP 题型分类体系让每一类题型都有对应的识别特征和解题模板。二、底层机制与原理深度剖析DP 的本质是最优子结构的递推DP 的三个核心概念——最优子结构、重叠子问题、无后效性——教科书上都有定义但理解它们的关键在于用代码直觉去翻译。最优子结构翻译成代码直觉如果你能用一个递归函数f(state)表示从state出发的最优解且f的计算只依赖更小的子问题的f值那么这个问题就有最优子结构。反例求图中的最长简单路径没有最优子结构因为子路径的最优不一定组成全局最优。重叠子问题翻译成代码直觉如果你画出递归树发现很多节点的状态参数一模一样那就不用犹豫上记忆化搜索或 DP 表。如果递归树的每个节点状态都不同如快速排序那 DP 就不适用。无后效性翻译成代码直觉状态定义之后从该状态到终点的最优决策与怎么到达这个状态无关。换句话说状态本身包含了做后续决策所需的全部信息。这三个条件满足时DP 的解题框架就固定下来了定义状态 → 找状态转移 → 确定初始化 → 决定遍历顺序 → 返回目标状态。三、生产级代码实现与最佳实践五类 DP 模板 复杂度论证 DP 题型分类模板库 每类题型包含识别特征 状态定义 转移方程 复杂度分析 工程级代码 所有注释解释为什么这样设计而非这行代码做什么 from typing import List # 类型一线性 DP以打家劫舍 II 为例 def rob_circle(nums: List[int]) - int: LeetCode 213打家劫舍 II环形数组 时间复杂度O(n)遍历两次数组 空间复杂度O(1)只用 3 个变量滚动更新 环形问题的通用处理方式分成选头不选尾和选尾不选头两个子问题 为什么不选择更多分割因为环只有一个断点两种划分就能覆盖所有可能 if len(nums) 1: return nums[0] def rob_linear(arr: List[int]) - int: 线性版本的打家劫舍 —— 空间优化的关键是只保留前两个状态 prev2 prev1 0 # prev2 dp[i-2]prev1 dp[i-1] for val in arr: # dp[i] max(dp[i-1], dp[i-2] val) # 当前不偷继承前一个vs 偷当前加上前前个 current max(prev1, prev2 val) prev2, prev1 prev1, current return prev1 return max( rob_linear(nums[:-1]), # case1不偷最后一间 rob_linear(nums[1:]), # case2不偷第一间 ) # 类型二0-1 背包 def can_partition(nums: List[int]) - bool: LeetCode 416分割等和子集0-1 背包变种 时间复杂度O(n * sum/2)n 为数组长度 空间复杂度O(sum/2)使用一维 DP 优化倒序遍历避免覆盖 为什么倒序因为 0-1 背包每个物品只能用一次 正序遍历会导致同一个物品被重复使用变成完全背包 total sum(nums) if total % 2 ! 0: return False # 总和为奇数不可能等分 target total // 2 # dp[j] 表示能否选出和为 j 的子集 dp [False] * (target 1) dp[0] True # 空子集和为 0 for num in nums: # 倒序遍历保证每个 num 只用一次 for j in range(target, num - 1, -1): dp[j] dp[j] or dp[j - num] return dp[target] # 类型三区间 DP def max_coins(nums: List[int]) - int: LeetCode 312戳气球 时间复杂度O(n³)三重循环 空间复杂度O(n²)区间 DP 的 dp 表 区间 DP 的关键洞察定义 dp[i][j] 为区间 (i, j) 的气球被戳完后的最大得分 为什么要空区间因为这样边界条件就是 dp[i][i1] 0区间内没有气球 最后一个被戳的气球把问题分成了两个独立的子区间 # 在首尾添加 1处理边界第一个和最后一个气球被戳时的得分计算 nums [1] nums [1] n len(nums) dp [[0] * n for _ in range(n)] # length 从 2 开始至少包含一个气球即一个 nums 元素在区间中 for length in range(2, n): for left in range(n - length): right left length # 枚举区间内最后一个被戳的气球位置 for k in range(left 1, right): # 在区间 [left, right] 中k 是最后一个被戳的 # 戳 k 时它的邻居是 left 和 right因为区间内其他气球已被戳完 coins nums[left] * nums[k] * nums[right] dp[left][right] max( dp[left][right], dp[left][k] dp[k][right] coins, # 左子区间 右子区间 戳 k 得分 ) # dp[0][n-1] 表示区间 (0, n-1)即全部气球 return dp[0][n - 1] # 类型四状态压缩 DP def min_cost_tsp(graph: List[List[int]]) - int: 旅行商问题TSP的状态压缩 DP 解法 时间复杂度O(n² * 2ⁿ) 空间复杂度O(n * 2ⁿ) 状态压缩的适用场景n 很小通常 n ≤ 20且状态需要记录哪些元素已被使用 使用 bitmask 表示集合第 i 位为 1 表示节点 i 已被访问 dp[mask][i] 表示访问了 mask 表示的节点集合当前在节点 i 的最小代价 n len(graph) INF float(inf) # dp[mask][i]mask 是位掩码集合i 是当前所在节点 dp [[INF] * n for _ in range(1 n)] dp[1][0] 0 # 从节点 0 出发mask1只有节点 0 被访问 for mask in range(1 n): for i in range(n): if dp[mask][i] INF: continue # 当前状态不可达跳过 for j in range(n): if mask (1 j): # 节点 j 已在集合中 continue new_mask mask | (1 j) # 加入节点 j dp[new_mask][j] min( dp[new_mask][j], dp[mask][i] graph[i][j], ) # 回到起点 0 的最小代价 full_mask (1 n) - 1 return int(min(dp[full_mask][i] graph[i][0] for i in range(n)))每类 DP 的核心差异不在代码量而在状态定义的维度。线性 DP 的状态是一维下标背包 DP 的状态是一维容量区间 DP 的状态是二维区间端点状态压缩 DP 的状态是位掩码。掌握了这个维度规律看到新题就能快速归类。四、边界分析与架构权衡DP vs 贪心 vs 回溯DP 不是万能的它有三个替代方案需要权衡贪心当问题满足贪心选择性质局部最优能推导全局最优时贪心比 DP 更高效。例如活动选择问题DP 是 O(n²)贪心是 O(n log n)。识别方法看能否构造反例。如果能想到一个反例证明选当前最优不一定是全局最优那就不能用贪心。回溯DFS 剪枝当 n 很小且状态转移很难用 DP 表达时回溯更合适。比如N 皇后问题每一步的决策依赖前几步的具体布局而非状态摘要DP 很难建模回溯反而直接。记忆化搜索这是 DP 自顶向下的实现方式比填表法更直观但可能有递归栈溢出风险。当状态转移方向不明确比如图 DP时记忆化搜索更自然。选择 DP 的场景是状态维度可控不爆表转移规则清晰能写成方程问题规模足够大回溯会超时。三者同时满足DP 就是第一选择。五、总结DP 的难点不在于某道题的代码写不出来而在于这道题属于哪一种 DP——这个判断决定了你从哪个角度切入。7 月通过分类训练我建立了一个从看到题就发懵到先分类再建模的思维转变。将 DP 题归类后每一类都有固定的状态定义模式和转移套路。0-1 背包的选或不选、区间 DP 的枚举分割点、状态压缩 DP 的位掩码集合——这些都是可复用的思维模块。剩下的工作就是在模板基础上适配题目细节。练 DP不需要求多需要求通。把每一类 DP 的经典题做到能在白板上从头推导比刷 100 道杂题更有意义。