1. LeetCode Hot 100 动态规划专题解析动态规划Dynamic Programming是算法面试中的高频考点也是LeetCode Hot 100中的重点题型。这个专题将深入剖析动态规划的核心解题思路通过典型例题帮助掌握这一重要算法范式。动态规划本质上是一种空间换时间的优化技术通过将问题分解为相互重叠的子问题并存储子问题的解来避免重复计算。在LeetCode Hot 100中动态规划问题占比约15-20%是必须掌握的算法类型。2. 动态规划解题框架2.1 动态规划三要素任何动态规划问题都包含三个核心要素最优子结构问题的最优解包含子问题的最优解重叠子问题递归求解时会重复计算相同的子问题状态转移方程定义如何从一个状态推导出下一个状态2.2 解题四步法解决动态规划问题的标准流程定义dp数组的含义确定初始条件(base case)推导状态转移方程确定遍历顺序和边界条件以经典的爬楼梯问题(LeetCode 70)为例dp[i]表示爬到第i阶楼梯的方法数初始条件dp[0]1, dp[1]1状态转移dp[i] dp[i-1] dp[i-2]遍历顺序从i2开始正向遍历3. 典型问题分类解析3.1 单序列问题这类问题的输入通常是一个数组或字符串需要在单维度上进行状态转移。例题最长递增子序列(LeetCode 300)def lengthOfLIS(nums): dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i], dp[j]1) return max(dp)关键点dp[i]表示以nums[i]结尾的最长递增子序列长度双重循环比较所有前面的元素时间复杂度O(n²)可用二分查找优化到O(nlogn)3.2 双序列问题涉及两个输入序列的对比或匹配如字符串编辑距离、最长公共子序列等。例题编辑距离(LeetCode 72)def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): 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], # 删除 dp[i][j-1], # 插入 dp[i-1][j-1] # 替换 ) return dp[m][n]关键点dp[i][j]表示word1前i个字符转换为word2前j个字符的最小操作数初始化第一行和第一列表示空字符串的转换代价状态转移考虑三种操作的最小代价3.3 背包问题经典的背包问题及其变种包括0-1背包、完全背包、多重背包等。例题分割等和子集(LeetCode 416)def canPartition(nums): total sum(nums) if total % 2 ! 0: return False target total // 2 dp [False] * (target 1) dp[0] True for num in nums: for i in range(target, num-1, -1): dp[i] dp[i] or dp[i - num] return dp[target]关键点转化为0-1背包问题背包容量为sum/2dp[i]表示能否凑出和为i的子集内层循环需要倒序避免重复计算3.4 状态机问题这类问题中状态转移较为复杂可能需要定义多个状态或状态转移图。例题买卖股票的最佳时机(LeetCode 121-123系列)# 买卖股票的最佳时机III(LeetCode 123) def maxProfit(prices): buy1 buy2 float(-inf) sell1 sell2 0 for price in prices: buy1 max(buy1, -price) sell1 max(sell1, buy1 price) buy2 max(buy2, sell1 - price) sell2 max(sell2, buy2 price) return sell2关键点维护四个状态变量表示第一次买入/卖出和第二次买入/卖出的最大利润状态转移方程需要考虑前一个状态的影响空间复杂度优化到O(1)4. 动态规划优化技巧4.1 空间复杂度优化许多动态规划问题可以将二维dp数组优化为一维甚至用几个变量表示。示例斐波那契数列def fib(n): if n 2: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b4.2 记忆化搜索自顶向下的递归解法配合缓存有时比自底向上的迭代更直观。示例不同路径II(LeetCode 63)def uniquePathsWithObstacles(grid): m, n len(grid), len(grid[0]) memo {} def dfs(i, j): if (i,j) in memo: return memo[(i,j)] if i m or j n or grid[i][j] 1: return 0 if i m-1 and j n-1: return 1 memo[(i,j)] dfs(i1, j) dfs(i, j1) return memo[(i,j)] return dfs(0, 0)4.3 状态压缩对于状态数量有限的问题可以用位运算等技巧压缩状态表示。示例旅行商问题(TSP)def tsp(graph): n len(graph) VISITED_ALL (1 n) - 1 dp [[float(inf)] * n for _ in range(1n)] for i in range(n): dp[1i][i] 0 for mask in range(1n): for last in range(n): if not (mask (1last)): continue for curr in range(n): if mask (1curr): continue new_mask mask | (1curr) dp[new_mask][curr] min( dp[new_mask][curr], dp[mask][last] graph[last][curr] ) return min(dp[VISITED_ALL][i] graph[i][0] for i in range(n))5. 高频动态规划问题清单5.1 基础必刷题爬楼梯打家劫舍最大子数组和零钱兑换最长递增子序列5.2 进阶挑战题编辑距离不同的子序列分割回文串II地下城游戏戳气球5.3 面试高频题最长回文子串正则表达式匹配最长有效括号单词拆分最大正方形6. 动态规划解题心得识别问题特征当问题具有最优子结构和重叠子问题时考虑动态规划解法。定义状态要明确dp数组的定义直接影响状态转移方程的推导。常见定义方式包括dp[i]以第i个元素结尾的某种最优解dp[i][j]涉及两个序列或两个维度的状态dp[mask]状态压缩表示边界条件很重要初始条件处理不当是常见错误来源特别是dp[0]、dp[1]等初始状态。画状态转移表对于复杂问题手动填写小规模例子的dp表能帮助理解状态转移逻辑。空间优化放在最后先写出清晰的二维dp解法确认正确后再考虑空间优化。注意遍历顺序有些问题需要正向遍历有些需要逆向遍历这取决于状态依赖关系。调试技巧打印dp表是调试动态规划问题的有效方法可以直观看到状态转移是否正确。动态规划的学习曲线较为陡峭建议从简单问题入手逐步建立解题直觉。每解决一个问题后尝试用不同的状态定义重新思考培养多角度分析问题的能力。 
长河君 · 2026/11/2 2:11:36 · 阅读 1.2k LeetCode动态规划核心解析与高频题型攻略
1. LeetCode Hot 100 动态规划专题解析动态规划Dynamic Programming是算法面试中的高频考点也是LeetCode Hot 100中的重点题型。这个专题将深入剖析动态规划的核心解题思路通过典型例题帮助掌握这一重要算法范式。动态规划本质上是一种空间换时间的优化技术通过将问题分解为相互重叠的子问题并存储子问题的解来避免重复计算。在LeetCode Hot 100中动态规划问题占比约15-20%是必须掌握的算法类型。2. 动态规划解题框架2.1 动态规划三要素任何动态规划问题都包含三个核心要素最优子结构问题的最优解包含子问题的最优解重叠子问题递归求解时会重复计算相同的子问题状态转移方程定义如何从一个状态推导出下一个状态2.2 解题四步法解决动态规划问题的标准流程定义dp数组的含义确定初始条件(base case)推导状态转移方程确定遍历顺序和边界条件以经典的爬楼梯问题(LeetCode 70)为例dp[i]表示爬到第i阶楼梯的方法数初始条件dp[0]1, dp[1]1状态转移dp[i] dp[i-1] dp[i-2]遍历顺序从i2开始正向遍历3. 典型问题分类解析3.1 单序列问题这类问题的输入通常是一个数组或字符串需要在单维度上进行状态转移。例题最长递增子序列(LeetCode 300)def lengthOfLIS(nums): dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i], dp[j]1) return max(dp)关键点dp[i]表示以nums[i]结尾的最长递增子序列长度双重循环比较所有前面的元素时间复杂度O(n²)可用二分查找优化到O(nlogn)3.2 双序列问题涉及两个输入序列的对比或匹配如字符串编辑距离、最长公共子序列等。例题编辑距离(LeetCode 72)def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): 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], # 删除 dp[i][j-1], # 插入 dp[i-1][j-1] # 替换 ) return dp[m][n]关键点dp[i][j]表示word1前i个字符转换为word2前j个字符的最小操作数初始化第一行和第一列表示空字符串的转换代价状态转移考虑三种操作的最小代价3.3 背包问题经典的背包问题及其变种包括0-1背包、完全背包、多重背包等。例题分割等和子集(LeetCode 416)def canPartition(nums): total sum(nums) if total % 2 ! 0: return False target total // 2 dp [False] * (target 1) dp[0] True for num in nums: for i in range(target, num-1, -1): dp[i] dp[i] or dp[i - num] return dp[target]关键点转化为0-1背包问题背包容量为sum/2dp[i]表示能否凑出和为i的子集内层循环需要倒序避免重复计算3.4 状态机问题这类问题中状态转移较为复杂可能需要定义多个状态或状态转移图。例题买卖股票的最佳时机(LeetCode 121-123系列)# 买卖股票的最佳时机III(LeetCode 123) def maxProfit(prices): buy1 buy2 float(-inf) sell1 sell2 0 for price in prices: buy1 max(buy1, -price) sell1 max(sell1, buy1 price) buy2 max(buy2, sell1 - price) sell2 max(sell2, buy2 price) return sell2关键点维护四个状态变量表示第一次买入/卖出和第二次买入/卖出的最大利润状态转移方程需要考虑前一个状态的影响空间复杂度优化到O(1)4. 动态规划优化技巧4.1 空间复杂度优化许多动态规划问题可以将二维dp数组优化为一维甚至用几个变量表示。示例斐波那契数列def fib(n): if n 2: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b4.2 记忆化搜索自顶向下的递归解法配合缓存有时比自底向上的迭代更直观。示例不同路径II(LeetCode 63)def uniquePathsWithObstacles(grid): m, n len(grid), len(grid[0]) memo {} def dfs(i, j): if (i,j) in memo: return memo[(i,j)] if i m or j n or grid[i][j] 1: return 0 if i m-1 and j n-1: return 1 memo[(i,j)] dfs(i1, j) dfs(i, j1) return memo[(i,j)] return dfs(0, 0)4.3 状态压缩对于状态数量有限的问题可以用位运算等技巧压缩状态表示。示例旅行商问题(TSP)def tsp(graph): n len(graph) VISITED_ALL (1 n) - 1 dp [[float(inf)] * n for _ in range(1n)] for i in range(n): dp[1i][i] 0 for mask in range(1n): for last in range(n): if not (mask (1last)): continue for curr in range(n): if mask (1curr): continue new_mask mask | (1curr) dp[new_mask][curr] min( dp[new_mask][curr], dp[mask][last] graph[last][curr] ) return min(dp[VISITED_ALL][i] graph[i][0] for i in range(n))5. 高频动态规划问题清单5.1 基础必刷题爬楼梯打家劫舍最大子数组和零钱兑换最长递增子序列5.2 进阶挑战题编辑距离不同的子序列分割回文串II地下城游戏戳气球5.3 面试高频题最长回文子串正则表达式匹配最长有效括号单词拆分最大正方形6. 动态规划解题心得识别问题特征当问题具有最优子结构和重叠子问题时考虑动态规划解法。定义状态要明确dp数组的定义直接影响状态转移方程的推导。常见定义方式包括dp[i]以第i个元素结尾的某种最优解dp[i][j]涉及两个序列或两个维度的状态dp[mask]状态压缩表示边界条件很重要初始条件处理不当是常见错误来源特别是dp[0]、dp[1]等初始状态。画状态转移表对于复杂问题手动填写小规模例子的dp表能帮助理解状态转移逻辑。空间优化放在最后先写出清晰的二维dp解法确认正确后再考虑空间优化。注意遍历顺序有些问题需要正向遍历有些需要逆向遍历这取决于状态依赖关系。调试技巧打印dp表是调试动态规划问题的有效方法可以直观看到状态转移是否正确。动态规划的学习曲线较为陡峭建议从简单问题入手逐步建立解题直觉。每解决一个问题后尝试用不同的状态定义重新思考培养多角度分析问题的能力。