专题 10动态规划（进阶）：子序列与背包

10.1DP 的两大主线：子序列与背包

进阶 DP 看起来题海茫茫，其实绝大多数都能归到两条主线上。先一句话分清它们的形态差异，后面就不乱了：

先分清「子序列」和「子串」

这两个词经常被混用，但 DP 写法天差地别，面试也常考你这个区分：

一句话：子串用「滑动窗口/双指针」（因为连续，左右边界能滑动）； 子序列用「二维 DP」（因为不连续，必须枚举「以谁结尾 / 前面配对到哪」）。看到「子序列」三个字，基本就该往本章的二维 dp 上想了。

10.2最长递增子序列（中等，力扣 300）

中等 核心：以谁结尾 + 递推

题意：给你一个整数数组，找出其中严格递增的最长子序列的长度（子序列不要求连续）。 例如 nums = [10,9,2,5,3,7,101,18]，最长递增子序列是 [2,3,7,101] 或 [2,5,7,101]，长度 4。

思路推导

暴力枚举所有子序列是指数级的，显然不行。关键观察：一个递增子序列一定「以某个数结尾」。 那我们换个角度——不去想「全局最长是哪个」，而是先算「以每个位置 i 结尾，最长能多长」，最后再取全局最大。

状态：dp[i] = 以 nums[i] 结尾的最长递增子序列的长度。

怎么求 dp[i]？看 i 前面所有比 nums[i] 小的数 j（即 nums[j] < nums[i]）。 如果选了 nums[i]，那它一定能接在以 nums[j] 结尾的递增子序列后面，长度变成 dp[j] + 1。 我们取所有满足条件的 j 里 dp[j]+1 的最大值；如果前面没有更小的，那 nums[i] 自己开头，长度为 1：

dp[i] = 1
对每一个 j < i 且 nums[j] < nums[i]：
    dp[i] = max(dp[i], dp[j] + 1)

初始化：每个 dp[i] 至少是 1（只包含自己）。答案：不是 dp[n-1]，而是整个 dp 数组的最大值——因为最长子序列不一定以最后一个元素结尾。

参考代码（O(n²) 定义法）

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
        int[] dp = new int[n];
        int ans = 1;                         // 至少有一个元素，长度至少 1
        for (int i = 0; i < n; i++) {
            dp[i] = 1;                       // 初始化：自身构成一个长度为 1 的子序列
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {     // 只有更小的才能接在后面
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);       // 全局最大值，不一定在末尾
        }
        return ans;
    }
}

复杂度（O(n²) 版）：时间 O(n²)（两层循环），空间 O(n)。n ≤ 2500 时可通过。

进阶：O(n log n) 的贪心 + 二分（理解优先级低）

有一个更快但更绕的思路：维护一个数组 tails，tails[k] 表示「长度为 k+1 的递增子序列，其结尾元素能取到的最小值」。 遍历 nums，对每个 x 用二分在 tails 里找第一个 ≥ x 的位置替换掉（保持 tails 递增），x 比所有都大就追加。 tails 的最终长度就是答案。下面给出代码，面试通常 O(n²) 已够，这段代码看懂即可，不必强背：

class Solution {
    public int lengthOfLIS(int[] nums) {
        // tails[k] 存「长度为 k+1 的 LIS 的最小可能结尾」
        int[] tails = new int[nums.length];
        int size = 0;                        // 当前tails有效长度
        for (int x : nums) {
            int lo = 0, hi = size;
            while (lo < hi) {                // 二分找第一个 >= x 的位置
                int mid = (lo + hi) / 2;
                if (tails[mid] < x) lo = mid + 1;
                else hi = mid;
            }
            tails[lo] = x;                   // 替换（或追加）以维持「更小结尾」
            if (lo == size) size++;          // 找到了更长的序列
        }
        return size;
    }
}

10.3最长公共子序列（中等，力扣 1143）

中等 核心：相等取左上 +1，否则取左/上最大

题意：给定两个字符串 text1、text2，求它们的最长公共子序列（LCS）长度，子序列可不连续。 例如 text1 = "abcde"，text2 = "ace"，LCS 是 "ace"，长度 3。

思路推导

两个序列，自然想到二维 dp。状态：dp[i][j] = text1 的前 i 个字符（下标 0..i-1）与 text2 的前 j 个字符（下标 0..j-1）的 LCS 长度。

核心在两字符「相等与否」分两种情形（这是子序列型二维 DP 的标志性分支）：

• 若 text1[i-1] == text2[j-1]：这两个字符可以一起作为公共子序列的结尾。 那么 dp[i][j] = 「去掉这两个字符后的 LCS」+ 1，即 dp[i][j] = dp[i-1][j-1] + 1。 为什么是「左上」？因为 dp[i-1][j-1] 正好是两边都「各退一格」的状态。
• 若不相等：这对字符不能同时选。那 LCS 要么来自「text1 退一格」（dp[i-1][j]），要么来自「text2 退一格」（dp[i][j-1]）， 取较大的：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

为什么相等时取「左上 +1」？因为当前这对匹配字符，是在「两者都还没用到这对字符」的基础上延长出来的公共子序列， 而「两者都没用这对字符」的状态恰好就是同时去掉最后一个字符——即 dp[i-1][j-1]（左上方格）。它不是 dp[i-1][j] 也不是 dp[i][j-1]， 那两个都只退了一边，会把刚匹配的那个字符算漏或重复。

初始化：第 0 行、第 0 列表示「有一个字符串为空」，LCS 长度自然是 0，所以 dp 数组默认 0 即可，不必额外赋值。 从 i=1、j=1 开始填。

参考代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        // dp[i][j]：text1前i个字符 与 text2前j个字符 的 LCS 长度
        int[][] dp = new int[m + 1][n + 1];   // 默认全 0，正好是第0行/列=0
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // 两字符相等：左上方状态 + 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];
    }
}

复杂度：时间 O(m×n)，空间 O(m×n)。两字符串长度都 ≤ 1000，约 10⁶ 次操作，稳。

亲手填一遍：text1="abc"、text2="ac"

把 dp 表画出来，你会更确信「相等取左上、不相等取 max(左,上)」：

      ""  a   c        （表头是 text2 的前 j 个字符）
""    0   0   0
a     0   1   1        a==a -> 左上0+1=1；a!=c -> max(左1,上0)=1
b     0   1   1        b!=a -> max(0,1)=1；b!=c -> max(1,1)=1
c     0   1   2        c!=a -> max(0,1)=1；c==c -> 左上1+1=2

右下角是 2，对应 LCS "ac"。注意第 3 行 c 列：text1 的 'c' 遇到 text2 的 'c' 相等，取的是左上方 dp[2][1]=1 再加 1 = 2—— 左上方正是「text1 前 2 个字符 'ab' 与 text2 前 1 个字符 'a' 的 LCS」，把这对匹配的 'c' 接到它后面，长度 +1。这就是「左上 +1」的几何意义。

10.4分割等和子集：01 背包（中等，力扣 416）

中等 核心：为什么一维背包必须倒序遍历

题意：给你一个正整数数组 nums，问能否把它分成和相等的两部分。例如 nums = [1,5,11,5]，可以分成 [1,5,5] 和 [11]，和都是 11，返回 true。

思路推导（把问题翻译成背包）

能平分，意味着存在一个子集，其和恰好等于 sum / 2。如果 sum 是奇数，直接不可能（返回 false）。 所以问题变成：从数组里选若干个（每个最多选一次）数，能否恰好凑出 sum/2？

这正是一个01 背包：每个数是一件「物品」，它的「重量」和「价值」都等于自己，背包容量 = sum/2， 问能否装满（价值能否达到容量）。每个物品只能选一次，所以是「01」背包（0 个或 1 个）。

状态：用一维数组 dp[j] 表示「能否凑出总和 j」（布尔）。初始化 dp[0] = true（凑出 0 总是可以的，一个都不选）。

转移：对每个数 num，我们要看「选了 num 之后，哪些 j 变得可凑」：如果 dp[j - num] 本来可凑，那 dp[j] 也可凑（j - num + num = j）。即 dp[j] = dp[j] || dp[j - num]。

为什么必须「倒序」遍历 j —— 本题最该讲清的点

关键就在这：每个数 只能选一次。如果我们正序从 num 遍历到容量 target，会发生什么？

正序（错误）：for j = num -> target:
    dp[j] = dp[j] || dp[j - num]
// 当处理到某个 j 时，dp[j-num] 已经被本轮这个 num 更新过了！
// 意味着同一个 num 被「再次使用」了，等价于完全背包，错。

举例：num = 3，target = 6。正序时 j=3 把 dp[3] 置 true；接着 j=6 看 dp[3] 已经是 true，于是 dp[6] 也变 true—— 但这是「用了两次 3」（3+3=6），而 01 背包里 3 只有一个！所以正序会让一个物品被重复选。

倒序则从大到小遍历：当更新 dp[j] 时，它依赖的 dp[j - num] 还是上一轮（没考虑当前 num）的旧值， 从而保证当前 num 在这一轮里最多贡献一次：

倒序（正确）：for j = target -> num (步长 -1):
    dp[j] = dp[j] || dp[j - num]
// 更新 dp[j] 时，dp[j-num] 尚未被本轮修改，仍是上一轮结果

一句话记忆：要「每个物品只用一次」就倒序；要「每个物品可用无限次」就正序（后者是 10.5 的完全背包）。

参考代码

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % 2 != 0) return false;        // 和是奇数，无法平分
        int target = sum / 2;
        // dp[j] 表示「能否凑出总和 j」
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;                           // 凑 0 总是可以（什么都不选）
        for (int num : nums) {                  // 外层遍历每个物品（每个只能选一次）
            // 内层倒序：避免同一个 num 被重复使用
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
}

复杂度：时间 O(n × target)，空间 O(target)。n ≤ 200，target ≤ 20000 量级，约 400 万次，稳。

为什么能压成一维（顺便理解倒序）

01 背包最原始的写法是二维：dp[i][j] 表示「考虑前 i 个物品、容量 j 时能否凑出」。 转移是 dp[i][j] = dp[i-1][j] || dp[i-1][j-num]——注意它只用到上一行 dp[i-1]，从不依赖本行更前的格子。 既然每次只用到上一行，我们就能把两行合并成一行：边算边覆盖，但必须保证「覆盖前用的还是上一行的值」。

倒序遍历恰好满足这点：更新 dp[j] 时，dp[j] 和 dp[j-num] 都还是「还没被第 i 个物品改过」的旧值（即上一行的 dp[i-1]）。 如果正序，dp[j-num] 已经被第 i 个物品改成新值（本行），那就等于用了 dp[i][j-num]，违背了「只用上一行」的前提—— 也就是允许了重复选。所以「倒序」不是玄学，它是「二维压一维时，保证只读上一行」的直接后果。

10.5零钱兑换：完全背包（中等，力扣 322）

中等 核心：与 01 背包唯一区别 = 正序

题意：给定不同面额的硬币 coins 和总金额 amount，每种硬币无限个，求凑出 amount 的最少硬币数；凑不出返回 -1。 例如 coins = [1,2,5], amount = 11，最优 5+5+1 = 11，用 3 个硬币，返回 3。

思路推导

这题和 10.4 几乎一样，只是两点不同：(1) 每种硬币无限个（完全背包）；(2) 求的是「最少个数」而不是「能否」。 把 dp 含义改成「凑出金额 j 的最少硬币数」：

• 初始化：dp[0] = 0（凑 0 用 0 个硬币）；其余设为一个很大的数（表示「暂时凑不出」），用 amount + 1 作上界即可。
• 转移：对每个硬币 coin，dp[j] = min(dp[j], dp[j - coin] + 1)。含义：要么不用这枚硬币（保持 dp[j]），要么用一枚 coin（dp[j-coin] + 1）。

完全背包为什么「正序」

因为硬币无限，我们希望同一个 coin 能被反复使用。正序遍历时，更新 dp[j] 用到的 dp[j-coin] 已经包含了「本轮这个 coin」的贡献， 于是 coin 自然可以叠加多次——这恰恰是我们要的。所以完全背包的内层是正序，与 01 背包恰好相反。

另外注意：本题 coins 在外层循环（每个面额分别处理），amount 在内层。这和「求组合数」的写法（amount 在外、coins 在内）不同， 本题求的是最少个数，两种循环顺序对结果无影响，习惯上把 coins 放外层更直观。

参考代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[j] 表示凑出金额 j 的最少硬币数
        int[] dp = new int[amount + 1];
        // 初始化为一个不可能的大数，表示「暂不可凑出」
        for (int j = 1; j <= amount; j++) dp[j] = amount + 1;
        dp[0] = 0;                              // 凑 0 元用 0 个硬币
        for (int coin : coins) {               // 外层：每种面额
            // 内层正序：同一 coin 可重复使用（完全背包）
            for (int j = coin; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
        // 若仍是初始大数，说明凑不出
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

复杂度：时间 O(coins.length × amount)，空间 O(amount)。amount ≤ 10⁴，完全够。

10.6背包问题一张表总结

背包装类题经常混，下面这张表把「01 vs 完全」「遍历顺序」「适用问题」一次性列清，建议截图背下来：

10.7本专题常见坑

10.8自测题