企业官网建设流程全解析

动态规划题型分类与解题套路总结：从入门到工程思维的跃迁

一、深度引言与场景痛点：为什么 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][i+1] = 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 出发，mask=1（只有节点 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 道杂题更有意义。