CS-Notes 中的 Leetcode 动态规划题解：八大题型、状态转移方程与空间优化全解

2026-09-06 15:21:25作者：仰钰奇

本文基于 CS-Notes 仓库中的 Leetcode 题解 - 动态规划展开，系统讲解动态规划（Dynamic Programming, DP）面试高频的八大题型——斐波那契数列、矩阵路径、数组区间、分割整数、最长递增子序列、最长公共子序列、0-1 背包、股票交易与字符串编辑，共覆盖 26 道经典 Leetcode 题目。读完后你能掌握"定义状态 → 写出转移方程 → 处理边界 → 空间压缩"的完整 DP 建模方法，并直接复现仓库中的全部 Java 参考实现。

一、动态规划与递归的本质区别

在开始具体题型之前，先明确动态规划的定位。正如原笔记在开篇（notes/Leetcode 题解 - 动态规划.md）所概括的：

递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。

也就是说，DP 不是"另一种遍历方式"，而是"带记忆的策略"：凡是满足最优子结构、且朴素递归存在大量重复子问题的问题，都可以用一张 dp 表（一维、二维乃至多维）把子问题的答案存下来，将指数级时间压缩到多项式级。

本篇的八类题型正是面试中反复出现的高频模板，它们之间的共性可以归纳为四步：

定义状态：dp[i]（或 dp[i][j]）到底表示什么，必须一句话说清；
推导转移方程：dp 状态只与更小规模的状态有关；
确定初始值与边界：dp[0]、第一行/第一列等；
确定遍历方向与空间优化：一维化时尤其要注意正序/倒序遍历的区别。

下面按题型逐一展开，所有代码均为仓库文档中的 Java 参考实现。

二、斐波那契数列类：线性递推的四种变形

这一类的共同特征是：dp[i] 只由前几项线性组合而来，空间上几乎都可以压缩到 O(1)。

2.1 爬楼梯（70. Climbing Stairs, Easy）

题目描述：有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。

定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp[i] 表示走到第 i 个楼梯的方法数目。第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，因此状态转移方程为：

dp[i] = dp[i-1] + dp[i-2]

考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储，把 O(N) 空间复杂度优化为 O(1)：

public int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    int pre2 = 1, pre1 = 2;
    for (int i = 2; i < n; i++) {
        int cur = pre1 + pre2;
        pre2 = pre1;
        pre1 = cur;
    }
    return pre1;
}

这道题与剑指 Offer 的跳台阶问题同构，仓库中另有 10.3 跳台阶可对照阅读。

2.2 强盗抢劫（198. House Robber, Easy）

题目描述：抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。

定义 dp 数组用来存储最大的抢劫量，dp[i] 表示抢到第 i 个住户时的最大抢劫量。由于不能抢劫邻近住户，如果抢劫了第 i-1 个住户，就不能再抢第 i 个，因此：

dp[i] = max(dp[i-2] + nums[i], dp[i-1])

同样可以用两个变量滚动求解：

public int rob(int[] nums) {
    int pre2 = 0, pre1 = 0;
    for (int i = 0; i < nums.length; i++) {
        int cur = Math.max(pre2 + nums[i], pre1);
        pre2 = pre1;
        pre1 = cur;
    }
    return pre1;
}

2.3 强盗在环形街区抢劫（213. House Robber II, Medium）

环形街区的问题在于"首尾相连"：如果抢了第 0 个住户，就不能抢最后一个；反之亦然。因此问题被拆成两个互斥的线性子问题：

只抢 nums[0..n-2]（包含首、不含尾）
只抢 nums[1..n-1]（包含尾、不含首）

两者取最大值即为答案，注意 n == 0 与 n == 1 的边界处理：

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    if (n == 1) {
        return nums[0];
    }
    return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}

private int rob(int[] nums, int first, int last) {
    int pre2 = 0, pre1 = 0;
    for (int i = first; i <= last; i++) {
        int cur = Math.max(pre1, pre2 + nums[i]);
        pre2 = pre1;
        pre1 = cur;
    }
    return pre1;
}

这个"拆环为链"的技巧在环形数组类问题中是通用手段：枚举环上某个元素"选/不选"，把环形约束消解成线性约束。

2.4 信件错排

题目描述：有 N 个信和信封，它们被打乱，求错误装信方式的数量。

定义 dp 数组存储错误方式数量，dp[i] 表示前 i 个信和信封的错误方式数量。假设第 i 个信装到第 j 个信封里面，而第 j 个信装到第 k 个信封里面。根据 i 和 k 是否相等，分两种情况：

i == k：交换 i 和 j 的信后，它们的信和信封在正确的位置，但其余 i-2 封信有 dp[i-2] 种错误方式。由于 j 有 i-1 种取值，共有 (i-1) * dp[i-2] 种。
i != k：交换 i 和 j 的信后，第 i 个信和信封在正确的位置，其余 i-1 封信有 dp[i-1] 种错误方式。j 有 i-1 种取值，共有 (i-1) * dp[i-1] 种。

综上，错误装信方式数量为：

dp[i] = (i-1) * dp[i-2] + (i-1) * dp[i-1]

2.5 母牛生产（程序员代码面试指南 P181）

题目描述：假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。

第 i 年成熟的牛的数量为：

dp[i] = dp[i-1] + dp[i-3]

含义是：新增的牛 = 三年前（含）已成熟、今年又生了一头的所有母牛，即 dp[i-3]。这一类"带延迟项的斐波那契"递推与爬楼梯的滚动数组写法完全一致。

三、矩阵路径类：二维 DP 的两种经典统计

3.1 矩阵的最小路径和（64. Minimum Path Sum, Medium）

题目描述：求从矩阵左上角到右下角的最小路径和，每次只能向右和向下移动。仓库文档给出的示例：

[[1,3,1],
 [1,5,1],
 [4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

dp[i][j] 表示到达 (i, j) 的最小路径和，它只能从上方 (i-1, j) 或左方 (i, j-1) 走过来，因此 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。由于每个 dp[i][j] 只依赖上一行和左边一列，可用一维数组滚动：

public int minPathSum(int[][] grid) {
    if (grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (j == 0) {
                dp[j] = dp[j];        // 只能从上侧走到该位置
            } else if (i == 0) {
                dp[j] = dp[j - 1];    // 只能从左侧走到该位置
            } else {
                dp[j] = Math.min(dp[j - 1], dp[j]);
            }
            dp[j] += grid[i][j];
        }
    }
    return dp[n - 1];
}

这里有个一维化的小细节：内层循环必须从左往右（正序）遍历，因为 dp[j - 1]（本行左侧）和 dp[j]（上一行同列，尚未覆盖）都必须在更新前保持旧值。

3.2 矩阵的总路径数（62. Unique Paths, Medium）

题目描述：统计从矩阵左上角到右下角的路径总数，每次只能向右或者向下移动。

dp[i][j] 表示到达 (i, j) 的路径数，第一行第一列全为 1，转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1]，同样可一维化：

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[n - 1];
}

此外该问题也可以直接用数学公式求解——它是一个组合问题。机器人总共移动的次数 S = m + n - 2，向下移动的次数 D = m - 1，那么问题等价于从 S 个位置中取出 D 个位置的组合数量，解为 C(S, D)：

public int uniquePaths(int m, int n) {
    int S = m + n - 2;  // 总共的移动次数
    int D = m - 1;      // 向下的移动次数
    long ret = 1;
    for (int i = 1; i <= D; i++) {
        ret = ret * (S - D + i) / i;
    }
    return (int) ret;
}

组合数用"乘除交替"的滚动方式计算（ret * (S-D+i) / i 每一步都整除），可避免直接算阶乘导致溢出，这是对 DP 解法很好的对照：当状态空间本质上是"无记忆的组合计数"时，公式解往往更简洁。

四、数组区间类：前缀和与"以 i 结尾"的状态定义

4.1 数组区间和（303. Range Sum Query - Immutable, Easy）

仓库文档给出的示例：

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

这是前缀和（本质是一维 DP）的入门题：预处理 sum[i] 为 0 ~ i-1 的和，则求区间 i ~ j 的和可以转换为 sum[j + 1] - sum[i]：

class NumArray {

    private int[] sums;

    public NumArray(int[] nums) {
        sums = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
    }

    public int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
}

以 O(N) 的预处理换取 O(1) 的查询，是"用空间换时间"的最直接体现。

4.2 数组中等差递增子区间的个数（413. Arithmetic Slices, Medium）

仓库文档给出的示例：

A = [0, 1, 2, 3, 4]

return: 6, for 3 arithmetic slices in A:

[0, 1, 2],
[1, 2, 3],
[0, 1, 2, 3],
[0, 1, 2, 3, 4],
[ 1, 2, 3, 4],
[2, 3, 4]

dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。当 A[i] - A[i-1] == A[i-1] - A[i-2] 时，[A[i-2], A[i-1], A[i]] 构成一个新的等差子区间；而且在以 A[i-1] 结尾的每一个等差子区间后面再追加 A[i]，同样构成新的等差子区间。仓库文档用如下推演说明这一递推：

dp[2] = 1
    [0, 1, 2]
dp[3] = dp[2] + 1 = 2
    [0, 1, 2, 3], // [0, 1, 2] 之后加一个 3
    [1, 2, 3]     // 新的递增子区间
dp[4] = dp[3] + 1 = 3
    [0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4
    [1, 2, 3, 4],    // [1, 2, 3] 之后加一个 4
    [2, 3, 4]        // 新的递增子区间

综上，在 A[i] - A[i-1] == A[i-1] - A[i-2] 时，dp[i] = dp[i-1] + 1。因为等差子区间不一定以最后一个元素结尾，所以最终返回 dp 数组的累加结果：

public int numberOfArithmeticSlices(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    }
    int n = A.length;
    int[] dp = new int[n];
    for (int i = 2; i < n; i++) {
        if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
            dp[i] = dp[i - 1] + 1;
        }
    }
    int total = 0;
    for (int cnt : dp) {
        total += cnt;
    }
    return total;
}

这个"以 i 结尾 + 最后求和"的建模方式是区间/子序列类 DP 的通用套路，与下文最长递增子序列的定义一脉相承。

五、分割整子类：枚举第一个"切点"

5.1 分割整数的最大乘积（343. Integer Break, Medium）

题目描述：把整数 n 拆成至少两个正整数之和，使它们的乘积最大。For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4)。

定义 dp[i] 为整数 i 分割后的最大乘积。枚举第一个切点 j（1 <= j <= i-1），切下来的 j 既可以不再分割（贡献 j * (i-j)），也可以继续分割（贡献 j * dp[i-j]），因此：

dp[i] = max(dp[i], max(j * dp[i-j], j * (i-j)))

public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i - 1; j++) {
            dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
        }
    }
    return dp[n];
}

该问题在剑指 Offer 中对应"剪绳子"，仓库中有 14. 剪绳子一篇，可结合阅读。

5.2 按平方数来分割整数（279. Perfect Squares, Medium）

题目描述：用完全平方数凑出给定 n，求最少个数。For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9。

dp[i] 表示凑出 i 所需的最少完全平方数个数，枚举不大于 i 的每个平方数 square 作为"最后一块"：dp[i] = min(dp[i-square] + 1)。文档中的实现还利用"连续平方数之差是连续奇数（1+2=3, 3+4=7, ... 差值依次为 3, 5, 7...）"的性质增量生成平方数列表，避免重复计算 k*k：

public int numSquares(int n) {
    List<Integer> squareList = generateSquareList(n);
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int min = Integer.MAX_VALUE;
        for (int square : squareList) {
            if (square > i) {
                break;
            }
            min = Math.min(min, dp[i - square] + 1);
        }
        dp[i] = min;
    }
    return dp[n];
}

private List<Integer> generateSquareList(int n) {
    List<Integer> squareList = new ArrayList<>();
    int diff = 3;
    int square = 1;
    while (square <= n) {
        squareList.add(square);
        square += diff;
        diff += 2;
    }
    return squareList;
}

5.3 分割整数构成字母字符串（91. Decode Ways, Medium）

题目描述：数字字符串按 1~26 映射到字母，求有多少种解码方式。Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12)。

dp[i] 表示前 i 个字符的解码方法数，转移时只考虑最后 1 个字符单独解码、或最后 2 个字符合并解码两种情况；关键边界是含 '0' 的串（如 "06"、"27" 都非法）：

public int numDecodings(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0' ? 0 : 1;
    for (int i = 2; i <= n; i++) {
        int one = Integer.valueOf(s.substring(i - 1, i));
        if (one != 0) {
            dp[i] += dp[i - 1];
        }
        if (s.charAt(i - 2) == '0') {
            continue;
        }
        int two = Integer.valueOf(s.substring(i - 2, i));
        if (two <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}

dp[0] = 1 是一个约定俗成的"空串有一种解码方式"的基准，保证"两个字符合并解码"时 dp[i-2] 有正确的起点。

六、最长递增子序列（LIS）：从 O(N²) 到 O(N log N)

先明确定义：已知一个序列 {S1, S2, ..., Sn}，取出若干数组成新的序列 {Si1, Si2, ..., Sim}，其中 i1、i2 ... im 保持递增，即新序列中各个数仍然保持原数列中的先后顺序，称新序列为原序列的一个子序列。如果在子序列中，当下标 ix > iy 时，Six > Siy，称子序列为原序列的一个递增子序列。

定义 dp 数组存储最长递增子序列的长度，dp[n] 表示以 Sn 结尾的序列的最长递增子序列长度。对于一个递增子序列 {Si1, Si2, ..., Sim}，如果 im < n 并且 Sim < Sn，此时 {Si1, Si2, ..., Sim, Sn} 为一个递增子序列，长度增加 1。满足上述条件的递增子序列中，最长的那个就是要找的，在最长递增子序列上加上 Sn 就构成了以 Sn 为结尾的最长递增子序列，因此：

dp[n] = max{ 1, dp[i] + 1 | Si < Sn && i < n }

之所以要"最小为 1"，是因为求 dp[n] 时可能找不到任何满足条件的递增子序列，此时 {Sn} 自身就构成一个长度为 1 的递增子序列。另外，LIS 不一定以 SN 为结尾，因此需要遍历 dp 数组取最大值，max{ dp[i] | 1 <= i <= N } 才是所求。

6.1 最长递增子序列（300. Longest Increasing Subsequence, Medium）

O(N²) 的朴素解法：

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        int max = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                max = Math.max(max, dp[j] + 1);
            }
        }
        dp[i] = max;
    }
    return Arrays.stream(dp).max().orElse(0);
}

文档中特别提示：使用 Stream 求最大值会导致运行时间过长，可以改成手写循环：

int ret = 0;
for (int i = 0; i < n; i++) {
    ret = Math.max(ret, dp[i]);
}
return ret;

进一步地，可以用二分查找把时间复杂度降为 O(N log N)。定义一个 tails 数组，tails[i] 存储长度为 i+1 的递增子序列的最后一个元素（注意：它始终保存的是"该长度下最小的尾元素"，因此 tails 数组本身保持有序）。对于一个元素 x：

如果它大于 tails 数组所有的值，把它添加到 tails 后面，表示最长递增子序列长度加 1；
如果 tails[i-1] < x <= tails[i]，那么更新 tails[i] = x（用更小的尾元素替换，给后续元素更多接龙空间）。

例如对于数组 [4, 3, 6, 5]：

tails      len      num
[]         0        4
[4]        1        3
[3]        1        6
[3,6]      2        5
[3,5]      2        null

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] tails = new int[n];
    int len = 0;
    for (int num : nums) {
        int index = binarySearch(tails, len, num);
        tails[index] = num;
        if (index == len) {
            len++;
        }
    }
    return len;
}

private int binarySearch(int[] tails, int len, int key) {
    int l = 0, h = len;
    while (l < h) {
        int mid = l + (h - l) / 2;
        if (tails[mid] == key) {
            return mid;
        } else if (tails[mid] > key) {
            h = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

需要强调的是：tails 数组并不是某个真实的子序列（如示例中 [3,5] 中的 3 和 5 在原数组里未必能连成一条链），它的正确读法是"长度恰好为 len 的 LIS 的最小可能尾元素"，这正是它保持有序、从而可用二分的根本原因。

6.2 一组整数对能够构成的最长链（646. Maximum Length of Pair Chain, Medium）

仓库文档给出的示例：

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

题目描述：对于 (a, b) 和 (c, d)，如果 b < c，则它们可以构成一条链。做法是把每对数看作一个"物品"，按左端点排序后套用 LIS 的 O(N²) 框架——若 pairs[j][1] < pairs[i][0]，说明第 j 对可以接在第 i 对前面：

public int findLongestChain(int[][] pairs) {
    if (pairs == null || pairs.length == 0) {
        return 0;
    }
    Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
    int n = pairs.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (pairs[j][1] < pairs[i][0]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Arrays.stream(dp).max().orElse(0);
}

6.3 最长摆动子序列（376. Wiggle Subsequence, Medium）

仓库文档给出的示例：

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

题目要求 O(N) 时间复杂度求解。定义 up 为"以当前元素结尾、最后一步是上升"的摆动子序列长度，down 为"最后一步是下降"的长度，扫描一遍即可：

public int wiggleMaxLength(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int up = 1, down = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            up = down + 1;
        } else if (nums[i] < nums[i - 1]) {
            down = up + 1;
        }
    }
    return Math.max(up, down);
}

相邻相等时两个状态都不更新，等于自动跳过平台段——这体现了 DP 状态设计"让转移条件天然过滤非法情况"的思想。

七、最长公共子序列（LCS）：二维 DP 与 LIS 的对比

对于两个序列 S1 和 S2，找出它们最长的公共子序列。定义一个二维数组 dp，其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符的最长公共子序列的长度。考虑 Si 与 Sj 值是否相等，分两种情况：

当 Si == Sj 时，就能在 S1 前 i-1 个字符与 S2 前 j-1 个字符的 LCS 基础上再加上 Si 这个值，长度加 1，即 dp[i][j] = dp[i-1][j-1] + 1；
当 Si != Sj 时，此时 LCS 为"S1 前 i-1 个字符与 S2 前 j 个字符"或"S1 前 i 个字符与 S2 前 j-1 个字符"两者 LCS 的最大者，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

综上，状态转移方程为：

dp[i][j] = dp[i-1][j-1] + 1,      当 S1_i == S2_j
dp[i][j] = max(dp[i-1][j], dp[i][j-1]),  当 S1_i != S2_j

对于长度为 N 的 S1 和长度为 M 的 S2，dp[N][M] 就是两序列的 LCS 长度。文档中特别对比了 LCS 与 LIS 的三个不同点：

LCS 针对两个序列，求它们的公共子序列；
LIS 中 dp[i] 表示以 Si 为结尾的最长递增子序列长度，子序列必须包含 Si；而 LCS 中 dp[i][j] 表示前 i / 前 j 个字符的 LCS，不一定包含 Si 和 Sj；
求最终解时，LCS 的 dp[N][M] 就是最终解，而 LIS 的 dp[N] 不是最终解，需要遍历 dp 数组找最大者。

7.1 最长公共子序列（1143. Longest Common Subsequence）

public int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (text1.charAt(i - 1) == text2.charAt(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[n1][n2];
}

dp 数组开成 int[n1+1][n2+1]，多出来的第一行第一列天然为 0，等价于"空前缀的 LCS 为 0"的边界条件，避免了单独的初始化代码。

八、0-1 背包：面试出现率最高的 DP 模板

8.0 标准模型、空间优化与贪心不可行的反例

问题模型：有一个容量为 N 的背包，要用这个背包装下价值最大的物品，物品有两个属性：体积 w 和价值 v。

定义一个二维数组 dp，其中 dp[i][j] 表示前 i 件物品、体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w、价值为 v，根据第 i 件物品是否添加到背包中分两种情况：

不添加：dp[i][j] = dp[i-1][j]（总体积不超过 j 的前 i 件物品的最大价值就是前 i-1 件的最大价值）；
添加：dp[i][j] = dp[i-1][j-w] + v。

取两者中的较大者，得到 0-1 背包的状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weights, int[] values) {
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 1; j <= W; j++) {
            if (j >= w) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[N][W];
}

空间优化：观察状态转移方程可以发现，前 i 件物品的状态仅与前 i-1 件有关，因此可以把 dp 定义为一维数组，dp[j] 既表示 dp[i-1][j] 也可以表示 dp[i][j]：

dp[j] = max(dp[j], dp[j-w] + v)

但这里有一个极易踩坑的细节：一维化后 dp[j-w] 在语义上必须表示 dp[i-1][j-w]，所以不能先算 dp[i][j-w]——否则会把旧值覆盖、使同一件物品被装入多次。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]，程序实现时按倒序循环容量即可：

public int knapsack(int W, int N, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = W; j >= 1; j--) {
            if (j >= w) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
    }
    return dp[W];
}

这个"倒序 = 0-1、正序 = 完全"的遍历方向差异，是后文找零钱、单词拆分题中反复用到的核心结论。

为什么 0-1 背包无法使用贪心算法：按性价比 v/w 从高到低依次装入并不保证最优，因为这种方式可能造成背包空间浪费。考虑下面的物品和一个容量为 5 的背包，如果先添加物品 0 再添加物品 1，只能存放价值 16，浪费了大小为 2 的空间；最优方式是存放物品 1 和物品 2，价值为 22：

id	w	v	v/w
0	1	6	6
1	2	10	5
2	3	12	4

0-1 背包的常见变种（文档列出）：

完全背包：物品数量为无限个；
多重背包：物品数量有限制；
多维费用背包：物品不仅有重量还有体积，同时考虑两种限制；
其它：物品之间相互约束或者依赖。

8.1 划分数组为和相等的两部分（416. Partition Equal Subset Sum, Medium）

仓库文档给出的示例：

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

若数组总和为奇数直接无解；否则问题等价于"能否从中选出若干个元素，使其和恰好为 sum/2"——这就是一个背包大小为 sum/2 的 0-1 背包（每个元素只能用一次），dp[i] 为布尔型表示"和 i 是否可达"，倒序遍历保证每个数只用一次：

public boolean canPartition(int[] nums) {
    int sum = computeArraySum(nums);
    if (sum % 2 != 0) {
        return false;
    }
    int W = sum / 2;
    boolean[] dp = new boolean[W + 1];
    dp[0] = true;
    for (int num : nums) {                 // 0-1 背包一个物品只能用一次
        for (int i = W; i >= num; i--) {   // 从后往前，先计算 dp[i] 再计算 dp[i-num]
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[W];
}

private int computeArraySum(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    return sum;
}

8.2 改变一组数的正负号使得它们的和为一给定数（494. Target Sum, Medium）

仓库文档给出的示例：

Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

该问题可以转换为 Subset Sum 问题，从而使用 0-1 背包求解。把整组数看成两部分，P 取正号、N 取负号，推导如下：

                  sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
                       2 * sum(P) = target + sum(nums)

因此只要找到一个子集使正号部分的和等于 (target + sum(nums)) / 2 即可。dp[i] 这里表示"凑出和 i 的方案数"，是 0-1 背包"计数版"（注意 sum < S 或 (sum+S) 为奇数时无解）：

public int findTargetSumWays(int[] nums, int S) {
    int sum = computeArraySum(nums);
    if (sum < S || (sum + S) % 2 == 1) {
        return 0;
    }
    int W = (sum + S) / 2;
    int[] dp = new int[W + 1];
    dp[0] = 1;
    for (int num : nums) {
        for (int i = W; i >= num; i--) {
            dp[i] = dp[i] + dp[i - num];
        }
    }
    return dp[W];
}

private int computeArraySum(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    return sum;
}

文档同时给出了对比用的 DFS（暴力递归，无记忆化，指数级）解法：

public int findTargetSumWays(int[] nums, int S) {
    return findTargetSumWays(nums, 0, S);
}

private int findTargetSumWays(int[] nums, int start, int S) {
    if (start == nums.length) {
        return S == 0 ? 1 : 0;
    }
    return findTargetSumWays(nums, start + 1, S + nums[start])
            + findTargetSumWays(nums, start + 1, S - nums[start]);
}

8.3 01 字符构成最多的字符串（474. Ones and Zeroes, Medium）

仓库文档给出的示例：

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4

Explanation: There are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0"

这是一个多维费用的 0-1 背包：物品是字符串（0 的个数与 1 的个数分别是它的两个"体积"），背包有两个维度 m（可用的 0 数量）和 n（可用的 1 数量），价值都是 1。dp[i][j] 表示在 i 个 0 和 j 个 1 的限制下能构成的字符串最大数量，两维容量都要倒序遍历：

public int findMaxForm(String[] strs, int m, int n) {
    if (strs == null || strs.length == 0) {
        return 0;
    }
    int[][] dp = new int[m + 1][n + 1];
    for (String s : strs) {    // 每个字符串只能用一次
        int ones = 0, zeros = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                zeros++;
            } else {
                ones++;
            }
        }
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
            }
        }
    }
    return dp[m][n];
}

8.4 找零钱的最少硬币数（322. Coin Change, Medium）

仓库文档给出的示例：

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

题目描述：给一些面额的硬币，要求用这些硬币组成给定面额的钱数，且硬币数量最少。硬币可以重复使用。按背包语言映射：

物品：硬币
物品大小：面额
物品价值：数量

因为硬币可以重复使用，这是完全背包问题。完全背包只需要将 0-1 背包的逆序遍历 dp 数组改为正序遍历（同一种硬币可以在更新 dp[i] 时反复使用前面已更新的 dp[i - coin]）：

public int coinChange(int[] coins, int amount) {
    if (amount == 0 || coins == null) return 0;
    int[] dp = new int[amount + 1];
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) { //将逆序遍历改为正序遍历
            if (i == coin) {
                dp[i] = 1;
            } else if (dp[i] == 0 && dp[i - coin] != 0) {
                dp[i] = dp[i - coin] + 1;
            } else if (dp[i - coin] != 0) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == 0 ? -1 : dp[amount];
}

8.5 找零钱的硬币数组合（518. Coin Change 2, Medium）

仓库文档给出的示例：

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

同样是完全背包，但 dp 记录的是"可达成目标的组合数目"而非最少硬币数。注意外层遍历硬币、内层遍历金额：这样统计的是组合（1+2 与 2+1 算同一种）；若内外层交换则统计的是排列：

public int change(int amount, int[] coins) {
    if (coins == null) {
        return 0;
    }
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

8.6 字符串按单词列表分割（139. Word Break, Medium）

仓库文档给出的示例：

s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。与找零钱不同的是，该问题涉及字典中单词的使用顺序——物品必须按一定顺序放入背包中，例如 dict = ["lee", "tc", "cod"] 就不够组成字符串 "leetcode"（因为 cod 接在 lee 后面拼不出 "cod e"... 必须按 s 中出现的先后切分）。

文档给出的结论是：求解有顺序约束的完全背包问题时，对物品的迭代放在最里层，对背包的迭代放在外层，才能保证物品按字符串位置顺序放入：

public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (String word : wordDict) {   // 对物品的迭代应该放在最里层
            int len = word.length();
            if (len <= i && word.equals(s.substring(i - len, i))) {
                dp[i] = dp[i] || dp[i - len];
            }
        }
    }
    return dp[n];
}

8.7 组合总和（377. Combination Sum IV, Medium）

仓库文档给出的示例：

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

这是"涉及顺序"的完全背包计数问题，与 518 题正好相反：这里 (1,2,1) 和 (2,1,1) 算两种不同方案，因此外层遍历金额、内层遍历物品（nums 排序后利用 nums[j] <= i 剪枝）：

public int combinationSum4(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int[] maximum = new int[target + 1];
    maximum[0] = 1;
    Arrays.sort(nums);
    for (int i = 1; i <= target; i++) {
        for (int j = 0; j < nums.length && nums[j] <= i; j++) {
            maximum[i] += maximum[i - nums[j]];
        }
    }
    return maximum[target];
}

至此可以提炼出完全背包的完整遍历规律：

目标	外循环	内循环	内循环方向
组合数（不计顺序），物品无限用	物品	容量	正序
排列数（计顺序），物品无限用	容量	物品	正序（容量递增）
0-1（每件一次）	物品	容量	倒序

九、股票交易类：状态机 DP

股票系列题的共同建模思路是把"持有/不持有股票"抽象为若干状态，每天的状态从昨天的若干状态转移而来。

9.1 需要冷却期的股票交易（309. Best Time to Buy and Sell Stock with Cooldown, Medium）

题目描述：交易之后需要有一天的冷却时间。

仓库文档用四个一维状态数组建模：buy（今天刚买入）、s1（持有着但今天没操作）、sell（今天刚卖出）、s2（今天不持有且不在冷却/无操作），按天推进状态转移：

public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) {
        return 0;
    }
    int N = prices.length;
    int[] buy = new int[N];
    int[] s1 = new int[N];
    int[] sell = new int[N];
    int[] s2 = new int[N];
    s1[0] = buy[0] = -prices[0];
    sell[0] = s2[0] = 0;
    for (int i = 1; i < N; i++) {
        buy[i] = s2[i - 1] - prices[i];
        s1[i] = Math.max(buy[i - 1], s1[i - 1]);
        sell[i] = Math.max(buy[i - 1], s1[i - 1]) + prices[i];
        s2[i] = Math.max(s2[i - 1], sell[i - 1]);
    }
    return Math.max(sell[N - 1], s2[N - 1]);
}

其中冷却期的约束体现在 buy[i] = s2[i - 1] - prices[i]：只能从"昨天卖完之后已冷却"的状态（s2）进入买入状态。

9.2 需要交易费用的股票交易（714. Best Time to Buy and Sell Stock with Transaction Fee, Medium）

仓库文档给出的示例：

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

题目描述：每交易一次，都要支付一定的费用。状态划分与冷却期版本完全同构，只是把约束从"冷却一天"换成"卖出时扣 fee"，体现在 sell[i] 的转移中：

public int maxProfit(int[] prices, int fee) {
    int N = prices.length;
    int[] buy = new int[N];
    int[] s1 = new int[N];
    int[] sell = new int[N];
    int[] s2 = new int[N];
    s1[0] = buy[0] = -prices[0];
    sell[0] = s2[0] = 0;
    for (int i = 1; i < N; i++) {
        buy[i] = Math.max(sell[i - 1], s2[i - 1]) - prices[i];
        s1[i] = Math.max(buy[i - 1], s1[i - 1]);
        sell[i] = Math.max(buy[i - 1], s1[i - 1]) - fee + prices[i];
        s2[i] = Math.max(s2[i - 1], sell[i - 1]);
    }
    return Math.max(sell[N - 1], s2[N - 1]);
}

9.3 只能进行两次的股票交易（123. Best Time to Buy and Sell Stock III, Hard）

限制最多两次完整交易（买+卖）后，状态空间可以进一步压缩为四个标量：第一次买入、第一次卖出、第二次买入、第二次卖出的累计最大收益，按天滚动更新：

public int maxProfit(int[] prices) {
    int firstBuy = Integer.MIN_VALUE, firstSell = 0;
    int secondBuy = Integer.MIN_VALUE, secondSell = 0;
    for (int curPrice : prices) {
        if (firstBuy < -curPrice) {
            firstBuy = -curPrice;
        }
        if (firstSell < firstBuy + curPrice) {
            firstSell = firstBuy + curPrice;
        }
        if (secondBuy < firstSell - curPrice) {
            secondBuy = firstSell - curPrice;
        }
        if (secondSell < secondBuy + curPrice) {
            secondSell = secondBuy + curPrice;
        }
    }
    return secondSell;
}

四个变量的更新必须严格按 buy → sell → buy → sell 的顺序进行，保证"第二次买入一定发生在第一次卖出之后"的时序约束。

9.4 只能进行 k 次的股票交易（188. Best Time to Buy and Sell Stock IV, Hard）

k 次交易的通用解法把状态展开为二维数组 maxProfit[i][j]（前 i 次交易、看到第 j 天为止的最大利润），用 localMax 维护"第 i 次交易在历史最优时机买入后的净头寸"：

public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) {   // 这种情况下该问题退化为普通的股票交易问题
        int maxProfit = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
    int[][] maxProfit = new int[k + 1][n];
    for (int i = 1; i <= k; i++) {
        int localMax = maxProfit[i - 1][0] - prices[0];
        for (int j = 1; j < n; j++) {
            maxProfit[i][j] = Math.max(maxProfit[i][j - 1], prices[j] + localMax);
            localMax = Math.max(localMax, maxProfit[i - 1][j] - prices[j]);
        }
    }
    return maxProfit[k][n - 1];
}

文档中特别处理了 k >= n / 2 的退化情形：n 天最多只能完成 n/2 次完整交易，此时交易次数约束实际上不起作用，退化为"无限次交易"的贪心解——把每一段上升区间的利润全部吃进（遍历一遍，prices[i] > prices[i-1] 时累加差价）。这是一个很好的启示：DP 之前先看约束是否实质生效，很多限制条件在参数范围外会退化成更简单的问题。

十、字符串编辑类：LCS 的三种应用

10.1 删除两个字符串的字符使它们相等（583. Delete Operation for Two Strings, Medium）

仓库文档给出的示例：

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

可以转换为求两个字符串的 LCS 问题：两个串最终都要删到"公共子序列"，删除次数 = 各自长度减去 2 倍 LCS 长度：

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return m + n - 2 * dp[m][n];
}

10.2 编辑距离（72. Edit Distance, Hard）

仓库文档给出的示例：

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

题目描述：修改一个字符串成为另一个字符串，使得修改次数最少。一次修改操作包括：插入一个字符、删除一个字符、替换一个字符。

dp[i][j] 表示 word1 前 i 个字符变为 word2 前 j 个字符的最少操作数。字符相等时 dp[i][j] = dp[i-1][j-1]；不等时取三种操作的最小值加 1（dp[i-1][j-1] 对应替换、dp[i][j-1] 对应插入、dp[i-1][j] 对应删除）。第一行第一列需要显式初始化（把长度 i 的串变成空串需要 i 次操作）：

public int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null) {
        return 0;
    }
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int i = 1; i <= n; i++) {
        dp[0][i] = i;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
            }
        }
    }
    return dp[m][n];
}

10.3 复制粘贴字符（650. 2 Keys Keyboard, Medium）

题目描述：最开始只有一个字符 A，问需要多少次操作能够得到 n 个字符 A，每次操作可以复制当前所有的字符，或者粘贴。

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

仓库文档给出了两种实现。递归版：找 n 的最小因子 i，答案 = i + f(n/i)（一次复制 + i-1 次粘贴得到 i 份，然后对每份递归放大），找不到因子说明 n 是质数，只能一步步粘贴 n 次：

public int minSteps(int n) {
    if (n == 1) return 0;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return i + minSteps(n / i);
    }
    return n;
}

DP 版把 f(i) 展开成一维表，对每个 i 找最小因子 j 后 dp[i] = dp[j] + dp[i/j]：

public int minSteps(int n) {
    int[] dp = new int[n + 1];
    int h = (int) Math.sqrt(n);
    for (int i = 2; i <= n; i++) {
        dp[i] = i;
        for (int j = 2; j <= h; j++) {
            if (i % j == 0) {
                dp[i] = dp[j] + dp[i / j];
                break;
            }
        }
    }
    return dp[n];
}

十一、如何在 CS-Notes 中继续扩展动态规划训练

本篇对应仓库 Leetcode 题解 - 目录中"算法思想"板块下的动态规划一篇，该目录精选了约 200 道题目并按算法思想与数据结构划分，可结合以下笔记交叉训练：

Leetcode 题解 - 二分查找：LIS 的 O(N log N) 解法依赖二分查找 tails 数组；
Leetcode 题解 - 搜索：Target Sum 的 DFS 解法是搜索与 DP 的对照样本；
Leetcode 题解 - 数学：Unique Paths 的组合数学解法属于该板块；
Leetcode 题解 - 贪心思想：对照 0-1 背包"贪心为何不可行"的反例，理解 DP 与贪心的分界；
剑指 Offer 系列中的 10.1 斐波那契数列、10.3 跳台阶、14. 剪绳子：分别是本篇爬楼梯、爬楼梯、整数分拆的同源题，可从目录剑指 Offer 题解 - 目录找到完整系列。

最后把全文的建模要点浓缩为一张速查表：

题型	状态定义	关键转移	空间/遍历要点
斐波那契类	dp[i]：第 i 项的值	由前 1~3 项线性组合	滚动变量，O(1) 空间
矩阵路径	dp[i][j]：到达 (i,j) 的最优值/路径数	上方 + 左方	一维滚动，内层正序
数组区间	dp[i]：以 i 结尾的区间数	dp[i] = dp[i-1] + 1（条件成立时）	最终求 dp 总和
分割整数	dp[i]：拆分 i 的最优结果	枚举第一个切点 j	O(N²)
LIS	dp[i]：以 i 结尾的最长长度	max{dp[j]+1 \| nums[j]<nums[i]}	tails + 二分降至 O(N log N)
LCS	dp[i][j]：前 i / 前 j 的公共长度	相等取对角+1，不等取上/左最大	结果在 dp[n1][n2]
0-1 背包	dp[j]：容量 j 的最大价值	max(dp[j], dp[j-w]+v)	一维 + 倒序容量
完全背包（计数/最少）	dp[j]：容量 j 的方案数/最少件数	dp[j] = dp[j] + dp[j-w] 等	一维 + 正序容量；"计顺序"时物品移到内层
股票交易	每天的 buy/sell 状态值	状态机逐日转移	可用标量压缩为 O(1)
字符串编辑	dp[i][j]：前缀间的最小编辑代价	对角/上/左三向转移	LCS 变体直接套模板