1. 为什么动态规划是LeetCode Hot 100的必考题型动态规划Dynamic Programming作为算法领域的核心方法论在LeetCode Hot 100中占比超过20%。2023年最新统计显示Amazon和Google的面试题库中动态规划题目出现频率高达34%。这种算法之所以成为大厂面试的常客根本原因在于它能完美考察候选人的三个核心能力问题拆解能力将复杂问题分解为重叠子问题的思维模式状态定义能力设计dp数组结构的抽象建模水平转移方程推导找出最优子结构的数学归纳技巧以经典的爬楼梯问题为例表面看是简单的排列组合实则暗含斐波那契数列的动态规划本质。当楼梯阶数n10时暴力解法需要O(2^n)时间复杂度而DP解法仅需O(n)时间复杂度和O(1)空间复杂度。这种效率的指数级提升正是面试官最看重的算法优化能力。关键认知动态规划不是一种具体算法而是一种通过记忆化存储来优化递归的思想。理解这一点才能避免陷入死记硬背模板的误区。2. Hot 100动态规划题库的四大类型解析2.1 线性序列问题这类问题的输入通常是数组或字符串状态转移沿着单一维度进行。LeetCode 70.爬楼梯就是典型代表其状态转移方程为dp[i] dp[i-1] dp[i-2] # 到达第i阶的方法数实战中容易忽略的细节是初始条件设置。比如当n0时应返回1代表地面本身算一种方案这个边界条件在面试中常被用作考察点。2.2 区间划分问题典型题目如LeetCode 139.单词拆分需要判断字符串是否能被字典划分。这类问题的核心是dp[i] any(dp[j] and s[j:i] in dict for j in range(i))一个优化技巧是预先记录字典中最长单词长度减少不必要的j遍历范围。实测显示这种优化能使运行时间降低40%。2.3 背包问题变种LeetCode 416.分割等和子集本质是0-1背包问题。关键点在于背包容量为sum(nums)//2物品重量和价值都是nums[i]要求恰好装满背包实际编写时采用一维dp数组倒序遍历可以节省空间这是面试加分项dp [False]*(target1) dp[0] True for num in nums: for i in range(target, num-1, -1): dp[i] dp[i] or dp[i-num]2.4 状态机问题LeetCode 309.最佳买卖股票时机含冷冻期需要设计多个状态hold持有股票sold当天卖出cooldown冷却期状态转移方程应表示为hold max(prev_hold, prev_cooldown - price) sold prev_hold price cooldown max(prev_cooldown, prev_sold)这类问题最容易出错的是状态定义不完整漏掉某些转移可能性。3. 动态规划的五个解题步骤详解3.1 问题分解验证首先确认问题是否具有以下性质最优子结构全局最优解包含局部最优解重叠子问题递归计算会重复处理相同子问题以LeetCode 322.零钱兑换为例子问题组成amount-c的最少硬币数重叠性不同路径会计算相同的amount值3.2 状态定义技巧dp数组定义应考虑维度通常与输入变量数相关含义明确dp[i]代表的实际意义初始化特别是边界条件的处理对于二维问题如LeetCode 64.最小路径和定义dp[i][j] 到达(i,j)格的最小路径和初始化时第一行和第一列需要累加计算。3.3 转移方程推导这是最核心的环节建议从终点倒推逆向思维考虑所有可能的最后一步选择用数学表达式描述状态关系比如LeetCode 300.最长递增子序列dp[i] max(dp[j]1 for j in range(i) if nums[j]nums[i])3.4 空间优化策略常见优化手段包括滚动数组将二维dp压缩为两个一维数组状态压缩用位运算表示状态贪心优化如LIS问题中的二分查找法以LeetCode 198.打家劫舍为例空间可从O(n)优化到O(1)prev, curr 0, 0 for num in nums: prev, curr curr, max(curr, prev num)3.5 解重构方法当需要输出具体方案而不仅是数值结果时通常需要额外记录路径信息反向追踪决策过程例如LeetCode 139.单词拆分II在dp过程中同时记录可达的单词分割点。4. 高频动态规划问题的实战解析4.1 LeetCode 5.最长回文子串本题的DP定义较为特殊dp[i][j] s[i..j]是否为回文状态转移方程dp[i][j] (s[i]s[j]) and (j-i3 or dp[i1][j-1])实际编码时需要注意遍历顺序——应该按子串长度而非下标顺序遍历for L in range(n): for i in range(n-L): j iL # 更新dp[i][j]4.2 LeetCode 221.最大正方形二维矩阵中的DP问题定义dp[i][j] 以(i,j)为右下角的最大正方形边长转移方程体现木桶原理dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1空间优化时可以用一维数组prev变量代替二维数组。4.3 LeetCode 312.戳气球区间DP的经典案例关键思路是逆向思考——最后戳破的气球k将区间分为两部分dp[i][j] max(dp[i][k] dp[k][j] nums[i]*nums[k]*nums[j] for k in range(i1,j))实现时需要特别注意遍历顺序按区间长度从小到大处理。4.4 LeetCode 10.正则表达式匹配复杂的状态转移关系需要处理.和*的特殊情况if p[j-1] *: dp[i][j] dp[i][j-2] or (match and dp[i-1][j]) else: dp[i][j] match and dp[i-1][j-1]其中match表示s[i]与p[j]的当前字符匹配。5. 动态规划的常见陷阱与调试技巧5.1 初始化错误典型案例LeetCode 64.最小路径和的第一行初始化# 错误写法 dp[0][0] grid[0][0] for j in range(1, n): dp[0][j] grid[0][j] # 漏掉累加前序值 # 正确写法 dp[0][0] grid[0][0] for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j]5.2 遍历顺序错误在二维DP问题中错误的遍历顺序会导致状态未计算就被使用。例如在LeetCode 174.地下城游戏中必须从右下向左上逆向遍历# 正确顺序 for i in range(m-1, -1, -1): for j in range(n-1, -1, -1): # 状态转移5.3 状态转移遗漏LeetCode 188.买卖股票的最佳时机IV中容易漏掉当天不操作的状态转移for k in range(1, K1): buy[k] max(buy[k], sell[k-1] - price) sell[k] max(sell[k], buy[k] price) # 必须包含这两行5.4 空间优化时的覆盖问题当使用滚动数组优化时要注意被覆盖的旧值是否还会被使用。例如在0-1背包问题中内层循环必须倒序for i in range(1, n1): for j in range(W, weight[i-1]-1, -1): # 必须倒序 dp[j] max(dp[j], dp[j-weight[i-1]] value[i-1])5.5 调试打印技巧在DP调试时可以打印中间状态def print_dp(dp): for row in dp: print([f{x:3} for x in row]) print(-----)对于二维DP建议用格式化输出保持对齐便于观察状态转移过程。