LeetCode 高频题解深度剖析：动态规划与图论的完整思路推导

LeetCode 高频题解深度剖析动态规划与图论的完整思路推导一、引言痛点刷题中的一看就会一写就废动态规划和图论是 LeetCode 高频考点也是面试中最能区分候选人水平的题型。这两类题目的共同特点是解题思路一旦想到实现往往并不复杂但找到正确思路的过程本身就需要大量练习和系统性总结。一看就会一写就废是大多数刷题者的困境。问题的根源在于缺乏完整的思路推导框架——拿到一道新题时不知道从何处入手分析不知道何时该用 DP 何时该用图论算法更不知道状态转移方程应该如何设计。本文将以 LeetCode 高频题为例系统讲解动态规划和图论各类题型的分析框架和解题套路帮助读者建立问题识别-思路推导-代码实现的完整能力链条。二、动态规划深度剖析2.1 DP 问题识别框架动态规划并非凭空出现的魔法而是解决特定类型问题的方法论。识别一道题是否适合用 DP 求解需要关注以下特征flowchart TD A[问题特征] -- B{能否拆分br/子问题?} B --|是| C{子问题是否br/有重叠?} C --|是| D{能否定义br/最优子结构?} D --|是| E[适合用 DP] B --|否| F[可能用贪心br/或分治] C --|否| G[可能用br/分治递归]最优子结构问题的最优解可以由其子问题的最优解构造。重叠子问题递归过程中会重复计算相同的子问题。2.2 经典 DP 问题分类与思路2.2.1 线性 DP状态随线性变量转移# LeetCode 300. 最长递增子序列 def length_of_lIS(nums: list[int]) - int: 思路推导 1. 状态定义dp[i] 以第 i 个元素结尾的最长递增子序列长度 2. 状态转移dp[i] max(dp[j] 1) for j i where nums[j] nums[i] 3. 初始状态dp[i] 1每个元素自身就是一个子序列 4. 最终答案max(dp) 复杂度O(n²) 朴素 DP可优化为 O(n log n) 使用二分 if not nums: return 0 n len(nums) dp [1] * n # dp[i] 表示以 nums[i] 结尾的最长递增子序列长度 for i in range(n): for j in range(i): if nums[j] nums[i]: # 在所有比 nums[i] 小的元素中找最长的递增子序列 dp[i] max(dp[i], dp[j] 1) return max(dp) # LeetCode 1143. 最长公共子序列 def longest_common_subsequence(text1: str, text2: str) - int: 思路推导 1. 状态定义dp[i][j] text1[0..i-1] 与 text2[0..j-1] 的最长公共子序列长度 2. 状态转移 - 若 text1[i-1] text2[j-1]dp[i][j] dp[i-1][j-1] 1 - 否则dp[i][j] max(dp[i-1][j], dp[i][j-1]) 3. 空间优化从二维压缩到一维 复杂度O(mn) 时间O(min(m,n)) 空间 m, n len(text1), len(text2) # 空间优化只用两行 prev [0] * (n 1) curr [0] * (n 1) for i in range(1, m 1): for j in range(1, n 1): if text1[i - 1] text2[j - 1]: curr[j] prev[j - 1] 1 else: curr[j] max(prev[j], curr[j - 1]) prev, curr curr, prev return prev[n]2.2.2 区间 DP状态表示一个区间# LeetCode 516. 最长回文子序列 def longest_palindromic_subsequence(s: str) - int: 思路推导区间 DP 1. 状态定义dp[i][j] s[i..j] 范围内最长回文子序列长度 2. 状态转移 - 若 s[i] s[j]dp[i][j] dp[i1][j-1] 2 - 否则dp[i][j] max(dp[i1][j], dp[i][j-1]) 3. 遍历顺序小区间 - 大区间i 从大到小j 从小到大 区间 DP 通用模板 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 # 处理 dp[i][j] n len(s) if n 0: return 0 dp [[0] * n for _ in range(n)] # 单个字符是回文长度为 1 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]: if length 2: dp[i][j] 2 else: 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]2.3 DP 空间优化技巧# 状态压缩从 O(n²) 空间优化到 O(n) 或 O(1) def space_optimization_patterns(): 空间优化的常见模式 1. 二维 DP 压缩为一维 适用于当前状态只依赖上一行和左边元素的情况 - 从左到右遍历prev[i-1] 是当前行左边的值 - 从右到左遍历prev[i] 是上一行的值 # 一维 DP 示例0-1 背包问题 def knapSack_dp(W: int, weights: list[int], values: list[int]) - int: 0-1 背包问题 原始二维dp[i][w] 前 i 个物品容量 w 时的最大价值 空间优化dp[w] 容量 w 时的最大价值 关键内层循环从大到小遍历避免重复选择同一物品 n len(weights) dp [0] * (W 1) for i in range(n): # 从大到小遍历保证每个物品只被选择一次 for w in range(W, weights[i] - 1, -1): dp[w] max(dp[w], dp[w - weights[i]] values[i]) return dp[W] # 状态压缩框架伪代码 def dp_with_space_compression(): 二维转一维的判断条件 - dp[i][j] 只依赖 dp[i-1][j] 和 dp[i-1][j-1] 或 dp[i][j-1] - 从左到右遍历时需要先保存 prev[j-1]当前行左边 - 从右到左遍历时prev[j-1] 在上一行无需特殊处理 # 框架代码 def dp_2d_to_1d(grid): m, n len(grid), len(grid[0]) dp [0] * n for i in range(m): # 从右到左遍历典型场景 for j in range(n - 1, -1, -1): if i 0 and j 0: dp[j] grid[i][j] elif i 0: dp[j] dp[j - 1] grid[i][j] # 只能从左边来 elif j 0: dp[j] dp[j] grid[i][j] # 只能从上边来 else: dp[j] min(dp[j], dp[j - 1]) grid[i][j] # 从上或左来 return dp[n - 1] return dp_2d_to_1d三、图论算法深度剖析3.1 图的遍历框架flowchart TD A[图遍历] -- B[DFS 深度优先] A -- C[BFS 广度优先] B -- B1[递归实现] B -- B2[栈实现] C -- C1[队列实现] B1 -- B3[回溯/剪枝] B2 -- B4[迭代遍历] C1 -- C2[最短路径]from collections import deque from typing import List, Optional class Graph: 图的两种表示方式 def __init__(self, n: int, edges: List[List[int]]): # 邻接表 self.adj [[] for _ in range(n)] for u, v in edges: self.adj[u].append(v) # 无向图self.adj[v].append(u) # BFS 模板 def bfs(self, start: int) - List[int]: BFS 遍历 适用于最短路径、无权图层级遍历 时间复杂度O(V E) visited [False] * len(self.adj) result [] queue deque([start]) visited[start] True while queue: node queue.popleft() result.append(node) for neighbor in self.adj[node]: if not visited[neighbor]: visited[neighbor] True queue.append(neighbor) return result # DFS 模板递归 def dfs_recursive(self, start: int) - List[int]: DFS 递归遍历 适用于连通分量、拓扑排序、路径搜索 visited [False] * len(self.adj) result [] def dfs(node: int): visited[node] True result.append(node) for neighbor in self.adj[node]: if not visited[neighbor]: dfs(neighbor) dfs(start) return result # DFS 迭代栈 def dfs_iterative(self, start: int) - List[int]: visited [False] * len(self.adj) result [] stack [start] while stack: node stack.pop() if visited[node]: continue visited[node] True result.append(node) for neighbor in self.adj[node]: if not visited[neighbor]: stack.append(neighbor) return result3.2 最短路径算法族import heapq from typing import List, Tuple class ShortestPath: 最短路径算法集合 适用场景对比 - BFS无权图单源最短路O(V E) - Dijkstra有非负权单源最短路O(E log V) - Bellman-Ford可负权单源最短路O(VE) - Floyd-Warshall任意起终点全源最短路O(V³) staticmethod def dijkstra( n: int, edges: List[List[int]], source: int ) - List[int]: Dijkstra 算法堆优化 核心思想 1. 用最小堆维护 (距离, 节点) 2. 每次取出最小距离节点 3. 松弛该节点的所有出边 4. 若新距离更短则加入堆 局限性无法处理负权边负权会导致重复松弛 # 构建邻接表(neighbor, weight) adj [[] for _ in range(n)] for u, v, w in edges: adj[u].append((v, w)) dist [float(inf)] * n dist[source] 0 min_heap [(0, source)] # (距离, 节点) while min_heap: d, u heapq.heappop(min_heap) if d dist[u]: # 跳过过时条目 continue for v, weight in adj[u]: new_dist dist[u] weight if new_dist dist[v]: dist[v] new_dist heapq.heappush(min_heap, (new_dist, v)) return dist staticmethod def bellman_ford( n: int, edges: List[List[int]], source: int ) - Optional[List[int]]: Bellman-Ford 算法 核心思想 1. 进行 V-1 轮松弛操作 2. 每轮松弛所有边 3. 第 V 轮若仍有更新则存在负环 适用场景 - 检测负权环 - 边权可为负的最短路径 dist [float(inf)] * n dist[source] 0 # V-1 轮松弛 for _ in range(n - 1): updated False for u, v, w in edges: if dist[u] ! float(inf) and dist[u] w dist[v]: dist[v] dist[u] w updated True if not updated: break # 提前终止优化 # 第 V 轮检测负环 for u, v, w in edges: if dist[u] ! float(inf) and dist[u] w dist[v]: return None # 存在负环无最短路 return dist3.3 拓扑排序与关键路径from collections import deque class TopologicalSort: 拓扑排序 应用场景 1. 课程表先修依赖 2. 任务调度 3. 编译顺序 4. 关键路径分析 Kahn 算法BFS 实现 1. 计算所有节点入度 2. 将入度为 0 的节点入队 3. 取出队首输出并将其邻接点入度 -1 4. 若邻接点入度变为 0则入队 staticmethod def kahn(n: int, edges: List[List[int]]) - Optional[List[int]]: Kahn 算法 返回拓扑排序结果若存在环则返回 None adj [[] for _ in range(n)] in_degree [0] * n for u, v in edges: adj[u].append(v) in_degree[v] 1 queue deque([i for i in range(n) if in_degree[i] 0]) result [] while queue: u queue.popleft() result.append(u) for v in adj[u]: in_degree[v] - 1 if in_degree[v] 0: queue.append(v) # 若结果数量不等于节点数说明存在环 return result if len(result) n else None staticmethod def dfs_version(n: int, edges: List[List[int]]) - Optional[List[int]]: DFS 版本拓扑排序 核心思想在 DFS 返回时将节点加入结果 后序遍历的逆序即为拓扑序 adj [[] for _ in range(n)] for u, v in edges: adj[u].append(v) VISITING 1 VISITED 2 state [0] * n result [] def dfs(u: int) - bool: 返回是否存在环 state[u] VISITING for v in adj[u]: if state[v] VISITING: return False # 存在环 if state[v] 0 and not dfs(v): return False state[u] VISITED result.append(u) # 后序位置加入 return True for i in range(n): if state[i] 0: if not dfs(i): return None # 存在环 return result[::-1] # 逆序得到拓扑序四、Trade-offs 分析4.1 DP 时间复杂度的优化路径原始复杂度优化后适用条件典型题目O(n²)O(n log n)LIS 问题300. 最长递增子序列O(nm)O(n m)编辑距离等72. 编辑距离O(2ⁿ)O(n·W)0-1 背包经典背包问题4.2 图算法选型决策树flowchart TD A[求最短路径?] -- B{是否有环?} A -- C{边权是否负?} B --|无环| D[拓扑排序 DP] B --|有环| C C --|全正| E[Dijkstra] C --|可有负| F{Bellman-Fordbr/检测负环?} C --|全相同| G[BFS] F --|是| H[bellman_ford] F --|否| I[Dijkstra]五、总结动态规划和图论题目的解题能力需要通过系统训练逐步建立。以下三点是高效刷题的关键第一建立问题识别框架。不是所有优化问题都是 DP不是所有图问题都用 Dijkstra。通过识别问题的特征最优子结构、重叠子问题、负权边选择合适的算法。第二从暴力到优化的演进路径。面对新题时先尝试暴力递归可能带备忘录再优化为迭代 DP。很多 DP 题目可以直接从暴力版本演变而来。第三模板化与套路总结。将常见题型如背包问题、LIS、LCS、区间 DP、拓扑排序总结为固定套路形成肌肉记忆。刷题的目的是建立思维框架而非记忆答案。