动态规划题单

一、基础入门题（必刷）

1. 斐波那契数列类

• 509. 斐波那契数 (Easy)
• 70. 爬楼梯 (Easy) ⭐⭐⭐
• 746. 使用最小花费爬楼梯 (Easy)
• 198. 打家劫舍 (Medium) ⭐⭐⭐
• 213. 打家劫舍 II (Medium)
• 337. 打家劫舍 III (Medium)

2. 路径问题

• 62. 不同路径 (Medium) ⭐⭐⭐
• 63. 不同路径 II (Medium)
• 64. 最小路径和 (Medium) ⭐⭐⭐
• 120. 三角形最小路径和 (Medium)
• 931. 下降路径最小和 (Medium)

二、背包问题（核心重点）

1. 0-1背包

• 416. 分割等和子集 (Medium) ⭐⭐⭐⭐
• 494. 目标和 (Medium) ⭐⭐⭐
• 474. 一和零 (Medium)
• 1049. 最后一块石头的重量 II (Medium)

2. 完全背包

• 322. 零钱兑换 (Medium) ⭐⭐⭐⭐
• 518. 零钱兑换 II (Medium) ⭐⭐⭐
• 377. 组合总和 Ⅳ (Medium)
• 279. 完全平方数 (Medium)
• 139. 单词拆分 (Medium) ⭐⭐⭐

3. 多重背包

• 1155. 掷骰子的N种方法 (Medium)

三、子序列问题（高频考点）

1. 最长递增子序列

• 300. 最长递增子序列 (Medium) ⭐⭐⭐⭐⭐
• 674. 最长连续递增序列 (Easy)
• 718. 最长重复子数组 (Medium)
• 1143. 最长公共子序列 (Medium) ⭐⭐⭐⭐
• 1035. 不相交的线 (Medium)

2. 编辑距离

• 72. 编辑距离 (Hard) ⭐⭐⭐⭐⭐
• 583. 两个字符串的删除操作 (Medium)
• 712. 两个字符串的最小ASCII删除和 (Medium)

3. 回文子序列

• 516. 最长回文子序列 (Medium) ⭐⭐⭐
• 647. 回文子字符串 (Medium)
• 5. 最长回文子串 (Medium) ⭐⭐⭐

四、股票问题（经典系列）

• 121. 买卖股票的最佳时机 (Easy) ⭐⭐⭐⭐
• 122. 买卖股票的最佳时机 II (Medium) ⭐⭐⭐
• 123. 买卖股票的最佳时机 III (Hard) ⭐⭐⭐
• 188. 买卖股票的最佳时机 IV (Hard)
• 309. 最佳买卖股票时机含冷冻期 (Medium) ⭐⭐⭐
• 714. 买卖股票的最佳时机含手续费 (Medium)

五、区间DP（进阶题型）

• 96. 不同的二叉搜索树 (Medium) ⭐⭐⭐
• 312. 戳气球 (Hard) ⭐⭐⭐⭐
• 1039. 多边形三角剖分的最低得分 (Medium)
• 375. 猜数字大小 II (Medium)

六、状态机DP

• 10. 正则表达式匹配 (Hard) ⭐⭐⭐⭐
• 44. 通配符匹配 (Hard)
• 115. 不同的子序列 (Hard)
• 97. 交错字符串 (Medium)

七、树形DP

• 124. 二叉树中的最大路径和 (Hard) ⭐⭐⭐⭐
• 543. 二叉树的直径 (Easy)
• 687. 最长同值路径 (Medium)
• 968. 监控二叉树 (Hard)

八、数位DP

• 233. 数字1的个数 (Hard)
• 357. 统计各位数字都不同的数字个数 (Medium)
• 902. 最大为 N 的数字组合 (Hard)

九、概率DP

• 688. 骑士在棋盘上的概率 (Medium)
• 837. 新21点 (Medium)

十、面试必备模板

1. 一维DP模板

# 基础一维DP
dp = [0] * (n + 1)
dp[0] = 初始值
for i in range(1, n + 1):
    dp[i] = 状态转移方程
return dp[n]

2. 二维DP模板

# 基础二维DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
# 初始化
for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = 状态转移方程
return dp[n][m]

3. 背包问题模板

# 0-1背包
dp = [0] * (target + 1)
for num in nums:
    for j in range(target, num - 1, -1):
        dp[j] = max(dp[j], dp[j - num] + num)

# 完全背包
dp = [0] * (target + 1)
for num in nums:
    for j in range(num, target + 1):
        dp[j] = max(dp[j], dp[j - num] + num)

刷题建议

1. 按顺序刷题：从基础入门题开始，逐步提升难度
2. 重点关注：标记⭐⭐⭐以上的题目为面试高频题
3. 总结模板：每种类型都要掌握对应的模板和套路
4. 反复练习：动态规划需要大量练习才能熟练掌握
5. 时间分配：建议每天2-3道题，持续练习1-2个月

面试技巧

1. 状态定义要清晰：明确dp[i]或dp[i][j]代表什么
2. 状态转移方程推导：从小规模问题开始分析
3. 边界条件处理：注意初始化和边界情况
4. 空间优化：能用一维数组就不用二维数组
5. 时间复杂度分析：要能准确分析算法复杂度