多数人卡在 DP 上不是写不出方程，而是状态定义错了却还能跑出样例答案。dp[i] 被含糊理解成"前 i 个的最优值"，于是背包少一维容量、LIS 少一个"结尾下标"，小用例正确、规模一大就偏。难点集中在第一步：状态要装下决定后续决策的全部信息。

---

1. DP 适合什么

判据	满足时的含义	不满足时该换什么
重叠子问题	同一子问题被反复求解，缓存有意义	分治（子问题互不相交）
最优子结构	全局最优由子问题最优拼出	搜索 / 回溯 + 剪枝
无后效性	状态确定后，后续决策与"怎么走到这里"无关	状态里补维度，装下路径信息
状态规模可控	状态数 × 转移代价可接受	贪心、近似算法

三条常见混淆要分清：

• 与贪心：贪心只做局部最优且不回看，前提是"局部最优可推广"；DP 保留全部候选状态，等价于带回看的枚举，能用贪心时 DP 也对，只是更贵。
• 与分治：分治子问题不重叠（归并的两半互不相干），DP 子问题重叠，所以要存表。
• 不该用 DP：无重叠子问题、状态维度爆炸、需要输出全部方案（该用搜索）。

---

2. 四步推导

步骤	该问自己的问题	产出
定义状态	dp[...] 的下标各自代表什么？它是否唯一确定了"接下来能做什么"？	维数与语义
写转移	最后一步决策是什么？它由哪些更小的状态推来？	递推式
定边界	最小的合法输入是什么？空集合、不可达怎么表示？	初值与哨兵
定顺序	转移依赖的状态是否已经算过？	遍历方向

顺序最容易被忽略，而它决定正确性：0-1 背包必须逆序、完全背包必须正序，两者代码只差一个循环方向，语义却完全不同。写不出转移时，多半是状态定义漏了信息，而不是方程不会推。

---

3. 四个例子走一遍

3.1 爬楼梯与 LIS

/* 例 1：爬楼梯。状态 = 到达第 i 级的方法数，转移只依赖前两级 */
static int climbStairs(int n) {
    if (n <= 1) return 1;          // 边界：n = 0 与 n = 1 都只有一种走法
    int prev = 1, cur = 1;         // 滚动变量，空间 O(1)
    for (int i = 2; i <= n; i++) {
        int next = prev + cur;
        prev = cur;
        cur = next;
    }
    return cur;
}

/* 例 2：LIS。状态必须是"以 i 结尾"，不能是"前 i 个" */
static int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);                       // 每个元素自身构成长度 1
    int best = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}

LIS 的状态定义是重点。若定义成"前 i 个的最长上升子序列长度"，dp[i] 与 dp[i+1] 无从衔接——不知道子序列结尾值，就无法判断 nums[i] 能否接上。改成"以 i 结尾"后结尾值确定，比较才成立；代价是答案要在过程中取最值。另有 O(n log n) 的二分做法（维护各长度的最小结尾值），本篇不展开。

3.2 零钱兑换

/* 状态 dp[i] = 凑出金额 i 的最少硬币数；不可达用 INF 表示 */
static int coinChange(int[] coins, int amount) {
    final int INF = amount + 1;                // 比任何合法答案都大，且 +1 不溢出
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;                                 // 边界：金额 0 需要 0 枚
    for (int i = 1; i <= amount; i++) {        // 外层金额、内层硬币 → 完全背包正序
        for (int c : coins) {
            if (c <= i && dp[i - c] != INF) {
                dp[i] = Math.min(dp[i], dp[i - c] + 1);
            }
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}

INF 取 amount + 1 而非 Integer.MAX_VALUE：后者做 INF + 1 会溢出成负数并被 Math.min 选中。dp[i-c] != INF 是"不可达状态不参与转移"的必要保护。

3.3 0-1 背包

/* 状态 dp[c] = 容量 c 下的最大价值；每件物品只能用一次 → 容量必须逆序遍历 */
static int knapsack(int[] weight, int[] value, int cap) {
    int[] dp = new int[cap + 1];               // 未选任何物品时价值为 0，天然初值
    for (int i = 0; i < weight.length; i++) {
        for (int c = cap; c >= weight[i]; c--) {   // 逆序：保证用的是上一轮的状态
            dp[c] = Math.max(dp[c], dp[c - weight[i]] + value[i]);
        }
    }
    return dp[cap];
}

逆序的理由：dp[c] 依赖 dp[c - w]，正序时 dp[c - w] 可能已被本轮"放入当前物品"更新，等于同一物品放两次——那正是完全背包的语义。压缩后"上一层"的信息只能靠遍历方向保住。

---

4. 空间优化

原状态	优化后	成立条件	遍历方向
dp[i][c]（0-1 背包）	dp[c]	转移只依赖 i-1 层	容量逆序
dp[i][c]（完全背包）	dp[c]	允许同一物品重复选	容量正序
dp[i]（爬楼梯）	两个变量	转移只依赖前 1–2 项	正序，覆盖旧值即可
dp[i][j]（编辑距离）	两行滚动	只依赖上一行与当前行左侧	行优先

压缩的通用判据是转移引用的层数：只引用固定偏移（上一层、前一列）就能压缩，引用范围不定（如区间 DP 的 dp[l][r]）就不能。

---

5. 记忆化与递推

/* 自顶向下：最好想，状态就是递归参数 */
static int fibMemo(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];         // -1 表示"未计算"，不能与合法值 0 混用
    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

/* 自底向上：同一题的递推写法，省掉递归栈与函数调用开销 */
static int fibIter(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

维度	记忆化搜索	递推
思维难度	低（照抄暴力递归 + 缓存）	中（要先定好顺序）
无用状态	不算（只算可达）	整表都算
空间优化	难（缓存粒度由递归参数决定）	易（滚动数组直接手写）
风险	递归深度、栈溢出、memo 初值歧义	顺序写错导致答案错且不报错

memo 初值必须是"不可能成为合法答案"的值。fib 可用 -1；"最少硬币数"里 0 是合法值，只能用 -1/INF 并配套判断。用 0 当"未计算"标记是最常见的隐性错误。

---

6. 状态定义的常见错误

错误	表现	修法
状态不足以决定后续决策	样例过、规模大就偏小	补维度（剩余容量、上次选择、结尾下标）
"前 i 个"与"以 i 结尾"混用	答案取错位置，或转移无法比较	明确语义，答案在过程中取最值
维度遗漏（背包少容量维）	物品被隐式重复使用	写出二维式再压缩
把"恰好"与"至多"混为一谈	初值错、答案多算	恰好用 INF，至多用 0 初始化
状态里塞了路径	状态数爆炸	仅在需要输出方案时记前驱

---

7. 初始值与边界

/* 三种语义的初值写法，差异全在第一行 */
int[] dpExact = new int[n + 1];
Arrays.fill(dpExact, INF);   dpExact[0] = 0;   // 恰好装满：只有 0 可达
int[] dpAtMost = new int[n + 1];               // 至多：全 0，任何容量都"合法"
int[] dpCount = new int[n + 1]; dpCount[0] = 1; // 计数：空方案算一种

INF/-1 的传播规则要成对设计：求 min 时用 INF 并在转移前判 != INF（否则 INF + 1 溢出）；求 max 时用 -1 并在转移前判 != -1；求计数时用 0 表示不可达，且不能参与加法。初值写错不会报错，只会让答案系统性偏大或偏小。

---

8. 复杂度

例子	状态数	单次转移	时间	空间（优化后）
爬楼梯	n	O(1)	O(n)	O(1)
LIS	n	O(n)	O(n²)	O(n)
零钱兑换	amount	O(硬币数)	O(amount × 硬币数)	O(amount)
0-1 背包	n × cap	O(1)	O(n × cap)	O(cap)

一律按"状态数 × 单次转移代价"估，不要凭感觉写 O(n)。需要真实对比时按 JMH 口径测量，不要用单次 System.nanoTime 下结论。

---

9. 排错

现象	原因	处理
答案比正确值小	0-1 背包容量写成正序，物品被重复用	容量改逆序
答案比正确值大	初值给了"至多"语义却按"恰好"解读	按语义重设初值
大规模用例算不出结果	状态维度爆炸或用了 int 溢出的 INF	降维、换 long、INF 取保守值
ArrayIndexOutOfBounds	dp[i - c] 未判 c <= i	加边界判断
记忆化结果随机变化	memo 初值用了合法值	换 -1/INF 并判空
递归版栈溢出	状态链长度接近输入规模	改递推或加大栈
取模后答案错	同时求最值与取模，顺序冲突	最值不改模，计数才取模

---

10. 边界：什么时候不该上 DP

场景	换什么	理由
子问题不重叠	分治 / 直接递归	存表没有收益
只需一种可行解	贪心 / 构造	DP 求最优更贵
需要枚举全部方案	回溯 + 剪枝	DP 只保留最优，丢掉方案
状态数超过可枚举上限	状态压缩、折半、换建模	表存不下
约束是连续区间且可贪心	单调队列 / 斜率优化	普通 DP 会多一层枚举
输入流式、需在线回答	近似或增量结构	DP 要求全量输入

最后一条常被忽略：DP 的前提是"能看见全部输入并按下标组织状态"，流式场景里状态表会无限增长。

---

11. 自测

1. 什么条件下 dp[i][c] 可以安全压缩成 dp[c]？压缩后靠什么信息区分"上一层"？
2. LIS 为什么必须定义成"以 i 结尾"，而不能是"前 i 个"？
3. 0-1 背包容量正序遍历会得到哪个问题的答案？
4. INF 取 Integer.MAX_VALUE 会引发什么具体错误？
5. 记忆化搜索与递推在"是否会计算无用状态"上的差别，什么时候这个差别很重要？
6. 状态定义"不足以决定后续决策"时，通常表现为答案偏大还是偏小？举一个例子说明。