动态规划(DP)是算法面试里出现频率最高的家族,也是新手最容易"看懂题解但自己想不出来"的题型。原因不在难,而在大家学的是"题目 + 答案",而不是从一个朴素递归一步步推导到 DP的过程。这篇文章给你这套推导框架,然后用它打通从入门到 LeetCode 中等/困难的常见题型。
DP 的本质:有重叠子问题的递归 + 记忆化
动态规划只解决一类问题:原问题可以拆成更小的同类子问题,且这些子问题会被重复计算。"重复计算"是关键,不重复就用不到 DP,只是普通分治。
最经典的入门例子是斐波那契:
// 朴素递归:指数级时间复杂度
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// fib(40) 已经要算几秒,fib(50) 几乎跑不出来慢的原因:fib(38) 被算了很多次。把每个 n 的结果缓存起来,瞬间从指数变线性:
// 自顶向下:递归 + 记忆化
function fibMemo(n, memo = {}) {
if (n <= 1) return n;
if (memo[n] !== undefined) return memo[n];
return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}
// 自底向上:迭代,用数组存所有子问题答案
function fibDP(n) {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
// 滚动数组:只用两个变量
function fibBest(n) {
if (n <= 1) return n;
let a = 0, b = 1;
for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
return b;
}"朴素递归 → 加记忆化 → 改迭代 → 压缩空间"是 DP 题的标准演进路径。会写朴素递归是第一道闸,后面三步都是机械优化。
解 DP 题的固定四步法
- 定义状态:dp[i] / dp[i][j] 表示什么?这是最关键的一步,直接决定能不能做出来。
- 写状态转移方程:dp[i] 怎么从 dp[更小的 i] 算出来?
- 确定初始值和遍历顺序:边界 dp[0] 是什么?是按 i 从小到大还是从大到小?
- (可选)优化空间:如果只用到前 k 个状态,用滚动数组。
一维 DP:爬楼梯、打家劫舍、最大子数组和
爬楼梯
每次能爬 1 或 2 阶,爬到 n 阶有多少种方法?
// 状态:dp[i] = 爬到第 i 阶的方法数
// 转移:dp[i] = dp[i-1] + dp[i-2]
// (从 i-1 阶迈 1 步 或 从 i-2 阶迈 2 步)
// 初始:dp[0]=1, dp[1]=1
function climbStairs(n) {
if (n <= 1) return 1;
let a = 1, b = 1;
for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
return b;
}打家劫舍
一排房子,nums[i] 是第 i 间的钱,不能偷相邻两间,问最多能偷多少。
// 状态:dp[i] = 考虑前 i 间房,能偷到的最大金额
// 转移:dp[i] = max(dp[i-1], dp[i-2] + nums[i])
// 不偷第 i 间 偷第 i 间(那么 i-1 不能偷)
function rob(nums) {
let prev = 0, curr = 0;
for (const x of nums) {
[prev, curr] = [curr, Math.max(curr, prev + x)];
}
return curr;
}最大子数组和(Kadane 算法)
// 状态:dp[i] = 以 nums[i] 结尾的最大子数组和
// 注意"以 i 结尾"是关键技巧 —— 让相邻状态有清晰联系
// 转移:dp[i] = max(nums[i], dp[i-1] + nums[i])
// 单独自己 接到前面的子数组
// 答案:max(dp)
function maxSubArray(nums) {
let curr = nums[0], best = nums[0];
for (let i = 1; i < nums.length; i++) {
curr = Math.max(nums[i], curr + nums[i]);
best = Math.max(best, curr);
}
return best;
}二维 DP:网格路径、最长公共子序列
不同路径
m×n 网格,从左上走到右下,只能向右或向下,有多少种路径?
// 状态:dp[i][j] = 到 (i,j) 的路径数
// 转移:dp[i][j] = dp[i-1][j] + dp[i][j-1]
// 初始:第一行第一列都是 1
function uniquePaths(m, n) {
const dp = Array(n).fill(1); // 第一行
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] += dp[j - 1]; // dp[j] 现在是上一行,dp[j-1] 是同一行
}
}
return dp[n - 1];
}最长公共子序列 LCS
给两个字符串,找最长的公共子序列(不必连续)的长度。这是字符串 DP 的祖师爷。
// 状态:dp[i][j] = s1 前 i 个字符 和 s2 前 j 个字符 的 LCS 长度
// 转移:
// s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
// 否则: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
function lcs(s1, s2) {
const m = s1.length, n = s2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i - 1] === s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
console.log(lcs('abcde', 'ace')); // 3 ('ace')LCS 是模板题:编辑距离、最长公共子串、最短编辑路径都是它的变种。
编辑距离(Levenshtein 距离)
把 word1 变成 word2 最少需要多少次操作(插入/删除/替换)?
// 状态:dp[i][j] = word1 前 i 个变成 word2 前 j 个的最少操作数
// 转移:
// word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]
// 否则:dp[i][j] = 1 + min(
// dp[i-1][j], // 删除 word1[i-1]
// dp[i][j-1], // 在 word1 末尾插入 word2[j-1]
// dp[i-1][j-1] // 把 word1[i-1] 替换成 word2[j-1]
// )
function editDistance(w1, w2) {
const m = w1.length, n = w2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (w1[i - 1] === w2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
}
}
return dp[m][n];
}背包问题:DP 里最重要的家族
0-1 背包和完全背包是几乎所有"选/不选"类问题的母题。
0-1 背包
有 n 个物品,第 i 个重量 w[i]、价值 v[i],背包容量 C,每个物品只能选一次,求最大总价值。
// 状态:dp[i][c] = 考虑前 i 个物品、容量 c 时的最大价值
// 转移:
// 不选第 i 个: dp[i][c] = dp[i-1][c]
// 选(且装得下): dp[i][c] = dp[i-1][c - w[i-1]] + v[i-1]
// 取两者较大
function knapsack(w, v, C) {
const n = w.length;
const dp = Array.from({ length: n + 1 }, () => new Array(C + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let c = 0; c <= C; c++) {
dp[i][c] = dp[i - 1][c];
if (c >= w[i - 1]) {
dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]);
}
}
}
return dp[n][C];
}
// 空间压缩到一维:注意 c 必须倒序遍历(否则会重复使用同一物品)
function knapsack1D(w, v, C) {
const dp = new Array(C + 1).fill(0);
for (let i = 0; i < w.length; i++) {
for (let c = C; c >= w[i]; c--) { // 倒序!
dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
}
}
return dp[C];
}完全背包(每个物品无限选)
// 唯一改动:内层 c 改成"正序"遍历,允许重复使用同一物品
function completeKnapsack(w, v, C) {
const dp = new Array(C + 1).fill(0);
for (let i = 0; i < w.length; i++) {
for (let c = w[i]; c <= C; c++) { // 正序!
dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
}
}
return dp[C];
}"0-1 倒序、完全正序"是背包问题最值得记住的一句口诀。
零钱兑换(完全背包变形)
给定面额 coins,凑成 amount 所需的最少硬币数。
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (const c of coins) {
for (let i = c; i <= amount; i++) {
dp[i] = Math.min(dp[i], dp[i - c] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}区间 DP:最长回文子序列
区间 DP 的状态通常是 dp[i][j],表示"区间 [i,j] 的某个最优值",转移依赖更小的区间。
// 最长回文子序列
// 状态:dp[i][j] = s 在 [i,j] 内的最长回文子序列长度
// 转移:
// s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
// 否则: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
// 注意:i 倒序、j 正序,因为依赖更小区间
function longestPalindromeSubseq(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (let j = i + 1; j < n; j++) {
if (s[i] === s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}状态机 DP:股票买卖系列
"买卖股票的最佳时机 IV"是状态机 DP 的代表 —— 用一个二维状态(第几天,当前持/不持)精确刻画行为。
// 一次买卖(只能交易一次)
function maxProfit(prices) {
let minPrice = Infinity, best = 0;
for (const p of prices) {
minPrice = Math.min(minPrice, p);
best = Math.max(best, p - minPrice);
}
return best;
}
// 不限交易次数(但同一天不能买卖,且需要先卖才能买)
function maxProfitUnlimited(prices) {
let hold = -Infinity, cash = 0;
for (const p of prices) {
const newHold = Math.max(hold, cash - p); // 继续持有 or 今天买入
const newCash = Math.max(cash, hold + p); // 继续空仓 or 今天卖出
[hold, cash] = [newHold, newCash];
}
return cash;
}怎么判断一道题是不是 DP
面试时拿到题,问自己三个问题:
- 题目要"最值/计数/可行性"吗?(最长、最短、最大、有多少种、能不能)
- 能不能分解成"前 i 个的最优解 + 第 i+1 个的决策"?
- 同一个子问题会被多次需要吗?
三个都是"是",八九不离十是 DP。如果是"找一条路径""组合数学的精确公式""贪心局部最优能推出全局",那可能是别的算法。
记忆化递归:从朴素递归更平滑地过渡到 DP
有时候自顶向下的记忆化递归比自底向上的 DP 更好理解,尤其是当状态空间稀疏(很多子问题用不到)时它还更高效。
// 单词拆分:给定字典,问 s 能否被字典里的单词拼接成
function wordBreak(s, wordDict) {
const set = new Set(wordDict);
const memo = new Map();
function can(i) {
if (i === s.length) return true;
if (memo.has(i)) return memo.get(i);
for (let j = i + 1; j <= s.length; j++) {
if (set.has(s.slice(i, j)) && can(j)) {
memo.set(i, true);
return true;
}
}
memo.set(i, false);
return false;
}
return can(0);
}这种"先写朴素递归,然后给入口函数加一个 memo Map"的模式,几乎所有 DP 题都适用。它的好处是写法贴近你解决问题的思路,缺点是有递归调用栈开销。
树形 DP 入门:打家劫舍 III
把房子从一排变成一棵二叉树,相邻节点(父子)不能同时偷,问最多偷多少。
// 状态:每个节点返回 [不偷该节点的最大值, 偷该节点的最大值]
// 转移:
// 不偷:左右子树都可偷可不偷,各取较大
// 偷: 左右子树必须都不偷,加上当前节点的值
function rob3(root) {
function dfs(node) {
if (!node) return [0, 0];
const [ln, lp] = dfs(node.left);
const [rn, rp] = dfs(node.right);
const notRob = Math.max(ln, lp) + Math.max(rn, rp);
const rob = ln + rn + node.val;
return [notRob, rob];
}
return Math.max(...dfs(root));
}树形 DP 的精髓:把"每个节点对外提供的状态"想清楚,然后递归收集左右子树的状态,合成自己对外提供的状态。一旦能写出"返回什么、依赖什么",代码自然就出来了。
常见易错点
错 1:状态定义忘了"以 i 结尾"。 "最长上升子序列"如果定义成"前 i 个的最长上升子序列长度",转移就写不出来 —— 因为 dp[i] 不一定包含 nums[i]。改成"以 nums[i] 结尾的最长上升子序列长度",转移立刻清晰。
错 2:背包问题维度混淆。 0-1 背包压一维必须倒序,完全背包必须正序 —— 顺序错了 AC 不了。记口诀比死记原理更可靠。
错 3:初始值边界考虑不全。 编辑距离的 dp[i][0] = i 和 dp[0][j] = j,如果都默认 0,转移方程立刻崩。每写完一个 DP,都手动跑一遍 i=0、j=0 的边界,确保不依赖未初始化的状态。
写在最后
动态规划没有"灵光一现"。每一道你看着惊艳的 DP 题解,背后都是"定义状态 → 写转移方程 → 确定边界和顺序 → 必要时压缩空间"这套机械流程。卡住的几乎永远是第一步 —— 状态定义错了,转移方程就没法写。多练几道一维二维的入门题,把状态定义那种"以 i 结尾""考虑前 i 个""[i,j] 区间内"的常用模板熟透,后面的题就只是模板的组合。
给的练习路径:爬楼梯 → 打家劫舍 → 最大子数组和 → 不同路径 → 最长公共子序列 → 编辑距离 → 0-1 背包 → 零钱兑换 → 最长回文子序列 → 股票买卖系列。这十道刷完且不看题解能独立写出,大部分 DP 中等题你都能拿下。困难题再加上"区间 DP""树形 DP""数位 DP"这几个专题就够了。
—— 别看了 · 2026