动态规划

动态规划总纲：从递归、记忆化搜索到递推；如何识别 DP、设计状态、分类刷题与避坑。

#resource / algorithm #type / concept #status / growing #algo / dp

[!info] related notes 算法面试题型 MOC 递归 线性 DP 背包 DP 网格 DP 与双序列 DP 区间 DP 与状态机 DP 爬楼梯 打家劫舍 最长递增子序列 不同路径 最小路径和 零钱兑换 II 目标和 最长回文子序列 买卖股票的最佳时机 打家劫舍 II 打家劫舍 III 不同的子序列 戳气球 最长有效括号 股票含冷冻期 股票含手续费 股票 k 次交易 树形 DP 数位 DP 概率 DP 股票最大资产

动态规划

动态规划（Dynamic Programming，DP）的本质是：

把一个大问题拆成若干个有重叠的子问题，并记录子问题答案，避免重复计算。

一句话记忆：

  • 递归 + 缓存 = 记忆化搜索（自顶向下）
  • 记忆化搜索改成循环 = 递推（自底向上）

一眼判断：这题是不是 DP

看到下面这些信号，要往 DP 想：

  • 求最值：最大值、最小值、最长、最少次数、最大收益、最低代价
  • 能拆成子问题：当前答案依赖更小规模问题
  • 有重复子问题：暴力递归会重复计算同一个状态
  • 无后效性：后面的决策只关心“当前状态”，不关心“怎么走到这里”

如果你发现：

  • 暴力递归能写
  • 递归参数不多
  • 相同参数会被反复调用

那它大概率就能改成 DP。

DP 和递归的关系

很多 DP 题，最自然的思路不是先写 for 循环，而是先写递归。

因为递归最容易想清楚：

这个问题的最后一步是什么？

例子：打家劫舍

题目：打家劫舍

定义 dfs(i) 表示考虑到下标 i 时的最大收益。

对于第 i 个房子：

  • 不偷：dfs(i - 1)
  • 偷：dfs(i - 2) + nums[i]

所以：

dfs(i) = Math.max(dfs(i - 1), dfs(i - 2) + nums[i])

边界：

dfs(i) = 0, when i < 0

记忆化搜索（自顶向下）

var rob = function(nums) {
    const n = nums.length;
    const cache = new Array(n).fill(-1);

    function dfs(i) {
        if (i < 0) return 0;
        if (cache[i] !== -1) return cache[i];

        const res = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);
        cache[i] = res;
        return res;
    }

    return dfs(n - 1);
};

递推（自底向上）

var rob = function(nums) {
    const n = nums.length;
    const f = new Array(n + 2).fill(0);

    for (let i = 0; i < n; i++) {
        f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);
    }

    return f[n + 1];
};

这里 f[i + 2] 表示考虑 nums[0...i] 的最大收益。整体右移 2 位，是为了让边界更整齐。

做 DP 的固定五步

每道 DP 题都强制自己按这个顺序思考：

1. 定义状态

先回答：dp[i] / dp[i][j] 表示什么？

常见定义方式：

  • 前 i 个元素中的最优值 / 方案数
  • 以第 i 个元素结尾的最优值
  • 到达坐标 (i, j) 的最优值 / 方案数
  • 区间 [i, j] 的最优值
  • 容量为 j 时的最优值 / 方案数
  • 匹配到两个前缀时的最优值

2. 写状态转移

问自己：最后一步发生了什么？

常见思路：

  • 选 / 不选
  • 枚举最后一个选谁
  • 从上 / 左 / 左上转移
  • 枚举分割点
  • 当前字符相等 / 不等

3. 定边界 / 初始化

比如：

  • dp[0] = ?
  • 空串 / 空数组时答案是什么
  • 不可达状态设成 -INF、INF 还是 false

4. 定遍历顺序

必须保证：算当前状态时，它依赖的状态已经算出来。

典型顺序：

  • 线性 DP：从左到右
  • 网格 DP：从上到下、从左到右
  • 区间 DP：按区间长度从小到大
  • 01 背包：容量倒序
  • 完全背包：容量正序

5. 看能不能优化空间

如果当前状态只依赖前一行 / 前几个状态，就考虑：

  • 滚动数组
  • 压成几个变量

两个最关键的状态设计

A. 定义成“前 i 个元素”

适合“选或不选”类题目：

这类题的思考方式是：

当前元素，我选它还是不选它？

B. 定义成“以第 i 个元素结尾”

适合“枚举最后一个选谁”类题目：

  • 最长递增子序列（LIS）
  • 以 i 结尾的最大子数组和
  • 以 i 结尾的最长连续上升序列

这类题的思考方式是：

如果答案最后停在 i，那它前面从哪里转移来？

常见题型总览

一页式速查表

题型常见状态转移关键词先练什么再练什么
线性 DPdp[i] / 前 i 个 / 以 i 结尾选或不选、接在前面[[climbing-stairs爬楼梯]]、[[house-robber打家劫舍]][[longest-increasing-subsequenceLIS]]、[[longest-valid-parentheses最长有效括号]]
背包 DPdp[j] / dp[i][j]容量、恰好装、方案数[[partition-equal-subset-sum分割等和子集]]、[[coin-change零钱兑换]][[coin-change-ii零钱兑换 II]]、[[target-sum目标和]]
网格 / 双序列 DPdp[i][j]上 / 左 / 左上、字符相等/不等[[unique-paths不同路径]]、[[minimum-path-sum最小路径和]][[longest-common-subsequenceLCS]]、[[edit-distance编辑距离]]、[[distinct-subsequences不同的子序列]]
区间 DPdp[l][r] / dp[i][j]枚举最后一步、按长度枚举[[longest-palindromic-substring最长回文子串]][[longest-palindromic-subsequence最长回文子序列]]、[[burst-balloons戳气球]]
状态机 DPdp[i][state]持股 / 不持股 / 冷冻 / 交易次数[[best-time-to-buy-and-sell-stock股票入门]][[best-time-to-buy-and-sell-stock-with-cooldown冷冻期]]、[[best-time-to-buy-and-sell-stock-with-transaction-fee手续费]]、[[best-time-to-buy-and-sell-stock-ivk 次交易]]
树形 DP节点返回多状态子树合并、偷/不偷、选/不选[[house-robber-iii打家劫舍 III]][[dp-tree-dp树形 DP]]
数位 DPdfs(pos, limit, started, state)按位枚举、前缀受限[[dp-digit-dp数位 DP]][[dp-digit-dp数位 DP]]
概率 DPdp[i][j] / f[state]概率转移、期望、总概率[[dp-probability-dp概率 DP]][[dp-probability-dp概率 DP]]

1. 线性 DP

2. 背包 DP

3. 网格 DP / 双序列 DP

4. 区间 DP / 状态机 DP

背包里三个高频问法

至多装

容量不超过 j，不要求装满。

恰好装

必须刚好凑出容量 j。

初始化通常最关键：

  • 最大值型：不可达设 -INF
  • 最小值型：不可达设 INF
  • 可行性：不可达设 false

至少装

要求容量达到至少某个值。

常见做法：

  • 转成“恰好装”
  • 或最后枚举所有 j >= target

背包里“值”不一定是价值

dp[j] 里装的内容可能是：

  • 最大价值
  • 最小物品数
  • 是否可达
  • 方案数
  • 组合数 / 排列数

不要只背公式，一定先问：

这个状态里保存的到底是什么？

二维 DP 里最常见的两个方向

网格型

例如不同路径、最小路径和。

通常：

dp[i][j] = 从起点走到 (i, j) 的方案数 / 最优值

再从上面、左边转移。

双序列型

例如 LCS、编辑距离。

通常：

dp[i][j] = s 的前 i 个字符与 t 的前 j 个字符的答案

最长回文子串：为什么是区间 DP

定义：

dp[i][j] 表示 s[i...j] 是否为回文串

转移：

dp[i][j] = (s[i] === s[j]) && (j - i <= 1 || dp[i + 1][j - 1])

因为依赖 dp[i + 1][j - 1]，所以要：

  • i 从大到小
  • j 从小到大

或者按区间长度枚举。

Manacher 是回文串专项优化算法，不属于入门 DP 主线。先掌握中心扩展和区间 DP 再说。

做题通用模板

每次做 DP 题，先问自己五个问题：

  1. 状态是什么？
  2. 最后一步是什么？
  3. 初始值是什么？
  4. 遍历顺序为什么这样？
  5. 能不能压缩空间？

如果还不会，就退一步：

  1. 先写暴力递归
  2. 看递归参数是谁在变化
  3. 看有没有重复子问题
  4. 再改成记忆化搜索 / 递推

常见错误

  • 状态定义不清：前 i 个 和 以 i 结尾 混了
  • 转移写错：01 背包写成完全背包，或者反过来
  • 初始化错误：尤其是恰好装满、不可达状态
  • 遍历顺序错误：区间 DP、01 背包、完全背包最常错
  • 组合 / 排列搞混：枚举顺序不同，答案含义不同

新手学习路线

第一阶段：先学 DP 是怎么来的

目标：每道题都尝试写三遍：递归 -> 记忆化搜索 -> 递推。

第二阶段：掌握两种状态设计

第三阶段：刷背包专题

第四阶段：补区间 DP / 状态机 DP

对应笔记：最长回文子串、最长回文子序列、戳气球、买卖股票的最佳时机、含冷冻期、含手续费、k 次交易、股票最大资产

第五阶段：进阶专题

一页式速记

  • 先写递归，再想缓存，再改递推
  • 选 / 不选 -> 往“前 i 个元素”想
  • 枚举最后一个 -> 往“以 i 结尾”想
  • 两个前缀 / 网格坐标 -> 往 dp[i][j] 想
  • 区间 [l, r] -> 往区间 DP 想
  • 每次都检查：状态、转移、初始化、顺序、空间优化
创建于 2025/1/1 更新于 2026/5/27