动态规划

1. 初探动态规划

动态规划(dynamic programming)是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。在本节中，我们从一个经典例题入手，先给出它的暴力回溯解法，观察其中包含的重叠子问题，再逐步导出更高效的动态规划解法。 爬楼梯问题： 给定一个共有n阶的楼梯，你每步可以上1阶或者2阶，请问有多少种方案可以爬到楼顶？如图所示，对于一个3阶楼梯，共有3种方案可以爬到楼顶。
本题的目标是求解方案数量，我们可以考虑通过回溯来穷举所有可能性。具体来说，将爬楼梯想象为一个多轮选择的过程：从地面出发，每轮选择上1阶或2阶，每当到达楼梯顶部时就将方案数量加1，当越过楼梯顶部时就将其剪枝。代码如下所示：

/* 回溯 */
void backtrack(List<Integer> choices, int state, int n, List<Integer> res) {
    // 当爬到第 n 阶时，方案数量加 1
    if (state == n)
        res.set(0, res.get(0) + 1);
    // 遍历所有选择
    for (Integer choice : choices) {
        // 剪枝：不允许越过第 n 阶
        if (state + choice > n)
            continue;
        // 尝试：做出选择，更新状态
        backtrack(choices, state + choice, n, res);
        // 回退
    }
}

/* 爬楼梯：回溯 */
int climbingStairsBacktrack(int n) {
    List<Integer> choices = Arrays.asList(1, 2); // 可选择向上爬 1 阶或 2 阶
    int state = 0; // 从第 0 阶开始爬
    List<Integer> res = new ArrayList<>();
    res.add(0); // 使用 res[0] 记录方案数量
    backtrack(choices, state, n, res);
    return res.get(0);
}

1.2 方法一：暴力搜索

回溯算法通常并不显式地对问题进行拆解，而是将求解问题看作一系列决策步骤，通过试探和剪枝，搜索所有可能的解。我们可以尝试从问题分解的角度分析这道题。设爬到第i阶共有dp[i]种方案，那么dp[i]就是原问题，其子问题包括： 由于每轮只能上1阶或2阶，因此当我们站在第i阶楼梯上时，上一轮只可能站在第i-1阶或第i-2阶上。换句话说，我们只能从第i-1阶或第i-2阶迈向第i阶。由此便可得出一个重要推论：爬到第i-1阶的方案数加上爬到第i-2阶的方案数就等于爬到第i阶的方案数。公式如下： 这意味着在爬楼梯问题中，各个子问题之间存在递推关系，原问题的解可以由子问题的解构建得来。下图展示了该递推关系：
 我们可以根据递推公式得到暴力搜索解法。以dp[n]为起始点，递归地将一个较大问题拆解为两个较小问题的和，直至到达最小子问题dp[1]和dp[2]时返回。其中，最小子问题的解是已知的，即dp[1]=1、dp[2]=2，表示爬到第1、2阶分别有1、2种方案。观察以下代码，它和标准回溯代码都属于深度优先搜索，但更加简洁：

/* 搜索 */
int dfs(int i) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i == 1 || i == 2)
        return i;
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(i - 1) + dfs(i - 2);
    return count;
}

/* 爬楼梯：搜索 */
int climbingStairsDFS(int n) {
    return dfs(n);
}

下图展示了暴力搜索形成的递归树。对于问题dp[n]，其递归树的深度为n，时间复杂度为O(2ⁿ)。指数阶属于爆炸式增长，如果我们输入一个比较大的n，则会陷入漫长的等待之中。
观察下图，指数阶的时间复杂度是"重叠子问题"导致的。例如的dp[9]被分解为dp[8]和dp[7]，dp[8]被分解为dp[7]和dp[6]，两者都包含子问题dp[7]。以此类推，子问题中包含更小的重叠子问题，子子孙孙无穷尽也。绝大部分计算资源都浪费在这些重叠的子问题上。

1.3 方法二：记忆化搜索

为了提升算法效率，我们希望所有的重叠子问题都只被计算一次。为此，我们声明一个数组mem来记录每个子问题的解，并在搜索过程中将重叠子问题剪枝:

1. 当首次计算dp[i]时，我们将其记录至mem[i] ，以便之后使用。
2. 当再次需要计算dp[i]时，我们便可直接从mem[i]中获取结果，从而避免重复计算该子问题。

/* 记忆化搜索 */
int dfs(int i, int[] mem) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i == 1 || i == 2)
        return i;
    // 若存在记录 dp[i] ，则直接返回之
    if (mem[i] != -1)
        return mem[i];
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(i - 1, mem) + dfs(i - 2, mem);
    // 记录 dp[i]
    mem[i] = count;
    return count;
}

/* 爬楼梯：记忆化搜索 */
int climbingStairsDFSMem(int n) {
    // mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
    int[] mem = new int[n + 1];
    Arrays.fill(mem, -1);
    return dfs(n, mem);
}

观察下图，经过记忆化处理后，所有重叠子问题都只需计算一次，时间复杂度优化至O(n)，这是一个巨大的飞跃。

1.4 方法三：动态规划

记忆化搜索是一种"从顶至底"的方法：我们从原问题(根节点)开始，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题(叶节点)。之后，通过回溯逐层收集子问题的解，构建出原问题的解。与之相反，动态规划是一种"从底至顶"的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。在以下代码中，我们初始化一个数组dp来存储子问题的解，它起到了与记忆化搜索中数组mem相同的记录作用：

/* 爬楼梯：动态规划 */
int climbingStairsDP(int n) {
    if (n == 1 || n == 2)
        return n;
    // 初始化 dp 表，用于存储子问题的解
    int[] dp = new int[n + 1];
    // 初始状态：预设最小子问题的解
    dp[1] = 1;
    dp[2] = 2;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

下图模拟了以上代码的执行过程：
与回溯算法一样，动态规划也使用"状态"概念来表示问题求解的特定阶段，每个状态都对应一个子问题以及相应的局部最优解。例如，爬楼梯问题的状态定义为当前所在楼梯阶数i。根据以上内容，我们可以总结出动态规划的常用术语:

• 将数组dp称为dp表，dp[i]表示状态i对应子问题的解。
• 将最小子问题对应的状态(第1阶和第2阶楼梯)称为初始状态。
• 将递推公式dp[i]=dp[i-1]+dp[i-2]称为状态转移方程。

1.5 空间优化

细心的读者可能发现了，由于dp[i]只与dp[i-1]和dp[i-2]有关，因此我们无须使用一个数组dp来存储所有子问题的解，而只需两个变量滚动前进即可。代码如下所示：

/* 爬楼梯：空间优化后的动态规划 */
int climbingStairsDPComp(int n) {
    if (n == 1 || n == 2)
        return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = a + b;
        a = tmp;
    }
    return b;
}

观察以上代码，由于省去了数组dp占用的空间，因此空间复杂度从O(n)降至O(1)。在动态规划问题中，当前状态往往仅与前面有限个状态有关，这时我们可以只保留必要的状态，通过"降维"来节省内存空间。这种空间优化技巧被称为"滚动变量"或"滚动数组"。

2. 动态规划问题特性

在上一节中，我们学习了动态规划是如何通过子问题分解来求解原问题的。实际上，子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同：

• 分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。
• 动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。
• 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题。

实际上，动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构、无后效性。

2.1 最优子结构

我们对爬楼梯问题稍作改动，使之更加适合展示最优子结构概念。
问题一：给定一个楼梯，你每步可以上1阶或者2阶，每一阶楼梯上都贴有一个非负整数，表示你在该台阶所需要付出的代价。给定一个非负整数数组cost，其中cost0[i]表示在第i个台阶需要付出的代价，cost[0]为地面(起始点)。请计算最少需要付出多少代价才能到达顶部？
如图所示，若第1、2、3阶的代价分别为1、10、1，则从地面爬到第3阶的最小代价为2。
设dp[i]为爬到第i阶累计付出的代价，由于第i阶只可能从i-1阶或i-2阶走来，因此dp[i]只可能等于dp[i-1]+cost[i]或dp[i-2]+cost[i]。为了尽可能减少代价，我们应该选择两者中较小的那一个：
这便可以引出最优子结构的含义：原问题的最优解是从子问题的最优解构建得来的。本题显然具有最优子结构：我们从两个子问题最优解dp[i-1]和dp[i-2]中挑选出较优的那一个，并用它构建出原问题dp[i]的最优解。
那么，上一节的爬楼梯题目有没有最优子结构呢？它的目标是求解方案数量，看似是一个计数问题，但如果换一种问法："求解最大方案数量"。我们意外地发现，虽然题目修改前后是等价的，但最优子结构浮现出来了：第n阶最大方案数量等于第n-1阶和第n-2阶最大方案数量之和。所以说，最优子结构的解释方式比较灵活，在不同问题中会有不同的含义。 根据状态转移方程，以及初始状态dp[1]=cost[1]和dp[2]=cost[2]，我们就可以得到动态规划代码：

/* 爬楼梯最小代价：动态规划 */
int minCostClimbingStairsDP(int[] cost) {
    int n = cost.length - 1;
    if (n == 1 || n == 2)
        return cost[n];
    // 初始化 dp 表，用于存储子问题的解
    int[] dp = new int[n + 1];
    // 初始状态：预设最小子问题的解
    dp[1] = cost[1];
    dp[2] = cost[2];
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return dp[n];
}

下图展示了以上代码的动态规划过程。
本题也可以进行空间优化，将一维压缩至零维，使得空间复杂度从O(n)降至O(1)：

/* 爬楼梯最小代价：空间优化后的动态规划 */
int minCostClimbingStairsDPComp(int[] cost) {
    int n = cost.length - 1;
    if (n == 1 || n == 2)
        return cost[n];
    int a = cost[1], b = cost[2];
    for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = Math.min(a, tmp) + cost[i];
        a = tmp;
    }
    return b;
}

2.2 无后效性

无后效性是动态规划能够有效解决问题的重要特性之一，其定义为：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关。以爬楼梯问题为例，给定状态i，它会发展出状态i+1和状态i+2，分别对应跳1步和跳2步。在做出这两种选择时，我们无须考虑状态i之前的状态，它们对状态i的未来没有影响。然而，如果我们给爬楼梯问题添加一个约束，情况就不一样了。
问题二：给定一个共有n阶的楼梯，你每步可以上1阶或者2阶，但不能连续两轮跳1阶，请问有多少种方案可以爬到楼顶？
如图所示，爬上第3阶仅剩2种可行方案，其中连续三次跳1阶的方案不满足约束条件，因此被舍弃。
在该问题中，如果上一轮是跳1阶上来的，那么下一轮就必须跳2阶。这意味着，下一步选择不能由当前状态(当前所在楼梯阶数)独立决定，还和前一个状态(上一轮所在楼梯阶数)有关。不难发现，此问题已不满足无后效性，状态转移方程dp[i]=dp[i-1]+dp[i-2]也失效了，因为dp[i-1]代表本轮跳1阶，但其中包含了许多"上一轮是跳1阶上来的"方案，而为了满足约束，我们就不能将dp[i-1]直接计入dp[i]中。
为此，我们需要扩展状态定义：状态[i,j]表示处在第i阶并且上一轮跳了j阶，其中j∈{1,2}。此状态定义有效地区分了上一轮跳了1阶还是2阶，我们可以据此判断当前状态是从何而来的。

• 当上一轮跳了1阶时，上上一轮只能选择跳2阶，即dp[i,1]只能从dp[i-1, 2]转移过来。
• 当上一轮跳了2阶时，上上一轮可选择跳1阶或跳2阶，即dp[i,2]可以从dp[i-2,1]或dp[i-2,2]转移过来。
  如图所示，在该定义下，dp[i,j]表示状态[i,j]对应的方案数。此时状态转移方程为：
  最终，返回dp[n,1]+dp[n,2]即可，两者之和代表爬到第n阶的方案总数：

/* 带约束爬楼梯：动态规划 */
int climbingStairsConstraintDP(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    // 初始化 dp 表，用于存储子问题的解
    int[][] dp = new int[n + 1][3];
    // 初始状态：预设最小子问题的解
    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[2][1] = 0;
    dp[2][2] = 1;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i][1] = dp[i - 1][2];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
    }
    return dp[n][1] + dp[n][2];
}

在上面的案例中，由于仅需多考虑前面一个状态，因此我们仍然可以通过扩展状态定义，使得问题重新满足无后效性。然而，某些问题具有非常严重的"有后效性"。
问题三： 给定一个共有n阶的楼梯，你每步可以上1阶或者2阶。规定当爬到第i阶时，系统自动会在第2i阶上放上障碍物，之后所有轮都不允许跳到第2i阶上。例如，前两轮分别跳到了第2、3阶上，则之后就不能跳到第4、6阶上。请问有多少种方案可以爬到楼顶？
在这个问题中，下次跳跃依赖过去所有的状态，因为每一次跳跃都会在更高的阶梯上设置障碍，并影响未来的跳跃。对于这类问题，动态规划往往难以解决。实际上，许多复杂的组合优化问题(例如旅行商问题)不满足无后效性。对于这类问题，我们通常会选择使用其他方法，例如启发式搜索、遗传算法、强化学习等，从而在有限时间内得到可用的局部最优解。

3. 动态规划解题思路

3.1 问题判断

总的来说，如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常适合用动态规划求解。然而，我们很难从问题描述中直接提取出这些特性。因此我们通常会放宽条件，先观察问题是否适合使用回溯(穷举)解决。适合用回溯解决的问题通常满足"决策树模型"，这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。换句话说，如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯来解决。

3.2 问题求解步骤

动态规划的解题流程会因问题的性质和难度而有所不同，但通常遵循以下步骤：描述决策，定义状态，建立dp表，推导状态转移方程，确定边界条件等。为了更形象地展示解题步骤，我们使用一个经典问题"最小路径和"来举例。 问题四：给定一个nXn的二维网格grid ，网格中的每个单元格包含一个非负整数，表示该单元格的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。请返回从左上角到右下角的最小路径和。
下图展示了一个例子，给定网格的最小路径和为13。

1. 第一步：思考每轮的决策，定义状态，从而得到dp表
   本题的每一轮的决策就是从当前格子向下或向右走一步。设当前格子的行列索引为[i,j]，则向下或向右走一步后，索引变为[i+1,j]或[i,j+1]。因此，状态应包含行索引和列索引两个变量，记为[i,j]。
   状态[i,j]对应的子问题为：从起始点[0.0]走到[i,j]的最小路径之和，解记为dp[i,j]。走到[i,j]的最小路径和，解记为dp[i,j]。至此，我们就得到了下图所示的二维dp矩阵，其尺寸与输入网格相同。

提示

动态规划和回溯过程可以描述为一个决策序列，而状态由所有决策变量构成。它应当包含描述解题进度的所有变量，其包含了足够的信息，能够用来推导出下一个状态。每个状态都对应一个子问题，我们会定义一个表来存储所有子问题的解，状态的每个独立变量都是dp表的一个维度。从本质上看，dp表是状态和子问题的解之间的映射。

2. 第二步：找出最优子结构，进而推导出状态转移方程
   对于状态[i,j]，它只能从上边格子[i-1]和左边格子[i,j-1]转移而来。因此最优子结构为：到达[i,j]的最小路径和由[i-1,j]的最小路径和与[i-1,j]的最小路径和中较小的那一个决定。根据以上分析，可推出下图所示的状态转移方程：

提示

根据定义好的dp表，思考原问题和子问题的关系，找出通过子问题的最优解来构造原问题的最优解的方法，即最优子结构。一旦我们找到了最优子结构，就可以使用它来构建出状态转移方程。

3. 第三步：确定边界条件和状态转移顺序
   在本题中，处在首行的状态只能从其左边的状态得来，处在首列的状态只能从其上边的状态得来，因此首行i=0和首列j=0是边界条件。如图所示，由于每个格子是由其左方格子和上方格子转移而来，因此我们使用循环来遍历矩阵，外循环遍历各行，内循环遍历各列。
   

提示

边界条件在动态规划中用于初始化dp表，在搜索中用于剪枝。状态转移顺序的核心是要保证在计算当前问题的解时，所有它依赖的更小子问题的解都已经被正确地计算出来。

根据以上分析，我们已经可以直接写出动态规划代码。然而子问题分解是一种从顶至底的思想，因此按照"暴力搜索->记忆化搜索->动态规划"的顺序实现更加符合思维习惯。

3.3 暴力搜索

从状态[i,j]开始搜索，不断分解为更小的状态[i-1,j]和[i,j-1]，递归函数包括以下要素:

• 递归参数：状态[i,j]。
• 返回值：从[0,0]到[i,j]的最小路径和dp[i,j]。
• 终止条件：当i=0且j=0时，返回代价grid[0，0]。
• 剪枝：当i<0时或j<0时索引越界，此时返回代价+∞，代表不可行。

/* 最小路径和：暴力搜索 */
int minPathSumDFS(int[][] grid, int i, int j) {
    // 若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) {
        return Integer.MAX_VALUE;
    }
    // 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
    int up = minPathSumDFS(grid, i - 1, j);
    int left = minPathSumDFS(grid, i, j - 1);
    // 返回从左上角到 (i, j) 的最小路径代价
    return Math.min(left, up) + grid[i][j];
}

下图给出了以dp[2,1]为根节点的递归树，其中包含一些重叠子问题，其数量会随着网格grid的尺寸变大而急剧增多。从本质上看，造成重叠子问题的原因为：存在多条路径可以从左上角到达某一单元格。

每个状态都有向下和向右两种选择，从左上角走到右下角总共需要m+n-2步，所以最差时间复杂度为O(2ᵐ⁺ⁿ)。请注意，这种计算方式未考虑临近网格边界的情况，当到达网络边界时只剩下一种选择，因此实际的路径数量会少一些。

3.4 记忆化搜索

我们引入一个和网格grid相同尺寸的记忆列表mem，用于记录各个子问题的解，并将重叠子问题进行剪枝：

/* 最小路径和：记忆化搜索 */
int minPathSumDFSMem(int[][] grid, int[][] mem, int i, int j) {
    // 若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) {
        return Integer.MAX_VALUE;
    }
    // 若已有记录，则直接返回
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // 左边和上边单元格的最小路径代价
    int up = minPathSumDFSMem(grid, mem, i - 1, j);
    int left = minPathSumDFSMem(grid, mem, i, j - 1);
    // 记录并返回左上角到 (i, j) 的最小路径代价
    mem[i][j] = Math.min(left, up) + grid[i][j];
    return mem[i][j];
}

如图所示，在引入记忆化后，所有子问题的解只需计算一次，因此时间复杂度取决于状态总数，即网格尺寸O(mn):

3.5 动态规划

基于迭代实现动态规划解法，代码如下所示：

/* 最小路径和：动态规划 */
int minPathSumDP(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    // 初始化 dp 表
    int[][] dp = new int[n][m];
    dp[0][0] = grid[0][0];
    // 状态转移：首行
    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // 状态转移：首列
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // 状态转移：其余行和列
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}

下图展示了最小路径和的状态转移过程，其遍历了整个网格，因此时间复杂度为O(mn)。数组dp大小为nXm，因此空间复杂度为O(mn)。

3.6 空间优化

由于每个格子只与其左边和上边的格子有关，因此我们可以只用一个单行数组来实现dp表。请注意，因为数组dp只能表示一行的状态，所以我们无法提前初始化首列状态，而是在遍历每行时更新它：

/* 最小路径和：空间优化后的动态规划 */
int minPathSumDPComp(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    // 初始化 dp 表
    int[] dp = new int[m];
    // 状态转移：首行
    dp[0] = grid[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // 状态转移：其余行
    for (int i = 1; i < n; i++) {
        // 状态转移：首列
        dp[0] = dp[0] + grid[i][0];
        // 状态转移：其余列
        for (int j = 1; j < m; j++) {
            dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}

4. 0-1背包问题

背包问题是一个非常好的动态规划入门题目，是动态规划中最常见的问题形式。其具有很多变种，例如0-1背包问题、完全背包问题、多重背包问题等。
问题一：给定n个物品，第i个物品的重量为wgt[i-1]、价值为val[i-1]，和一个容量为cap的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。
观察下图，由于物品编号i从1开始计数，数组索引从0开始计数，因此物品i对应重量wgt[i-1]和价值val[i-1]。
我们可以将0-1背包问题看作一个由n轮决策组成的过程，对于每个物体都有不放入和放入两种决策，因此该问题满足决策树模型。该问题的目标是求解"在限定背包容量下能放入物品的最大价值"，因此较大概率是一个动态规划问题。

1. 第一步：思考每轮的决策，定义状态，从而得到dp表
   对于每个物品来说，不放入背包，背包容量不变；放入背包，背包容量减小。由此可得状态定义：当前物品编号i和背包容量c，记为[i,c]。状态[i,c]对应的子问题为：前i个物品在容量为c的背包中的最大价值，记为dp[i,c]。待求解的是dp[n,cap]，因此需要一个尺寸为(n+1)x(cap+1)的二维dp表。
2. 找出最优子结构，进而推导出状态转移方程
   当我们做出物品i的决策后，剩余的是前i-1个物品决策的子问题，可分为以下两种情况:

• 不放入物品i：背包容量不变，状态变化为[i-1,c]。
• 放入物品i: 背包容量减少wgt[i-1],价值增加val[i-1],状态变化为[i-1,c-wgt[i-1]]。
  上述分析向我们揭示了本题的最优子结构：最大价值dp[i,c]等于不放入物品i和放入物品i两种方案中价值更大的那一个。由此可推导出状态转移方程： 需要注意的是，若当前物品重量wgt[i-1]超出剩余背包容量c,则只能选择不放入背包。

3. 确定边界条件和状态转移顺序
   当无物品或背包容量为0时最大价值为0，即首列dp[i,0]和首行dp[0,c]都等于0。当前状态[i,c]从上方的状态[i-1,c]和左上方的状态[i-1,c-wgt[i-1]]转移而来，因此通过两层循环正序遍历整个dp表即可。根据以上分析，我们接下来按顺序实现暴力搜索、记忆化搜索、动态规划解法。

4.1 暴力搜索

搜索代码包含以下要素：

• 递归参数：状态[i,c]
• 返回值：子问题的解dp[i,c]
• 终止条件: 当物品编号越界i=0或背包剩余容量为0时，终止递归并返回价值0。
• 剪枝：若当前物品重量超出背包剩余容量，则只能选择不放入背包。

/* 0-1 背包：暴力搜索 */
int knapsackDFS(int[] wgt, int[] val, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return Math.max(no, yes);
}

如图所示，由于每个物品都会产生不选和选两条搜索分支，因此时间复杂度为O(2ⁿ)。观察递归树，容易发现其中存在重叠子问题，例如dp[1,10]等。而当物品较多、背包容量较大，尤其是相同重量的物品较多时，重叠子问题的数量将会大幅增多。

4.2 记忆化搜索

为了保证重叠子问题只被计算一次，我们借助记忆列表mem来记录子问题的解，其中mem[i][c]对应dp[i,c]。引入记忆化之后，时间复杂度取决于子问题数量，也就是O(nxcap)。实现代码如下：

/* 0-1 背包：记忆化搜索 */
int knapsackDFSMem(int[] wgt, int[] val, int[][] mem, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) {
        return 0;
    }
    // 若已有记录，则直接返回
    if (mem[i][c] != -1) {
        return mem[i][c];
    }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, mem, i - 1, c);
    }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
    int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = Math.max(no, yes);
    return mem[i][c];
}

下图展示了在记忆化搜索中被剪掉的搜索分支。

4.3 动态规划

动态规划实质上就是在状态转移中填充dp表的过程，代码如下所示：

/* 0-1 背包：动态规划 */
int knapsackDP(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

如图所示，时间复杂度和空间复杂度都由数组dp大小决定，即O(nxcap)。

4.4 空间优化

由于每个状态都只与其上一行的状态有关，因此我们可以使用两个数组滚动前进，将空间复杂度从O(n²)降至O(n)。进一步思考，我们能否仅用一个数组实现空间优化呢？观察可知，每个状态都是由正上方或左上方的格子转移过来的。假设只有一个数组，当开始遍历第i行时，该数组存储的仍然是第i-1行的状态。

• 如果采取正序遍历，那么遍历到dp[i,j]时，左上方dp[i-1,1]~dp[i-1,j-1]值可能已经被覆盖，此时就无法得到正确的状态转移结果。
• 如果采取倒序遍历，则不会发生覆盖问题，状态转移可以正确进行。
  下图展示了在单个数组下从第i=1行转换至第i=2行的过程。请思考正序遍历和倒序遍历的区别。在代码实现中，我们仅需将数组dp的第一维i直接删除，并且把内循环更改为倒序遍历即可：
  

/* 0-1 背包：空间优化后的动态规划 */
int knapsackDPComp(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[] dp = new int[cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        // 倒序遍历
        for (int c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

5. 完全背包问题

在本节中，我们先求解另一个常见的背包问题：完全背包，再了解它的一种特例：零钱兑换。 问题一：给定n个物品，第i个物品的重量为wgt[i-1]、价值为val[i-1]，和一个容量为cap的背包。每个物品可以重复选取，问在限定背包容量下能放入物品的最大价值。

5.1 动态规划思路

完全背包问题和0-1背包问题非常相似，区别仅在于不限制物品的选择次数。

• 在0-1背包问题中，每种物品只有一个，因此将物品i放入背包后，只能从前i-1个物品中选择。
• 在完全背包问题中，每种物品的数量是无限的，因此将物品i放入背包后，仍可以从前i个物品中选择。

在完全背包问题的规定下，状态[i,c]的变化分为两种情况:

• 不放入物品i：与0-1背包问题相同，转移至[i-1,c]。
• 放入物品：与0-1背包问题不同，转移至[i,c-wgt[i-1]]。
  从而状态转移方程变为：
  

/* 完全背包：动态规划 */
int unboundedKnapsackDP(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

对比两道题目的代码，状态转移中有一处从i-1变为i，其余完全一致。

5.2 空间优化

由于当前状态是从左边和上边的状态转移而来的，因此空间优化后应该对dp表中的每一行进行正序遍历。这个遍历顺序与0-1背包正好相反。
代码实现比较简单，仅需将数组dp的第一维删除：

/* 完全背包：空间优化后的动态规划 */
int unboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[] dp = new int[cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[c] = dp[c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

5.3 零钱兑换问题

背包问题是一大类动态规划问题的代表，其拥有很多变种，例如零钱兑换问题。
问题二： 给定n种硬币，第i种硬币的面值为coins[i-1]，目标金额为amt，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额，则返回-1。

1. 动态规划思路
   零钱兑换可以看作完全背包问题的一种特殊情况，两者具有以下联系与不同点:

• 两道题可以相互转换，"物品"对应"硬币"、"物品重量"对应"硬币面值"、"背包容量"对应"目标金额"。
• 优化目标相反，完全背包问题是要最大化物品价值，零钱兑换问题是要最小化硬币数量。
• 完全背包问题是求"不超过"背包容量下的解，零钱兑换是求"恰好"凑到目标金额的解。

第一步：思考每轮的决策，定义状态，从而得到dp表
状态[i,a]对应的子问题为：前i种硬币能够凑出金额a的最少硬币数量，记为dp[i,a]。二维dp表的尺寸为(n+1)x(amt+1)。
第二步：找出最优子结构，进而推导出状态转移方程
本题与完全背包问题的状态转移方程存在以下两点差异:

• 本题要求最小值，因此需将运算符max()更改为min()
• 优化主体是硬币数量而非商品价值，因此在选中硬币时执行+1即可。
  第三步：确定边界条件和状态转移顺序
  当目标金额为0时，凑出它的最少硬币数量为0，即首列所有dp[i,0]都等于0。当无硬币时，无法凑出任意>0的目标金额，即是无效解。为使状态转移方程中的min()函数能够识别并过滤无效解，我们考虑使用+∞来表示它们，即令首行所有dp[0,a]都等于+∞。

/* 零钱兑换：动态规划 */
int coinChangeDP(int[] coins, int amt) {
    int n = coins.length;
    int MAX = amt + 1;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][amt + 1];
    // 状态转移：首行首列
    for (int a = 1; a <= amt; a++) {
        dp[0][a] = MAX;
    }
    // 状态转移：其余行和列
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案的较小值
                dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
            }
        }
    }
    return dp[n][amt] != MAX ? dp[n][amt] : -1;
}

大多数编程语言并未提供+∞变量，只能使用整型int的最大值来代替。而这又会导致大数越界：状态转移方程中的+1操作可能发生溢出。为此，我们采用数字amt+1来表示无效解，因为凑出amt的硬币数量最多为amt。最后返回前，判断dp[n,amt]是否等于amt+1，若是则返回-1，代表无法凑出目标金额。

5.4 空间优化

零钱兑换的空间优化的处理方式和完全背包问题一致：

/* 零钱兑换：空间优化后的动态规划 */
int coinChangeDPComp(int[] coins, int amt) {
    int n = coins.length;
    int MAX = amt + 1;
    // 初始化 dp 表
    int[] dp = new int[amt + 1];
    Arrays.fill(dp, MAX);
    dp[0] = 0;
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[a] = dp[a];
            } else {
                // 不选和选硬币 i 这两种方案的较小值
                dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
            }
        }
    }
    return dp[amt] != MAX ? dp[amt] : -1;
}

5.5 零钱兑换问题II

给定n种硬币，第i种硬币的面值为coins[i-1]，目标金额为amt ，每种硬币可以重复选取，问凑出目标金额的硬币组合数量。示例如图所示。

1. 动态规划思路
   相比于上一题，本题目标是求组合数量，因此子问题变为：前i种硬币能够凑出金额a的组合数量。而dp表仍然是尺寸为(n+1)x(amt+1)的二维矩阵。当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。状态转移方程为： 当目标金额为0时，无须选择任何硬币即可凑出目标金额，因此应将首列所有dp[i,0]都初始化为1。当无硬币时，无法凑出任何>0的目标金额，因此首行所有dp[0,a]都等于0。

/* 零钱兑换 II：动态规划 */
int coinChangeIIDP(int[] coins, int amt) {
    int n = coins.length;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][amt + 1];
    // 初始化首列
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案之和
                dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
            }
        }
    }
    return dp[n][amt];
}

2. 空间优化
   空间优化处理方式相同，删除硬币维度即可：

/* 零钱兑换 II：空间优化后的动态规划 */
int coinChangeIIDPComp(int[] coins, int amt) {
    int n = coins.length;
    // 初始化 dp 表
    int[] dp = new int[amt + 1];
    dp[0] = 1;
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[a] = dp[a];
            } else {
                // 不选和选硬币 i 这两种方案之和
                dp[a] = dp[a] + dp[a - coins[i - 1]];
            }
        }
    }
    return dp[amt];
}

6. 编辑距离问题

编辑距离，也称Levenshtein距离，指两个字符串之间互相转换的最少修改次数，通常用于在信息检索和自然语言处理中度量两个序列的相似度。
问题一： 输入两个字符串s和t，返回将s转换为t所需的最少编辑步数。你可以在一个字符串中进行三种编辑操作：插入一个字符、删除一个字符、将字符替换为任意一个字符。
如图所示，将 kitten 转换为 sitting 需要编辑3步，包括2次替换操作与1次添加操作；将hello转换为algo需要3步，包括2次替换操作和1次删除操作。
编辑距离问题可以很自然地用决策树模型来解释。字符串对应树节点，一轮决策(一次编辑操作)对应树的一条边。如图所示，在不限制操作的情况下，每个节点都可以派生出许多条边，每条边对应一种操作，这意味着从hello转换到algo有许多种可能的路径。从决策树的角度看，本题的目标是求解节点hello和节点algo之间的最短路径。

6.1 动态规划思路

1. 第一步：思考每轮的决策，定义状态，从而得到dp表
   每一轮的决策是对字符串s进行一次编辑操作。我们希望在编辑操作的过程中，问题的规模逐渐缩小，这样才能构建子问题。设字符串s和t的长度分别为n和m，我们先考虑两字符串尾部的字符s[n-1]和t[m-1]。

• 若s[n-1]和t[m-1]相同，我们可以跳过它们，直接考虑s[n-1]和t[m-2]。
• 若s[n-1]和t[m-1]不同，我们需要对s进行一次编辑(插入、删除、替换)，使得两字符串尾部的字符相同，从而可以跳过它们，考虑规模更小的问题。

也就是说，我们在字符串s中进行的每一轮决策(编辑操作)，都会使得s和t中剩余的待匹配字符发生变化。因此，状态为当前在s和t中考虑的第i和第j个字符，记为[i,j]。状态[i,j]对应的子问题：将s的前i个字符更改为t的前j个字符所需的最少编辑步数。至此，得到一个尺寸为(i+1)x(j+1)的二维dp表。
2. 第二步：找出最优子结构，进而推导出状态转移方程
考虑子问题dp[i,j]，其对应的两个字符串的尾部字符为s[i-1]和t[j-1]，可根据不同编辑操作分为图所示的三种情况:

• 在s[i-1]之后添加t[j-1]，则剩余子问题dp[i,j-1]。
• 删除s[i-1]，则剩余子问题dp[i-1,j]。
• 将s[i-1]替换为t[j-1]，则剩余子问题dp[i-1,j-1]。
  根据以上分析，可得最优子结构：dp[i,j]的最少编辑步数等于dp[i,j-1]、dp[i-1,j]、dp[i-1,j-1]三者中的最少编辑步数，再加上本次的编辑步数1。对应的状态转移方程为：
  请注意，当s[i-1]和t[j-1]相同时，无须编辑当前字符，这种情况下的状态转移方程为：
  

3. 第三步：确定边界条件和状态转移顺序
   当两字符串都为空时，编辑步数为0，即dp[0,0]=0。当s为空但t不为空时，最少编辑步数等于t的长度，即首行dp[0,j]=j。当s不为空但t为空时，最少编辑步数等于s的长度，即首列dp[i,0]=i。观察状态转移方程，解dp[i,j]依赖左方、上方、左上方的解，因此通过两层循环正序遍历整个dp表即可。

/* 编辑距离：动态规划 */
int editDistanceDP(String s, String t) {
    int n = s.length(), m = t.length();
    int[][] dp = new int[n + 1][m + 1];
    // 状态转移：首行首列
    for (int i = 1; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= m; j++) {
        dp[0][j] = j;
    }
    // 状态转移：其余行和列
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                // 若两字符相等，则直接跳过此两字符
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
                dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[n][m];
}

如图所示，编辑距离问题的状态转移过程与背包问题非常类似，都可以看作填写一个二维网格的过程。

6.2 空间优化

由于dp[i,j]是由上方dp[i-1,j]、左方dp[i,j-1]、左上方dp[i-1,j-1]转移而来的，而正序遍历会丢失左上方dp[i-1,j-1]，倒序遍历无法提前构建dp[i,j-1]，因此两种遍历顺序都不可取。为此，我们可以使用一个变量leftup来暂存左上方的解dp[i-1,j-1]，从而只需考虑左方和上方的解。此时的情况与完全背包问题相同，可使用正序遍历。代码如下所示：

/* 编辑距离：空间优化后的动态规划 */
int editDistanceDPComp(String s, String t) {
    int n = s.length(), m = t.length();
    int[] dp = new int[m + 1];
    // 状态转移：首行
    for (int j = 1; j <= m; j++) {
        dp[j] = j;
    }
    // 状态转移：其余行
    for (int i = 1; i <= n; i++) {
        // 状态转移：首列
        int leftup = dp[0]; // 暂存 dp[i-1, j-1]
        dp[0] = i;
        // 状态转移：其余列
        for (int j = 1; j <= m; j++) {
            int temp = dp[j];
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                // 若两字符相等，则直接跳过此两字符
                dp[j] = leftup;
            } else {
                // 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
                dp[j] = Math.min(Math.min(dp[j - 1], dp[j]), leftup) + 1;
            }
            leftup = temp; // 更新为下一轮的 dp[i-1, j-1]
        }
    }
    return dp[m];
}