动态规划在LeetCode高频题中的应用与技巧

发布时间：2026/10/26 4:51:37

1. 为什么动态规划是LeetCode Hot 100的必考题型

动态规划（Dynamic Programming）作为算法领域的核心方法论，在LeetCode Hot 100中占比超过20%。2023年最新统计显示，Amazon和Google的面试题库中，动态规划题目出现频率高达34%。这种算法之所以成为大厂面试的"常客"，根本原因在于它能完美考察候选人的三个核心能力：

问题拆解能力：将复杂问题分解为重叠子问题的思维模式
状态定义能力：设计dp数组结构的抽象建模水平
转移方程推导：找出最优子结构的数学归纳技巧

以经典的"爬楼梯"问题为例，表面看是简单的排列组合，实则暗含斐波那契数列的动态规划本质。当楼梯阶数n=10时，暴力解法需要O(2^n)时间复杂度，而DP解法仅需O(n)时间复杂度和O(1)空间复杂度。这种效率的指数级提升，正是面试官最看重的算法优化能力。

关键认知：动态规划不是一种具体算法，而是一种通过"记忆化存储"来优化递归的思想。理解这一点才能避免陷入死记硬背模板的误区。

2. Hot 100动态规划题库的四大类型解析

2.1 线性序列问题

这类问题的输入通常是数组或字符串，状态转移沿着单一维度进行。LeetCode 70.爬楼梯就是典型代表，其状态转移方程为：

dp[i] = dp[i-1] + dp[i-2] # 到达第i阶的方法数

实战中容易忽略的细节是初始条件设置。比如当n=0时应返回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]*(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]

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-i<3 or dp[i+1][j-1])

实际编码时需要注意遍历顺序——应该按子串长度而非下标顺序遍历：

for L in range(n): for i in range(n-L): j = i+L # 更新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(i+1,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, K+1): 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, n+1): 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，建议用格式化输出保持对齐，便于观察状态转移过程。