面试真题分类

按难度分类

整理 LeetCode 高频 DP 面试题，方便针对性练习。

---

简单难度 ⭐

题号	题目	类型	关键词
70	爬楼梯	**基础问题**	斐波那契
509	斐波那契数	**基础问题**	一维DP
118	杨辉三角	序列	路径压缩
198	打家劫舍	**基础问题**	一维DP
413	等差数列划分	序列	差分思想
256	粉刷房子	路径	行状态
121	买卖股票最佳时机	**股票问题**	单次交易
746	使用最小花费爬楼梯	**基础问题**	一维DP

---

中等难度 ⭐⭐

序列DP

题号	题目	类型
300	最长递增子序列	**序列问题**
1143	最长公共子序列	**序列问题**
72	编辑距离	**序列问题**
516	最长回文子序列	序列
5	最长回文子串	区间
647	回文子串个数	区间

背包DP

题号	题目	类型
416	分割等和子集	0/1背包
494	目标和	0/1背包
474	一和零	二维背包
518	零钱兑换 II	完全背包
322	零钱兑换	完全背包+最少硬币
377	组合总和 IV	完全背包
139	单词拆分	完全背包

路径DP

题号	题目	类型
62	不同路径	**路径问题**
63	不同路径 II	**路径问题**
64	最小路径和	**路径问题**
120	三角形最小路径和	**路径问题**
174	地下城游戏	**路径问题**

股票DP

题号	题目	类型
122	买卖股票最佳时机 II	**股票问题**
123	买卖股票最佳时机 III	**股票问题**
188	买卖股票最佳时机 IV	**股票问题**
309	最佳买卖股票含冷冻期	**股票问题**
714	买卖股票含手续费	**股票问题**

区间DP

题号	题目	类型
516	最长回文子序列	区间
131	分割回文串	区间
312	戳气球	**区间DP**
375	猜数字大小 II	博弈
486	预测赢家	博弈

树形DP

题号	题目	类型
124	二叉树最大路径和	**树形DP**
337	打家劫舍 III	**树形DP**
543	二叉树直径	**树形DP**
687	最长同值路径	树形

状态压缩

题号	题目	类型
698	划分为k个相等的子集	**状态压缩DP**
473	火柴拼正方形	**状态压缩DP**
526	优美的排列	状态压缩

---

困难难度 ⭐⭐⭐

题号	题目	类型
10	正则表达式匹配	序列
72	编辑距离	**序列问题**
174	地下城游戏	**路径问题**
329	矩阵中的最长递增路径	DAG/记忆化
354	俄罗斯套娃信封	LIS二维
410	分割数组的最大值	二分+DP
514	自由之路	状态压缩+字符串
741	摘樱桃	路径+状态

---

按公司分类

Google

• 10, 72, 124, 300, 312, 329, 410

Meta/Facebook

• 1143, 312, 410, 514, 741

Amazon

• 300, 1143, 416, 494, 198

Microsoft

• 72, 1143, 64, 96

---

核心套路总结

[!abstract] 面试常见模式 80% 的 DP 面试题可以用以下模板解决：

// 通用 DP 框架
function dpTemplate(dp, ...) {
  // 1. 确定状态 - 最后一步是什么？
  // 2. 转移方程 - dp[i] = ...
  // 3. 初始条件 - dp[0] = ...
  // 4. 计算顺序 - for i in range(n)

  // 空间优化（可选）
  // 滚动数组 / 一维降维
}

高频考点

考点	出现频率
序列 LIS/LCS	30%
背包DP	25%
路径DP	20%
股票DP	15%
其他	10%

---

参见: **DP算法索引** | **刷题指南**