动态规划难，不是因为代码一定长，而是因为状态定义一旦错了，后面的转移方程、初始化和遍历顺序都会跟着错。

面试里不要一上来就背模板。先问自己两个问题：这个问题能不能拆成子问题？当前答案是否依赖前面已经算过的答案？如果这两个问题都成立，再考虑 DP。

• 能说清 dp[i] 或 dp[i][j] 的含义。
• 能写出状态转移方程。
• 能处理初始化和遍历顺序。
• 能判断是否可以压缩空间。
• 能区分背包、子序列、区间等常见类型。

DP 不是看到“最值”就套。更靠谱的判断是看两个条件：

1. 问题能不能拆成规模更小的同类问题。
2. 子问题会不会被反复计算。

比如斐波那契数列，f(n) 依赖 f(n - 1) 和 f(n - 2)，而 f(n - 2) 会在递归里被反复计算。把这些中间结果存下来，就是 DP。

面试里可以先从暴力递归说起，再说明哪里重复计算，最后把递归改成记忆化搜索或表格递推。这个过程比直接背 dp 数组更容易让面试官相信你真的理解。

1. 定义状态：dp[i] 到底表示什么。
2. 写转移：当前状态从哪些状态推出来。
3. 做初始化：没有前置状态时答案是什么。
4. 定遍历顺序：先算哪些状态，后算哪些状态。
5. 检查样例：用一个小输入手推数组。

其中最重要的是第 1 步。dp[i] 的含义一旦含糊，后面的代码就会变成试出来的。

一个好的状态定义通常满足：

• 能覆盖题目要问的答案。
• 能从更小状态推出来。
• 维度尽量少，但不要为了省空间把含义写乱。

爬楼梯问题：

int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    int prev2 = 1;
    int prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

状态含义：到第 i 阶有多少种走法。转移方程：dp[i] = dp[i - 1] + dp[i - 2]。

这题还可以从递归推出来：

到第 i 阶的最后一步，要么从 i-1 走 1 步上来，要么从 i-2 走 2 步上来。

所以 dp[i] 只依赖前两个状态，可以把数组压缩成两个变量。空间压缩的前提是你确认旧状态以后不会再用。

每个物品只能选一次：

int knapsack01(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

容量要倒序遍历，避免同一个物品在一轮里被重复使用。

倒序遍历是 0-1 背包最容易被问的点。假设容量正序遍历，计算 dp[j] 时可能用到本轮刚更新过的 dp[j - weight]，等于同一个物品被选了多次。这就变成完全背包了。

0-1 背包的典型问法不一定直接叫背包，像“能否分成两个和相等的子集”，可以转成：能否从数组里选一些数，使它们的和等于总和的一半。

每个物品可以选多次：

int unboundedKnapsack(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int j = weights[i]; j <= capacity; j++) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

容量正序遍历，允许当前物品被重复使用。

完全背包里，正序遍历容量正是为了允许当前物品重复使用。比如零钱兑换，每种硬币可以用多次，计算更大金额时可以基于当前硬币已经参与过的状态继续转移。

如果题目问的是“组合数”还是“排列数”，遍历顺序也会变：

• 组合数：通常先遍历物品，再遍历容量。
• 排列数：通常先遍历容量，再遍历物品。

这块面试不一定问很深，但遇到零钱兑换 II 这类题时很关键。

两种写法都在存子问题答案。

如果一开始想不清遍历顺序，可以先写记忆化搜索。等状态关系清楚后，再改成递推。很多树形 DP、区间 DP，用记忆化搜索更容易写对。

DP 题不建议直接从代码开始。面试手写时，可以先把下面 4 句话讲清楚：

1. dp 数组的含义是什么，答案最终落在哪个位置。
2. 当前状态依赖哪些旧状态，为什么这些旧状态已经算过。
3. 初始化为什么这样写，尤其是 0、1、无穷大分别代表什么。
4. 遍历顺序为什么不会提前使用未计算或不该重复使用的状态。

如果这 4 句话说不清，代码大概率是靠记忆写出来的，遇到变体就容易散。

322. 零钱兑换 是完全背包里很适合面试的一题。题目给定硬币面额和目标金额，问凑成目标金额最少需要多少枚硬币，每种硬币可以使用无限次。

状态定义可以这样说：

dp[j] 表示凑成金额 j 所需的最少硬币数。

初始化是这题的关键。dp[0] = 0，表示凑成金额 0 不需要硬币；其他金额先设成一个不可能的较大值，表示暂时不可达。

代码里用到 Arrays.fill，需要导入 java.util.Arrays。

int coinChange(int[] coins, int amount) {
    int max = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, max);
    dp[0] = 0;

    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }

    return dp[amount] == max ? -1 : dp[amount];
}

为什么容量正序遍历？因为一枚硬币可以用多次。计算 dp[j] 时使用 dp[j - coin]，如果 dp[j - coin] 已经在本轮被当前硬币更新过，就代表当前硬币可以继续被使用，这正好符合完全背包。

如果题目变成“每种硬币只能用一次”，容量就要倒序遍历。遍历方向不是格式问题，而是在控制同一件物品能不能重复参与转移。

DP 题经常不是不会写转移，而是状态含义选错。下面几组状态看起来接近，但写法完全不同：

面试里可以主动说一句：这里的 dp[i] 是“以 i 结尾”，不是“前 i 个元素里的最优值”。这句话能避免很多子序列题写错。

以爬楼梯为例，n = 5 时的状态变化如下：

这张表要看的不是数字本身，而是状态只依赖前两个位置，所以可以压缩成两个变量。

DP 题建议检查这些边界：

常见错误写法：

for (int j = weights[i]; j <= capacity; j++) {
    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); // 0-1 背包中是错的
}

0-1 背包中容量要倒序遍历，否则本轮刚更新的状态会被再次使用，相当于同一个物品被选了多次。

• dp 含义不要频繁变化。
• 初始化不是随便填 0，要看状态含义。
• 0-1 背包容量倒序，完全背包容量正序。
• 求方案数和求最值的初始化不同。
• 子序列题经常需要区分“以 i 结尾”和“前 i 个元素内”。

• 为什么 DP 的第一步一定是定义状态？
• 记忆化搜索和递推的区别是什么？什么时候先写记忆化更稳？
• 0-1 背包为什么容量要倒序遍历？
• 完全背包为什么容量可以正序遍历？
• dp[i] 表示“以 i 结尾”和表示“前 i 个元素”时，转移有什么区别？
• 求最少次数、最大价值、方案数时，初始化分别要注意什么？

• 70. 爬楼梯
• 198. 打家劫舍
• 322. 零钱兑换
• 416. 分割等和子集
• 300. 最长递增子序列
• 1143. 最长公共子序列