Interview Prep
面试手撕 DP 板子：线性 / 路径 / 子序列 / 背包 / 字符串 / 股票
DP 面试板子总览：四步法、线性 DP、二维路径 DP、子序列 DP、01 背包与完全背包、字符串 DP、股票 DP，附最小必刷 20 题和完整板子题单。
DP 不像图论只有一个模板，它主要分成几种固定模型：线性、二维路径、子序列、背包、字符串、股票。这篇把这些模型的板子按”dp[i] 是什么 → 初始化 → 转移方程 → 返回”四步法整理在一起，再附上最小必刷 20 题和完整板子题单。
一、DP 最核心理解
DP 本质就是：
一个大问题，可以拆成很多小问题； 小问题的答案可以被复用。
做 DP 题的固定四步：
1. dp[i] 表示什么
2. 初始状态是什么
3. 状态转移方程是什么
4. 最后返回什么代码模板：
vector<int> dp(n, 0);
// 初始化
dp[0] = ...;
// 状态转移
for (int i = 1; i < n; i++) {
dp[i] = ...;
}
// 返回答案
return dp[n - 1];二、线性 DP 板子
1. 爬楼梯模型
典型题：
70 爬楼梯
746 使用最小花费爬楼梯
198 打家劫舍
213 打家劫舍 II70. 爬楼梯
含义：
dp[i] = 爬到第 i 阶的方法数转移：
dp[i] = dp[i - 1] + dp[i - 2];模板：
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) {
return n;
}
vector<int> dp(n + 1, 0);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};2. 打家劫舍模型
典型题：
198 打家劫舍
213 打家劫舍 II
740 删除并获得点数198. 打家劫舍
含义：
dp[i] = 偷到第 i 间房子时，最多能偷多少钱第 i 间有两种选择：
不偷 i：dp[i - 1]
偷 i：dp[i - 2] + nums[i]模板：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) {
return nums[0];
}
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
};三、二维路径 DP 板子
典型题：
62 不同路径
63 不同路径 II
64 最小路径和
120 三角形最小路径和
931 下降路径最小和1. 不同路径
含义：
dp[i][j] = 走到位置 (i, j) 的路径数量转移：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];模板：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};2. 最小路径和
含义：
dp[i][j] = 走到 (i, j) 的最小路径和转移：
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];模板：
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
};四、子序列 DP 板子
这是面试高频。
典型题：
300 最长递增子序列
1143 最长公共子序列
718 最长重复子数组
1035 不相交的线
53 最大子数组和
674 最长连续递增序列1. 最长递增子序列 LIS
300. 最长递增子序列
含义：
dp[i] = 以 nums[i] 结尾的最长递增子序列长度转移：
如果 nums[j] < nums[i]：
dp[i] = max(dp[i], dp[j] + 1)模板：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int ans = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};2. 最长公共子序列 LCS
1143. 最长公共子序列
含义：
dp[i][j] = text1 前 i 个字符 和 text2 前 j 个字符 的最长公共子序列长度注意这里 dp 开 m + 1 和 n + 1，这样边界好写。
模板：
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
};3. 最大子数组和
53. 最大子数组和
含义：
dp[i] = 以 nums[i] 结尾的最大连续子数组和转移：
dp[i] = max(nums[i], dp[i - 1] + nums[i]);模板：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
dp[0] = nums[0];
int ans = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = max(nums[i], dp[i - 1] + nums[i]);
ans = max(ans, dp[i]);
}
return ans;
}
};一句话理解：
前面的和如果是负担，就不要它；如果是收益，就带上它。
五、背包 DP 板子
背包是 DP 里最模板化的一类。
1. 01 背包
每个物品只能选一次。
典型题：
416 分割等和子集
1049 最后一块石头的重量 II
494 目标和
474 一和零一维 01 背包模板
vector<int> dp(bagSize + 1, 0);
for (int i = 0; i < items.size(); i++) {
for (int j = bagSize; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}关键点：
01 背包容量 j 必须倒序遍历因为每个物品只能用一次。
416. 分割等和子集
转化为：
能不能从 nums 里选一些数，使它们的和等于 sum / 2。
模板：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
vector<int> dp(target + 1, 0);
for (int i = 0; i < nums.size(); i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[target] == target;
}
};2. 完全背包
每个物品可以选无限次。
典型题：
322 零钱兑换
518 零钱兑换 II
279 完全平方数
377 组合总和 IV完全背包模板
vector<int> dp(bagSize + 1, 0);
for (int i = 0; i < items.size(); i++) {
for (int j = weight[i]; j <= bagSize; j++) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}关键点：
完全背包容量 j 正序遍历因为一个物品可以反复使用。
322. 零钱兑换
含义：
dp[j] = 凑出金额 j 所需要的最少硬币数量模板：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
if (dp[amount] == amount + 1) {
return -1;
}
return dp[amount];
}
};518. 零钱兑换 II
含义：
dp[j] = 凑出金额 j 的组合数模板：
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] = dp[j] + dp[j - coins[i]];
}
}
return dp[amount];
}
};注意：
先遍历物品，再遍历容量：组合数
先遍历容量，再遍历物品：排列数六、字符串 DP 板子
典型题：
5 最长回文子串
647 回文子串
516 最长回文子序列
72 编辑距离
115 不同的子序列
139 单词拆分1. 回文子串 DP
647. 回文子串
含义：
dp[i][j] = s[i...j] 是否是回文串转移：
如果 s[i] == s[j]：
如果 j - i <= 1，直接是回文
否则看 dp[i + 1][j - 1]模板：
class Solution {
public:
int countSubstrings(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s[i] == s[j]) {
if (j - i <= 1) {
dp[i][j] = 1;
} else if (dp[i + 1][j - 1] == 1) {
dp[i][j] = 1;
}
}
if (dp[i][j] == 1) {
ans++;
}
}
}
return ans;
}
};2. 编辑距离
72. 编辑距离
含义：
dp[i][j] = word1 前 i 个字符变成 word2 前 j 个字符的最少操作数模板：
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
int insertOp = dp[i][j - 1] + 1;
int deleteOp = dp[i - 1][j] + 1;
int replaceOp = dp[i - 1][j - 1] + 1;
dp[i][j] = min(insertOp, min(deleteOp, replaceOp));
}
}
}
return dp[m][n];
}
};七、股票 DP 板子
典型题：
121 买卖股票的最佳时机
122 买卖股票的最佳时机 II
123 买卖股票的最佳时机 III
188 买卖股票的最佳时机 IV
309 最佳买卖股票时机含冷冻期
714 买卖股票的最佳时机含手续费最基础的是状态机 DP。
121. 只能买卖一次
朴素写法：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = prices[0];
int ans = 0;
for (int i = 1; i < prices.size(); i++) {
ans = max(ans, prices[i] - minPrice);
minPrice = min(minPrice, prices[i]);
}
return ans;
}
};122. 可以买卖多次
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] > prices[i - 1]) {
ans += prices[i] - prices[i - 1];
}
}
return ans;
}
};股票题先记这两个就够了，状态机版本后面再补。
八、DP 题单加入你的总题单
DP 最小必刷 20 题
70 爬楼梯
746 使用最小花费爬楼梯
198 打家劫舍
213 打家劫舍 II
62 不同路径
63 不同路径 II
64 最小路径和
53 最大子数组和
300 最长递增子序列
1143 最长公共子序列
718 最长重复子数组
416 分割等和子集
494 目标和
322 零钱兑换
518 零钱兑换 II
279 完全平方数
139 单词拆分
647 回文子串
516 最长回文子序列
72 编辑距离九、最终完整板子题单
你要”齐全”的话，按这个刷。
第一组：数组 / 双指针 / 滑窗
1 两数之和
26 删除有序数组中的重复项
27 移除元素
283 移动零
11 盛最多水的容器
42 接雨水
3 无重复字符的最长子串
209 长度最小的子数组
438 找到字符串中所有字母异位词第二组：栈 / 单调栈
20 有效的括号
155 最小栈
232 用栈实现队列
739 每日温度
496 下一个更大元素 I
503 下一个更大元素 II
84 柱状图中最大的矩形第三组：链表
206 反转链表
92 反转链表 II
21 合并两个有序链表
141 环形链表
142 环形链表 II
160 相交链表
19 删除链表的倒数第 N 个结点
234 回文链表第四组：二叉树
144 二叉树的前序遍历
94 二叉树的中序遍历
145 二叉树的后序遍历
102 二叉树的层序遍历
104 二叉树的最大深度
111 二叉树的最小深度
226 翻转二叉树
101 对称二叉树
543 二叉树的直径
236 二叉树的最近公共祖先第五组：堆 / 优先队列
215 数组中的第 K 个最大元素
347 前 K 个高频元素
295 数据流的中位数
23 合并 K 个升序链表
973 最接近原点的 K 个点第六组：图论
841 钥匙和房间
1971 寻找图中是否存在路径
547 省份数量
200 岛屿数量
695 岛屿的最大面积
994 腐烂的橘子
542 01 矩阵
417 太平洋大西洋水流问题
207 课程表
210 课程表 II
802 找到最终的安全状态
310 最小高度树第七组：并查集
547 省份数量
1971 寻找图中是否存在路径
684 冗余连接
1319 连通网络的操作次数
990 等式方程的可满足性
721 账户合并第八组：回溯
46 全排列
47 全排列 II
77 组合
78 子集
90 子集 II
39 组合总和
40 组合总和 II
131 分割回文串
93 复原 IP 地址
51 N 皇后第九组：DP
70 爬楼梯
746 使用最小花费爬楼梯
198 打家劫舍
213 打家劫舍 II
62 不同路径
63 不同路径 II
64 最小路径和
53 最大子数组和
300 最长递增子序列
1143 最长公共子序列
718 最长重复子数组
416 分割等和子集
494 目标和
322 零钱兑换
518 零钱兑换 II
279 完全平方数
139 单词拆分
647 回文子串
516 最长回文子序列
72 编辑距离十、真正推荐的刷题顺序
别按 Hot100 顺序乱刷。你现在应该这样来：
1. BFS / DFS / 图论
200 -> 695 -> 994 -> 542 -> 207 -> 210
2. 二叉树
102 -> 104 -> 226 -> 101 -> 543 -> 236
3. 栈 / 单调栈
20 -> 739 -> 496 -> 503 -> 84
4. 链表
206 -> 21 -> 141 -> 142 -> 19 -> 92
5. DP 入门
70 -> 746 -> 198 -> 62 -> 64 -> 53
6. DP 进阶
300 -> 1143 -> 416 -> 322 -> 518 -> 647 -> 72
7. 回溯
46 -> 78 -> 77 -> 39 -> 131 -> 51
8. 堆
215 -> 347 -> 295 -> 23十一、你要背的 DP 总口诀
dp[i] 是什么？
初始化谁？
从哪里转移过来？
循环顺序怎么写？
答案在哪里？再具体一点：
线性 DP：通常从前往后
二维路径 DP：通常从左上到右下
子序列 DP：通常 i、j 双循环
01 背包：容量倒序
完全背包：容量正序
回文 DP：i 从后往前，j 从 i 往后最重要的是这两个：
01 背包：for j = target; j >= nums[i]; j--
完全背包：for j = coins[i]; j <= amount; j++这个背下来，DP 至少不会完全懵。