封面画师：Nengoro(ネんごろぅ)     封面ID：75292591

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

1. 动态规划

1.1 基本含义

动态规划，Dynamic Programming，简称 DP，是求解最优化问题的一种常用策略。

动态规划通常的使用套路（逐步优化）：

  • 暴力递归（自顶向下，会出现重叠子问题）
  • 记忆化搜索（自顶向下）
  • 递推（自底向上）

概念或许有点抽象，使用一道例题来介绍逐步优化成动态规划的步骤。

1.2 零钱兑换例题

来源 LeetCode 第 322 题：零钱兑换

假设现有若干枚 25 分、20 分、5 分、1 分的硬币，需要找给客户 41 分的零钱，如何使硬币个数 最少？

这道例题在《【算法】贪心》一文中出现过，但使用贪心策略进行求解时得到的并不是最优解，同时也告知可以使用动态规划来求取最优解，那怎么做呢？

思路分析

假设 dp(n)dp(n) 是凑到 nn 分需要的最少硬币个数。

  • 如果第 1 次选择了 25 分的硬币，那么 dp(n)=dp(n−25)+1dp(n) = dp(n - 25) + 1；

  • 如果第 1 次选择了 20 分的硬币，那么 dp(n)=dp(n−20)+1dp(n) = dp(n - 20) + 1；

  • 如果第 1 次选择了 5 分的硬币，那么 dp(n)=dp(n−5)+1dp(n) = dp(n - 5) + 1；

  • 如果第 1 次选择了 1 分的硬币，那么 dp(n)=dp(n−1)+1dp(n) = dp(n - 1) + 1；

所以 dp(n)=min{dp(n−25),dp(n−20),dp(n−5),dp(n−1)}+1dp(n)=min\{dp(n-25), dp(n-20), dp(n-5), dp(n-1)\}+1

解法：暴力递归

根据前面的思路分析不难得出 暴力递归 的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * LeetCode 322 零钱兑换
 *
 * @author mofan
 * @date 2022/11/17 22:15
 */
public class CoinChange {
    public static void main(String[] args) {
        /*
         * 假设有 4 枚硬币，面值分别是：25 20 5 1
         * 如何选取最小枚的硬币使总面值达到指定金额。
         */
        System.out.println(coins_1(41)); // 3
    }

    /**
     * 暴力递归（自顶向下的调用，会出现重叠子问题）
     *
     * @param n 目标金额
     * @return 最少硬币数量
     */
    static int coins_1(int n) {
        if (n < 1) return Integer.MAX_VALUE;
        if (n == 25 || n == 20 || n == 5 || n == 1) return 1;
        int min1 = Math.min(coins_1(n - 25), coins_1(n - 20));
        int min2 = Math.min(coins_1(n - 5), coins_1(n - 1));
        return Math.min(min1, min2) + 1;
    }
}

在 暴力递归 的实现中，自顶向下，从目标数值向下递减，在递减的过程中，通常会出现子问题重复计算的情况。当目标数值较大时，重复计算的情况会更多，显然 暴力递归 的时间复杂度较高，效率也很低。

要优化也很简单，把每个子问题的计算结果记录下来，下次遇到相同的子问题时，不再重复计算，而是直接使用记录的结果。

解法：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 记忆化搜索（自顶向下的调用）
 *
 * @param n 目标金额
 * @return 最少硬币数量
 */
static int coins_2(int n) {
    if (n < 1) return -1;
    int[] dp = new int[n + 1];
    int[] faces = {1, 5, 20, 25};
    // 按已知金额与目标金额进行初始化
    for (int face : faces) {
        if (n < face) break;
        dp[face] = 1;
    }
    return coins_2(n, dp);
}

static int coins_2(int n, int[] dp) {
    if (n < 1) return Integer.MAX_VALUE;
    // 未计算过的子问题
    if (dp[n] == 0) {
        int min1 = Math.min(coins_2(n - 25, dp), coins_2(n - 20, dp));
        int min2 = Math.min(coins_2(n - 5, dp), coins_2(n - 1, dp));
        dp[n] = Math.min(min1, min2) + 1;
    }
    // 计算过的子问题
    return dp[n];
}

尽管记忆化搜索的效率相比暴力递归的效率得到了提升，但依旧没有改变递归的本质。

如果能够使用非递归的方式来实现，效率还能进一步提升。

解法：递推

前两种解法中，都是从目标数值出发，自顶向下计算出最小子问题后，再从子问题向上递推，得到最终的解。既然如此，为什么不直接从最小子问题开始计算，然后向上递推得到最终的解呢？

假设有一整数数组 dp，其每个索引对应的数组即为凑得索引面值金额需要的最少硬币个数。此时目标数组为 n，在初始化 dp 数组时可以将其长度初始化为 n + 1（索引 0 不存放元素），那么 dp[n] 就是凑得目标金额所需的最少硬币个数。

在递推过程中，dp[i] 的值应该是 dp[i - 1]、dp[i - 5]、dp[i - 20] 和 dp[i - 25] 中的最小值加一。加一很好理解，已经选择了一枚硬币，肯定是要加一的。

1
2
3
4
5
6
7
8
9
10
11
12
13
static int coins_3(int n) {
    if (n < 1) return -1;
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int min = Integer.MAX_VALUE;
        if (i >= 1) min = Math.min(dp[i - 1], min);
        if (i >= 5) min = Math.min(dp[i - 5], min);
        if (i >= 20) min = Math.min(dp[i - 20], min);
        if (i >= 25) min = Math.min(dp[i - 25], min);
        dp[i] = min + 1;
    }
    return dp[n];
}

递推从 1 开始，循环项 i 必定大于等于 1，对 i >= 1 的判断并没有意义。当省略 i >= 1 的判断后，for 循环中的代码类似：

1
2
3
4
5
for (int i = 1; i <= n; i++) {
    int min = Integer.MAX_VALUE;
    min = Math.min(dp[i - 1], min);
    // ...
}

min 在相邻的两行中被依次赋值，不妨直接让 min 的初始值等于 dp[i - 1]：

1
2
3
4
5
6
7
8
9
10
11
12
static int coins_3(int n) {
    if (n < 1) return -1;
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int min = dp[i - 1];
        if (i >= 5) min = Math.min(dp[i - 5], min);
        if (i >= 20) min = Math.min(dp[i - 20], min);
        if (i >= 25) min = Math.min(dp[i - 25], min);
        dp[i] = min + 1;
    }
    return dp[n];
}

使用递推后，一次 for 就解决问题，时间、空间复杂度都是 O(n)O(n)，相比前两种递归求解的方式，效率又得到了提升。

1.3 零钱兑换的变体

最少硬币数已经求得了，那如果还要求输出选取的硬币信息，应该怎么办呢？

前文已经分析过：dp[i]=min{dp[i−25],dp[i−20],dp[i−5],dp[i−1]}+1dp[i]=min\{dp[i-25], dp[i-20], dp[i-5], dp[i-1]\}+1

以凑得 41 分为例：

  1. 第一次选取时 dp[i−20]dp[i-20]，即 dp[21]dp[21] 是 4 个值中最小的，那么最后加的那个 1 指的是选取了一枚 20 分的硬币；
  2. 第二次选取时 dp[i−20]dp[i-20]，即 dp[1]dp[1] 是 4 个值中最小的，最后加的那个 1 指的是又选取了一枚 20 分的硬币，此时共选取两枚 20 分的硬币；
  3. 第三次选取时 dp[i−1]dp[i-1]，即 dp[0]dp[0] 是 4 个值中最小的，最后加的那个 1 指的是选取了一枚 1 分的硬币，此时共选取两枚 20 分的硬币、一枚 1 分的硬币。

为了输出选取的硬币信息，可以再使用一个数组 faces， 该数组每个位置的值即为凑齐对应索引面值金额需要的最后一枚硬币信息。

还是以凑得 41 分为例：

  1. 当 i=41i=41 时，那么 dp[40]=2,dp[36]=4,dp[21]=2,dp[16]=4dp[40] = 2, dp[36] = 4, dp[21] = 2, dp[16] = 4，其中 dp[40]dp[40] 最小，因此 faces[41]=1faces[41] = 1；
  2. 当 i=40i=40 时，那么 dp[39]=7,dp[35]=3,dp[20]=1,dp[15]=3dp[39]=7,dp[35]=3,dp[20]=1,dp[15]=3，其中 dp[20]dp[20] 最小，因此 faces[40]=20faces[40]=20；
  3. 当 i=20i=20 时，那么 dp[19]=7,dp[15]=3,dp[0]=0dp[19]=7,dp[15]=3,dp[0]=0，其中 dp[0]dp[0] 最小，因此 faces[20]=20faces[20]=20；

如果需要输出选取的硬币信息，以目标金额 n=41n=41 为例：

  1. faces[41]=1faces[41]=1，首先输出 1，此时剩余金额 n=41−1=40n=41-1=40；
  2. faces[40]=20faces[40]=20，然后输出 20，此时剩余金额 n=40−20=20n=40-20=20；
  3. faces[20]=20faces[20]=20，最后再输出 20，此时剩余金额 n=20−20=0n=20-20=0，剩余金额为 0，结束输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
static int coins_4(int n) {
    if (n < 1) return -1;
    int[] dp = new int[n + 1];
    // faces[i] 表示凑够 i 分时第一次选择的硬币面值
    int[] faces = new int[dp.length];
    for (int i = 1; i <= n; i++) {
        int min = Integer.MAX_VALUE;
        if (i >= 1 && dp[i - 1] < min) {
            min = dp[i - 1];
            faces[i] = 1;
        }
        if (i >= 5 && dp[i - 5] < min) {
            min = dp[i - 5];
            faces[i] = 5;
        }
        if (i >= 20 && dp[i - 20] < min) {
            min = dp[i - 20];
            faces[i] = 20;
        }
        if (i >= 25 && dp[i - 25] < min) {
            min = dp[i - 25];
            faces[i] = 25;
        }
        dp[i] = min + 1;
    }
    print(faces, n);
    return dp[n];
}

static void print(int[] faces, int n) {
    System.out.print("[" + n + "] = ");
    while (n > 0) {
        System.out.print(faces[n] + " ");
        n -= faces[n];
    }
    System.out.println();
}

通用实现

前面的所有实现都指定了现有的硬币种类，如果要求使用用户传入硬币种类来使凑得的硬币枚数最少，应该怎么做呢？

在 coins_4() 方法的实现中可以看到有类似的模板代码，比如：

1
2
3
4
if (i >= 1 && dp[i - 1] < min) {
    min = dp[i - 1];
    faces[i] = 1;
}

对这些模板代码可以使用一个 for 循环来简化，通用实现也是这样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
    /*
     * 假设有 4 枚硬币，面值分别是：25 20 5 1
     * 如何选取最小枚的硬币使总面值达到指定金额。
     */
    System.out.println(coins_5(41, new int[]{1, 5, 20, 25}));
}

static int coins_5(int n, int[] faces) {
    if (n < 1 || faces == null || faces.length == 0) return -1;
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int min = Integer.MAX_VALUE;
        for (int face : faces) {
            if (i < face) continue;
            min = Math.min(dp[i - face], min);
        }
        dp[i] = min + 1;
    }
    return dp[n];
}

允许用户输入指定的硬币面额来进行凑数时，将有可能出现无法恰好凑齐目标金额的情况。比如传入 5、20、25 面额的硬币，需要凑得的目标金额是 41。

当无法凑齐时，返回 -1。假设指定的硬币面额是 5、20、25，那么无法恰好凑齐的情况有两种：

  • 需要凑齐 4 分，但指定的硬币的最小面额是 5；
  • 需要凑齐 41 分，尽管可以使用一些硬币，但余下的面额依旧无法恰好凑齐；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static int coins_5(int n, int[] faces) {
    if (n < 1 || faces == null || faces.length == 0) return -1;
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int min = Integer.MAX_VALUE;
        for (int face : faces) {
            // 减去 face 后的剩余面额也无法被恰好凑齐
            if (i < face || dp[i - face] < 0) continue;
            min = Math.min(dp[i - face], min);
        }
        // 如果没有进前面的循环，证明无法恰好凑得目标金额
        if (min == Integer.MAX_VALUE) {
            dp[i] = -1;
        } else {
            dp[i] = min + 1;
        }
    }
    return dp[n];
}

1.4 动态规划的常规步骤

经过“零钱兑换”问题的讲解，可以来总结下动态规划的常规步骤。

动态规划中的“动态”可以理解为是“会变化的状态”。动态规划的常规步骤是：

  1. 定义状态（状态是原问题、子问题的解），比如定义 dp(i)dp(i) 的含义；
  2. 设置初始状态（边界），比如设置 dp(0)dp(0) 的值；
  3. 确定状态转移方程，比如确定 dp(i)dp(i) 和 dp(i−1)dp(i-1) 的关系。

1.5 相关概念

维基百科对动态规划的解释是这样的：

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

动态规划就是：

  1. 将复杂的原问题拆解成若干个简单的子问题；
  2. 每个子问题仅仅解决 1 次，并保存它们的解；
  3. 最后推导出原问题的解

可以用动态规划来解决的问题，通常具备 2 个特点：

  • 最优子结构（最优化原理）：通过求解子问题的最优解，可以获得原问题的最优解。
  • 无后效性：
    • 某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响（未来与过去无关）
    • 在推导后面阶段的状态时，只关心前面阶段的具体状态值，不关心这个状态是怎么一步步推导出来的

无后效性

以一个例题来讲解无后效性：在只能向右、向下移动的情况下，从起点 (0, 0) 移动到终点 (4, 4) 一共有多少种方式？

无后效性例题图示

假设 dp(i,j)dp(i, j) 是从 (0,0)(0,0) 走到 (i,j)(i, j) 的走法，那么有：

  • dp(i,0)=dp(0,j)=1dp(i, 0) = dp(0, j) = 1
  • dp(i,j)=dp(i,j−1)+dp(i−1,j)dp(i, j) = dp(i, j - 1) + dp(i - 1, j)

所谓无后效性：

  • 推导 dp(i,j)dp(i, j) 时只需要用到 dp(i,j−1)dp(i, j - 1) 和 dp(i−1,j)dp(i - 1, j) 的值
  • 不需要关心 dp(i,j−1)dp(i, j - 1) 和 dp(i−1,j)dp(i - 1, j) 的值是怎么求出来的

那有后效性是怎么样的呢？

有后效性

现在不仅可以向右、向下移动，还可以向左、向上移动，但是同一个格子不能走 2 次，问：从起点 (0, 0) 移动到终点 (4, 4) 一共有多少种方式？

有后效性例题图示

针对本题来说，有后效性是指：dp(i,j)dp(i, j) 下一步要怎么移动，还要关心上一步是怎么来的，也就是还要关心 dp(i,j−1)dp(i, j - 1) 和 dp(i−1,j)dp(i - 1, j) 是怎么来的，因为同一个格子不能走 2 次。

2. 最大连续子序列和

2.1 题目描述

给定一个长度为 n 的整数序列，求它的最大连续子序列和。比如 -2、1、-3、4、-1、2、1、-5、4 的最大连续子序列和是 4 + (-1) + 2 + 1 = 6。

2.2 步骤分析

按照动态规划的常规步骤进行分析，即：定义状态、设置初始状态、确定状态转移方程。

定义状态

要求最大连续子序列和，可以先求出最大连续子序列，然后把子序列中的各个值相加即可得到最大连续子序列和。一个序列中的最大连续子序列可能是以原序列中任意一个元素结尾。

假设 numsnums 是给定的序列，dp(i)dp(i) 是以 nums[i]nums[i] 结尾的最大连续子序列和：

  • 以 nums[0]nums[0] 即 -2 结尾的最大连续子序列是 -2，所以 dp(0)=−2dp(0) = -2

  • 以 nums[1]nums[1] 即 1 结尾的最大连续子序列是 1，所以 dp(1)=1dp(1) = 1

  • 以 nums[2]nums[2] 即 -3 结尾的最大连续子序列是 1、-3，所以 dp(2)=dp(1)+(−3)=−2dp(2) = dp(1) + (-3) = -2

  • 以 nums[3]nums[3] 即 4 结尾的最大连续子序列是 4，所以 dp(3)=4dp(3) = 4

  • 以 nums[4]nums[4] 即 -1 结尾的最大连续子序列是 4、-1，所以 dp(4)=dp(3)+(−1)=3dp(4) = dp(3) + (-1) = 3

  • 以 nums[5]nums[5] 即 2 结尾的最大连续子序列是 4、-1、2，所以 dp(5)=dp(4)+2=5dp(5) = dp(4) + 2 = 5

  • 以 nums[6]nums[6] 即 1 结尾的最大连续子序列是 4、-1、2、1，所以 dp(6)=dp(5)+1=6dp(6) = dp(5) + 1 = 6

  • 以 nums[7]nums[7] 即 -5 结尾的最大连续子序列是 4、-1、2、1、-5，所以 dp(7)=dp(6)+(−5)=1dp(7) = dp(6) + (-5) = 1

  • 以 nums[8]nums[8] 即 4 结尾的最大连续子序列是 4、-1、2、1、-5、4，所以 dp(8)=dp(7)+4=5dp(8) = dp(7) + 4 = 5

确定状态转移方程

求 dp(i)dp(i) 的值时，需要参考 dp(i−1)dp(i-1) 的值：

  • 如果 dp(i−1)<0dp(i-1) \lt 0，那么 dp(i)=nums[i]dp(i)=nums[i]；
  • 如果 dp(i−1)>0dp(i-1) \gt 0，那么 dp(i)=dp(i−1)+nums[i]dp(i)=dp(i-1)+nums[i]。

设置初始状态

初始状态 dp(0)dp(0) 即为序列中的首元素 nums[0]nums[0]。

最终的解

numsnums 序列中最大连续子序列和是所有 dp(i)dp(i) 中的最大值 max{dp(i)}, i∈[0,nums.length)max \{ dp(i) \}, \ i \in [0, nums.length)。

2.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @author mofan
 * @date 2022/11/20 18:06
 */
public class MaxSubArray {
    public static void main(String[] args) {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray_1(nums));
    }

    static int maxSubArray_1(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] <= 0) {
                dp[i] = nums[i];
            } else {
                dp[i] = dp[i - 1] + nums[i];
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

空间复杂度和时间复杂度都是 O(n)O(n)。

代码的主要逻辑是：

1
2
3
4
5
if (dp[i - 1] <= 0) {
    dp[i] = nums[i];
} else {
    dp[i] = dp[i - 1] + nums[i];
}

无论什么情况，对 dp[i] 的赋值都有 nums[i]，只不过当 dp[i - 1] 大于 0 时，还要加上 dp[i - 1] 的值，因此不妨让 dp[i - 1] 与 0 进行比较，当 dp[i - 1] 更加时，就加上 dp[i - 1]，当 0 更大时，就加上 0，相当于不加任何数值。最终简化为：

1
dp[i] = nums[i] + Math.max(dp[i - 1], 0);

上述实现代码的时间复杂度和空间复杂度尽管已经非常可观，但仍有优化的空间。

当计算 dp[i] 的值时，只需要参考 dp[i - 1] 的值，并不需要 dp[i - 2] 或者更早计算出的值，所以 dp 并不非得是数组，一个整数就能满足：

1
2
3
4
5
6
7
8
9
10
static int maxSubArray_2(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int dp = nums[0];
    int max = dp;
    for (int i = 1; i < nums.length; i++) {
        dp = nums[i] + Math.max(dp, 0);
        max = Math.max(max, dp);
    }
    return max;
}

优化后，时间复杂度仍是 O(n)O(n)，但空间复杂度提升为 O(1)O(1)。

3. 最长上升子序列

3.1 问题描述

最长递增子序列，Longest Increasing Subsequence，简称 LIS。

来源 LeetCode 第 300 题：最长递增子序列

给定一个无序的整数序列，求出它最长上升子序列的长度（要求严格上升，但无需连续）。比如 [10, 2, 2, 5, 1, 7, 101, 18] 的最长上升子序列是 [2, 5, 7, 101] 和 [2, 5, 7, 18]，长度是 4。

所谓上升就是要求子序列中的元素值随索引的增加而增大。

3.2 步骤分析

按照动态规划的常规步骤进行分析，即：定义状态、设置初始状态、确定状态转移方程。

定义状态

一个序列中的最长上升子序列可能是以原序列中任意一个元素结尾。

假设 numsnums 是给定的序列，dp(i)dp(i) 是以 nums[i]nums[i] 结尾的最长上升子序列的长度：

  • 以 nums[0]nums[0] 即 10 结尾的最长上升子序列是 10，所以 dp(0)=1dp(0) = 1

  • 以 nums[1]nums[1] 即 2 结尾的最长上升子序列是 2，所以 dp(1)=1dp(1) = 1

  • 以 nums[2]nums[2] 即 2 结尾的最长上升子序列是 2，所以 dp(2)=1dp(2) = 1

  • 以 nums[3]nums[3] 即 5 结尾的最长上升子序列是 2、5，所以 dp(3)=dp(1)+1=dp(2)+1=2dp(3) = dp(1) + 1 = dp(2) + 1 = 2

  • 以 nums[4]nums[4] 即 1 结尾的最长上升子序列是 1，所以 dp(4)=1dp(4) = 1

  • 以 nums[5]nums[5] 即 7 结尾的最长上升子序列是 2、5、7，所以 dp(5)=dp(3)+1=3dp(5) = dp(3) + 1 = 3

  • 以 nums[6]nums[6] 即 101 结尾的最长上升子序列是 2、5、7、101，所以 dp(6)=dp(5)+1=4dp(6) = dp(5) + 1 = 4

  • 以 nums[7]nums[7] 即 18 结尾的最长上升子序列是 2、5、7、18，所以 dp(7)=dp(5)+1=4dp(7) = dp(5) + 1 = 4

确定状态转移方程

求 dp(i)dp(i) 的值时，并不是只考虑 dp(i−1)dp(i-1) 的值就行了。

本题要求的是最长上升子序列的长度，重点就在“上升”二字。

求取 dp(i)dp(i) 时，需要比较 nums 中索引 i 以前是否存在比 nums[i] 小的数。如果存在，求出以这些数结尾的最长上升子序列的长度，并挑选出一个最大值 maxmax，最终 dp(i)=max+1dp(i) = max + 1；如果不存在，那么 dp(i)=1dp(i) = 1。

假设 j∈[0,i)j \in [0,i)，遍历 dp(0)dp(0) 到 dp(j)dp(j) 的值，当：

  • nums[i]>nums[j]nums[i] \gt nums[j] 时，dp(i)=max{dp(i),dp(j)+1}dp(i)=max \{ dp(i), dp(j) + 1 \}；
  • nums[i]≤nums[j]nums[i] \le nums[j] 时，dp(i)=1dp(i)=1。

设置初始状态

  • dp(0)=1dp(0)=1
  • 所有的 dp(i)dp(i) 默认都初始化为 11

最终的解

numsnums 序列中最长上升子序列的长度是所有 dp(i)dp(i) 中的最大值 max{dp(i)}, i∈[0,nums.length)max \{ dp(i) \}, \ i \in [0, nums.length)。

3.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @author mofan
 * @date 2022/11/20 19:07
 */
public class LIS {
    public static void main(String[] args) {
        int[] nums = new int[]{10, 2, 2, 5, 1, 7, 101, 18};
        System.out.println(lengthOfLIS_1(nums));
    }

    static int lengthOfLIS_1(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int max = dp[0] = 1;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] <= nums[j]) continue;
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

使用了 dp 数组，因此空间复杂度是 O(n)O(n)。

存在两层 for 循环，因此时间复杂度是 O(n2)O(n^2)。

3.4 二分搜索

把原序列中每个元素看成是一张扑克牌，从左往右按顺序（按序列的索引）处理每一张扑克牌。

最长上升子序列二分搜索初始状态

从中抽取出一张扑克牌，将这张扑克牌 依次 与牌堆中的堆顶扑克进行比较：

  • 当不存在牌堆时，新建一个牌堆，抽取的扑克牌作为新牌堆的堆顶扑克；
  • 当抽取的扑克牌小于某个牌堆的堆顶扑克时，抽取的扑克牌作为该牌堆新的堆顶扑克，之后抽取新的扑克牌再依次与牌堆的堆顶扑克进行比较；
  • 当抽取的扑克牌大于牌堆中所有的堆顶扑克时，在最右边新建一个牌堆，抽取的扑克牌作为新牌堆的堆顶扑克；
  • 当处理完所有扑克牌时，牌堆的数量就是最长上升子序列的长度。

最长上升子序列二分搜索形成牌堆

为什么这样就能够求出最长上升子序列的长度呢？

其实很简单。当抽取的扑克能够作为现有牌堆中某个牌堆的新堆顶扑克时，就证明这张扑克一定是小于某个牌堆的堆顶扑克，那就一定不是 上升 的；只有当抽取的扑克形成了新的牌堆，证明这张扑克大于所有牌堆的堆顶扑克，使得堆顶扑克组成的序列长度增加。

编码思路

假设原序列是 nums，即最初的牌数组是 nums。

新建一个数组 top，该数组依次存放牌堆的堆顶扑克信息，最坏情况下，top 数组的长度等于牌数组 nums 的长度，因此初始化 top 数组的长度为牌数组 nums 的长度。

记牌堆数量为 len，初始值为 0，表示没有任何牌堆。

接下来在牌数组 nums 中遍历每一张牌 nums，由于牌堆堆顶扑克的大小是依次上升的，因此可以利用 二分搜索 找出 num 最终要放入的牌堆位置 index，之后 num 作为 index 位置牌堆的堆顶，即 top[index] = num。如果 index 与 len 相等，相当于新建一个牌堆，牌堆数量 len 自增一。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] top = new int[nums.length];
    int len = 0;
    for (int num : nums) {
        int begin = 0, end = len;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (num <= top[mid]) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        top[begin] = num;
        if (begin == len) len++;
    }
    return len;
}

经过优化后，空间复杂度认为 O(n)O(n)，但由于使用了二分搜索，此时的时间复杂度为 O(nlogn)O(nlogn)。

4. 最长公共子序列

4.1 问题描述

最长公共子序列，Longest Common Subsequence，简称 LCS。

来源 LeetCode 第 1143 题：最长公共子序列

给定两个无序的序列，求两个序列的最长公共子序列长度。比如 [1, 3, 5, 9, 10] 和 [1, 4, 9, 10] 的最长公共子序列是 [1, 9, 10]，长度是 3。

序列 ABCBDAB 和 BDCABA 的最长公共子序列长度是 4，但对应的公共子序列可能是：

  • ABCBDAB 和 BDCABA，即：BDAB
  • ABCBDAB 和 BDCABA，即：BDAB
  • ABCBDAB 和 BDCABA，即：BCAB
  • ABCBDAB 和 BDCABA，即：BCBA

4.2 思路分析

假设 2 个序列分别是 nums1nums1 和 nums2nums2，并且定义 i∈[1,nums1.length]i \in [1, nums1.length] 和 j∈[1,nums2.length]j \in [1, nums2.length] 两个变量。

假设 dp(i,j)dp(i, j) 是 nums1nums1 前 ii 个元素与 nums2nums2 前 jj 个元素的最长公共子序列长度。那么有：

  • dp(i,0)=dp(0,j)=0dp(i, 0) = dp(0, j) = 0
  • 当 nums1[i−1]=nums2[j−1]nums1[i - 1] = nums2[j - 1] 时，dp(i,j)=dp(i−1,j−1)+1dp(i, j) = dp(i - 1, j - 1) + 1
  • 当 nums1[i−1]≠nums2[j−1]nums1[i - 1] \ne nums2[j - 1] 时，dp(i,j)=max{dp(i−1,j),dp(i,j−1)}dp(i, j) = max\{ dp(i - 1, j), dp(i, j - 1) \}

前两条不必多说，第三条是因为第 ii 个元素，即 nums1[i−1]nums1[i - 1] 可能与 nums2nums2 前 jj 个元素中的某个元素相等，并使得最长公共子序列的长度加一（但并不是说只要相等，就一定会使得最长公共子序列长度加一，因为可能恰好这个元素已经在原本的最长公共子序列中存在），反之对 nums2nums2 也一样，因此需要求出两者的最大值。

最长公共子序列中第i-1与第j-1个元素不相等时的三种情况

4.3 递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @author mofan
 * @date 2022/11/26 16:03
 */
public class LCS {
    public static void main(String[] args) {
        int[] nums1 = {1, 3, 5, 9, 10};
        int[] nums2 = {1, 4, 9, 10};
        System.out.println(lcs(nums1, nums2)); // 3
    }

    static int lcs(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        return lcs(nums1, nums1.length, nums2, nums2.length);
    }

    /**
     * nums1 中前 i 个元素和 nums2 中前 j 个元素的最长公共子序列的长度
     */
    static int lcs(int[] nums1, int i, int[] nums2, int j) {
        if (i == 0 || j == 0) return 0;
        if (nums1[i - 1] == nums2[j - 1]) {
            return lcs(nums1, i - 1, nums2, j - 1) + 1;
        }
        return Math.max(
                lcs(nums1, i - 1, nums2, j),
                lcs(nums1, i, nums2, j - 1)
        );
    }
}

空间复杂度是 O(k)O(k)，其中 k=min{n,m}k = min\{ n, m \}，而 nn 与 mm 是两个序列的长度。

递归调用的空间复杂度取决于递归调用的次数，上述代码中当 i 或 j 其中一个等于 0 时就结束调用，而它们的最大值又分别是两个序列的长度，因此递归调用的次数就是两个序列中的最小长度，即 k=min{n,m}k = min\{ n, m \}。

时间复杂度是 O(2n)O(2^n)，当 n=mn = m 时。

最长公共子序列递归实现调用分析

并且在上图的调用分析中还出现了重复的递归调用。

4.3 非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static int lcs(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0) return 0;
    if (nums2 == null || nums2.length == 0) return 0;
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];
    for (int i = 1; i <= nums1.length; i++) {
        for (int j = 1; j <= nums2.length; j++) {
            if (nums1[i - 1] == nums2[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[nums1.length][nums2.length];
}

假设两个序列的长度分别为 m 和 n：

  • 根据引入的二维数组和给出的初始长度不难得出空间复杂度为 O(mn)O(mn)
  • 代码实现中使用了嵌套的 for 循环，因此时间复杂度也是 O(mn)O(mn)

但这并不是最优的解，还能进一步减小复杂度。

使用滚动数组进行优化

假设有两个序列 nums1 和 nums2，其中：

1
2
int[] nums1 = {"B", "D", "C", "A", "B", "A"};
int[] nums2 = {"A", "B", "C", "B", "D", "A", "B"};

对这两个序列进行计算的 dp 数组结果如下所示：

最长公共子序列中dp数组的计算结果

比如 dp[3][3] 表示 nums1 中前 3 个元素组成的子序列与 nums2 中前 3 个元素组成的子序列的最长公共子序列的长度。

由于 nums1[3] = nums2[3] = "C"，因此：

1
dp[3][3] = dp[2][2] + 1 = 1 + 1 = 2

在给出的计算图中也确实也发现 dp[3][3] = 2。

非递归实现中的主要逻辑代码是：

1
2
3
4
5
6
7
8
9
for (int i = 1; i <= nums1.length; i++) {
    for (int j = 1; j <= nums2.length; j++) {
        if (nums1[i - 1] == nums2[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]);
        }
    }
}

结合这段代码不难发现给出的计算图中的结果是一行一行计算出来的，不仅如此，每次计算第 i 行的数据时，只会用到前一行，即第 i - 1 行的数据，而不会用到第 i - 2 行或更早以前计算出来的数据。

因此，可以使用 滚动数组 的方式对非递归实现进行优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int lcs(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0) return 0;
    if (nums2 == null || nums2.length == 0) return 0;
    int[][] dp = new int[2][nums2.length + 1];
    for (int i = 1; i <= nums1.length; i++) {
        int row = i & 1; // 相当于 i % 2
        int preRow = (i - 1) & 1;
        for (int j = 1; j <= nums2.length; j++) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[row][j] = dp[preRow][j - 1] + 1;
            } else {
                dp[row][j] = Math.max(dp[preRow][j], dp[row][j - 1]);
            }
        }
    }
    return dp[nums1.length & 1][nums2.length];
}

进行优化后，空间复杂度变为 O(2n)O(2n)，其中 nn 为第二个序列的长度。

时间复杂度没有改变，这也很正常，因为这些遍历是不可缺少的。

但这仍不是最优解，还可以再优化。

使用一维数组进行优化

根据求解计算图中的结果可知：每次计算最多只需要三个值。

假设需要求 dp[i][j] 的值，最多只需要 dp[i - 1][j]、dp[i - 1][j - 1] 和 dp[i][j - 1] 三个值。

也就是说只需要三个变量就行了？

并不是这样的。求 dp[i][j] 需要的三个值已经知晓，那后续求解 dp[i + 1][j - 2] 需要哪些值呢？

很明显需要 dp[i][j - 2]、dp[i][j - 3] 和 dp[i + 1][j - 3] 的值，但如果只使用三个变量，将不会保存这些值的，也就无法求解。

为了能够顺利求解，必须保存前一行的解。 因此可以把二维数组优化成一维数组，进一步减少空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static int lcs(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0) return 0;
    if (nums2 == null || nums2.length == 0) return 0;
    int[] dp = new int[nums2.length + 1];
    for (int i = 1; i <= nums1.length; i++) {
        int cur = dp[0];
        for (int j = 1; j <= nums2.length; j++) {
            int leftTop = cur;
            cur = dp[j];
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[j] = leftTop + 1;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
        }
    }
    return dp[nums2.length];
}

经过这次优化后，空间复杂度变为 O(n)O(n)，其中 nn 为第二个序列的长度。

假设 mm 是第一个序列的长度，并且 m<nm \lt n，显然此时 O(n)O(n) 的空间复杂度并不是最优的。只需调转下序列的位置，让原本的第一个序列成为第二个序列，原本第二个序列成为第一个序列，此时的空间复杂度还能更低。

而调转序列位置的本质就是找到给定的两个序列的长度最小值作为 dp 数组的长度。

根据计算图可知，dp 的长度与顶部序列长度有关，即 ABCBDAB，由于这个序列横向放置，将其命名为 rowsNums，相应地另外一个序列名为 colsNums，而 dp 的长度应该是 rowsNums 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static int lcs(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0) return 0;
    if (nums2 == null || nums2.length == 0) return 0;
    int[] colsNums = nums1, rowsNums = nums2;
    if (nums1.length < nums2.length) {
        rowsNums = nums1;
        colsNums = nums2;
    }

    int[] dp = new int[rowsNums.length + 1];
    for (int i = 1; i <= colsNums.length; i++) {
        int cur = 0;
        for (int j = 1; j <= rowsNums.length; j++) {
            int leftTop = cur;
            cur = dp[j];
            if (colsNums[i - 1] == rowsNums[j - 1]) {
                dp[j] = leftTop + 1;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
        }
    }
    return dp[rowsNums.length];
}

5. 最长公共子串

5.1 问题描述

最长公共子串，Longest Common Substring，子串是连续的子序列。

求两个字符串的最长公共子串。比如：

ABCBA 和 BABCA 的最长公共子串是 ABC，长度是 3。

5.2 思路分析

假设 2 个字符串分别是 str1str1 和 str2str2，并且定义 i∈[1,str1.length]i \in [1, str1.length] 和 j∈[1,str2.length]j \in [1, str2.length] 两个变量。

假设 dp(i,j)dp(i, j) 是 同时 以 str[i−1]str[i - 1] 和 str2[j−1]str2[j - 1] 结尾 的最长公共子串长度。那么有：

  • dp(i,0)dp(i, 0) 和 dp(o,j)dp(o, j) 的初始值都是 00
  • 当 str[i−1]=str2[j−1]str[i - 1] = str2[j - 1] 时，dp(i,j)=dp(i−1,j−1)+1dp(i, j) = dp(i - 1, j - 1) + 1
  • 当 str[i−1]≠str2[j−1]str[i - 1] \ne str2[j - 1] 时，dp(i,j)=0dp(i, j) = 0

因此最长公共子串的长度是所有 dp(i,j)dp(i, j) 中的最大值 max{dp(i,j)}max\{ dp(i, j) \}。

5.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static int lcs(String str1, String str2) {
    if (str1 == null || str2 == null) return 0;
    char[] chars1 = str1.toCharArray();
    if (chars1.length == 0) return 0;
    char[] chars2 = str2.toCharArray();
    if (chars2.length == 0) return 0;

    int[][] dp = new int[chars1.length + 1][chars2.length + 1];
    int max = 0;
    for (int i = 1; i <= chars1.length; i++) {
        for (int j = 1; j <= chars2.length; j++) {
            if (chars1[i - 1] != chars2[j - 1]) continue;
            dp[i][j] = dp[i - 1][j - 1] + 1;
            max = Math.max(dp[i][j], max);
        }
    }
    return max;
}

显然，空间复杂度和时间复杂度都是 O(mn)O(mn)，其中 mm 和 nn 是两个字符串的长度。

dp 数组的计算结果如下图所示：

最长公共子串中dp数组的计算结果

结合前面的思路分析可知，每次计算一个全新的 dp(i,j)dp(i, j) 时最多只需要一个值，即 dp(i−1,j−1)dp(i - 1, j - 1)。

和求解最长公共子序列时一样，并不是说只引入一个变量来保存 dp(i−1,j−1)dp(i - 1, j - 1) 就行了，至少需要一个一维数组来依次保存这些值，优化过程与求解最长公共子序列基本一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static int lcs(String str1, String str2) {
    if (str1 == null || str2 == null) return 0;
    char[] chars1 = str1.toCharArray();
    if (chars1.length == 0) return 0;
    char[] chars2 = str2.toCharArray();
    if (chars2.length == 0) return 0;

    char[] closChars = chars1, rowsChars = chars2;
    if (chars1.length < chars2.length) {
        closChars = chars2;
        rowsChars = chars1;
    }
    int[] dp = new int[rowsChars.length + 1];
    int max = 0;
    for (int i = 1; i <= closChars.length; i++) {
        int cur = 0;
        for (int j = 1; j <= rowsChars.length; j++) {
            int leftTop = cur;
            cur = dp[j];
            if (closChars[i  - 1] != rowsChars[j - 1]) {
                dp[j] = 0;
            } else {
                dp[j] = leftTop + 1;
                max = Math.max(dp[j], max);
            }
        }
    }
    return max;
}

经过优化后，空间复杂度降低为 O(k),k=min{m,n}O(k), k = min\{ m, n \}，时间复杂度不变，依旧为 O(mn)O(mn)。

5.4 学习 0-1 背包后的优化

计算一个全新的 dp(i,j)dp(i, j) 时最多只需要一个值，即 dp(i−1,j−1)dp(i - 1, j - 1)。

在 0-1 背包问题中，采取了从大到小进行递减，而无需引入其他变量，因此可以得到如下优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static int lcs(String str1, String str2) {
    if (str1 == null || str2 == null) return 0;
    char[] chars1 = str1.toCharArray();
    if (chars1.length == 0) return 0;
    char[] chars2 = str2.toCharArray();
    if (chars2.length == 0) return 0;

    char[] closChars = chars1, rowsChars = chars2;
    if (chars1.length < chars2.length) {
        closChars = chars2;
        rowsChars = chars1;
    }
    int[] dp = new int[rowsChars.length + 1];
    int max = 0;

    for (int i = 1; i <= closChars.length; i++) {
        // 从大到下递减
        for (int j = rowsChars.length; j >= 1; j--) {
            if (closChars[i - 1] != rowsChars[j - 1]) {
                dp[j] = 0;
            } else {
                dp[j] = dp[j - 1] + 1;
                max = Math.max(dp[j], max);
            }
        }
    }
    return max;
}

6. 0-1 背包

6.1 问题描述

有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是 wiw_i，并且价值是 viv_i。

在保证总重量不超过 W 的前提下，选择某些物品装入背包，背包的最大总价值是多少？

注意： 每个物品只有 1 件，也就是每个物品只能选择 0 件或者 1 件，即要么选择它、要么不选择它。

6.2 思路分析

假设 values 是价值数组，weights 是重量数组。

那么编号为 k 的物品的价值是 values[k]，重量是 weights[k]，并且 k∈[0,n)k \in [0, n)，n 为物品总数。

假设 dp(i,j)dp(i, j) 是 有前 i 件物品可选、最大承重为 j 时 的最大总价值，其中 i∈[1,n],j∈[1,W]i \in [1, n],\quad j \in [1, W]。

显然 dp(i,0)=dp(0,j)=0dp(i, 0) = dp(0, j) = 0，那么 dp(i,j)dp(i, j) 的值应该怎么算呢？

针对前 i 件物品来说，第 i 件物品可以选择，也可以不选择，那么：

  • 当选择第 i 件物品时，dp(i,j)=dp(i−1,j−weights[i−1])+values[i−1]dp(i, j) = dp(i - 1, j - weights[i - 1]) + values[i - 1]
  • 当不选择第 i 件物品时，dp(i,j)=dp(i−1,j)dp(i, j) = dp(i - 1, j)

因此最终的 dp(i,j)dp(i, j) 应该是这两种情况下的最大值。

除此之外，第 i 件能否选择是建立在 j≥weights[i−1]j \ge weights[i - 1] 情况下。当 j<weights[i−1]j \lt weights[i - 1] 时，即第 i 件物品的总量比背包的最大承重还要大时，第 i 件物品是一定不能选择的，此时 dp(i,j)=dp(i−1,j)dp(i, j) = dp(i - 1, j)。

综上所述：

  • 当 j<weights[i−1]j \lt weights[i - 1] 时，dp(i,j)=dp(i−1,j)dp(i, j) = dp(i - 1, j)
  • 当 j≥weights[i−1]j \ge weights[i - 1] 时，dp(i,j)=max{dp(i−1,j),dp(i−1,j−weights[i−1])+values[i−1]}dp(i, j) = max\{ dp(i - 1, j), \quad dp(i - 1, j - weights[i - 1]) + values[i -1] \}

6.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * @author mofan
 * @date 2022/11/27 18:01
 */
public class Knapsack {
    public static void main(String[] args) {
        int[] values = {6, 3, 5, 4, 6};
        int[] weights = {2, 2, 6, 5, 4};
        int capacity = 10;
        System.out.println(maxValue(values, weights, capacity)); // 15
    }

    static int maxValue(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || capacity <= 0) return 0;

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

dp 数组的计算结果如下图所示：

0-1背包问题中dp数组的计算结果

以 v = 6，w = 4，capacity = 8 为例，即需要计算 dp(5,8)dp(5, 8) 的值。w = 4，小于最大承重 8，因此对于这件物品有选择与不选择两种方案：

  • 当选择这件物品时，dp(5,8)=dp(5−1,8−4)+6=dp(4,4)+6=9+6=15dp(5, 8) = dp(5 - 1, 8 - 4) + 6 = dp(4, 4) + 6 = 9 + 6 = 15
  • 当不选择这件物品时，dp(5,8)=dp(5−1,8)=dp(4,8)=11dp(5, 8) = dp(5 - 1, 8) = dp(4, 8) = 11

显然在选择这件物品时得到的总价值最大，因此 dp(5,8)=15dp(5, 8) = 15。

再尝试多种情况，可以发现：当计算 dp(i,j)dp(i, j) 的值时，一定 需要使用到前一行的计算结果。

因此上述实现的空间复杂度还能够优化， 使用一维数组来降低空间复杂度。

使用到的计算结果的位置在前一行中是不固定的，与当前可选择物品的总量有关。假设需要使用到的计算结果为 dp(m,n)dp(m, n)，那么 m=i−1,n≤jm = i - 1, \quad n \le j。

由于这个结果在前一行的位置不固定，并且所在列一定小于等于当前计算值所在的列，在计算一维数组中的值时不能再从左往右计算，而是要从右往左，也就是在计算 dp(i,j)dp(i, j) 的值时，jj 应该从大到小计算（最大是背包最大承重 W），否则会导致数据错乱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int maxValue(int[] values, int[] weights, int capacity) {
    if (values == null || values.length == 0) return 0;
    if (weights == null || weights.length == 0) return 0;
    if (values.length != weights.length || capacity <= 0) return 0;

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

优化后的代码中存在 dp[j] = dp[j] 的赋值语句，这是没有意义的，不如直接 continue，即：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int maxValue(int[] values, int[] weights, int capacity) {
    if (values == null || values.length == 0) return 0;
    if (weights == null || weights.length == 0) return 0;
    if (values.length != weights.length || capacity <= 0) return 0;

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

继续观察 dp 数组的计算结果：

0-1背包问题中dp数组的计算结果

以 v = 5，w = 6，capacity = 6 为例，先计算出 dp(3,6)=9dp(3, 6) = 9 的值。j 的值进一步缩小，接下来需要计算 dp(3,5)dp(3, 5) 的值，而此时 w = 6，大于背包最大承重，此时 一定 不能选择这件商品，那么 dp(3,5)=dp(2,5)=9dp(3, 5) = dp(2, 5) = 9。之后， j 的值还会继续缩小，w = 6 将一直大于背包最大承重，使得 dp(3,m)dp(3, m) 的值将一直等于 dp(2,m)dp(2, m) 的值。

也就是说，当 j < w 时，就没有让 j 继续缩小的意义了，无论它怎么缩小，计算出的值都是前一行的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
static int maxValue(int[] values, int[] weights, int capacity) {
    if (values == null || values.length == 0) return 0;
    if (weights == null || weights.length == 0) return 0;
    if (values.length != weights.length || capacity <= 0) return 0;

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

6.4 恰好装满

在原问题的基础上进行修改：要求在保证总重量 恰好 等于 W 的前提下，选择某些物品装入背包，求出背包的最大总价值。

基本思路与原问题类似，只不过 需要调整下初始状态。 以原问题的 dp(i,j)dp(i, j) 为例：

  • dp(i,0)=0dp(i, 0) = 0，最大承重是 0 时，不能放入任何物品，因此最大总价值也是 0，这毋庸置疑
  • 当 j>1j \gt 1 时，dp(0,j)=−1dp(0, j) = -1，当没有物品但又要 恰好 凑到 jj 的重量时，这显然是不可能的，而这里的 -1 就代表无法恰好装满

以求解 dp(m,n)dp(m, n) 为例，它的值有两种可能：

  1. 第 m 件物品被选择时：dp(m,n)=dp(m−1,n−weights[m−1])+values[m−1]dp(m, n) = dp(m - 1, n - weights[m - 1]) + values[m - 1]
  2. 第 m 件物品未被选择时：dp(m,n)=dp(m−1,n)dp(m, n) = dp(m - 1, n)

当第 m 件物品被选择时，需要计算 dp(m−1,n−weights[m−1])dp(m - 1, n - weights[m - 1]) 的值。如果这个值小于 0（或者说等于 -1），表示当选择了第 m 件物品后，无法使用剩下的物品恰好凑到剩下的背包总容量，也就是说这种情况下 dp(m,n)=−1dp(m, n) = -1，无法在选择了第 m 件物品时，恰好凑到目标重量；如果这个值大于 0，表示能够使用剩下的物品恰好凑到剩下的背包总容量，换而言之能够在选择了第 m 件物品的情况下，恰好凑到目标重量。

当第 m 件物品未被选择时，需要计算 dp(m−1,n)dp(m - 1, n) 的值，直接沿用即可。

最后在这两种情况下选取最大值作为 dp(m,n)dp(m, n) 的值。

在这种情况下，dp 数组的计算结果如下图所示：

0-1背包问题中恰好装满时dp数组的计算结果

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @return 如果返回 -1，表示没办法恰好凑到 capacity 的容量
 */
static int maxValueExactly(int[] values, int[] weights, int capacity) {
    if (values == null || values.length == 0) return -1;
    if (weights == null || weights.length == 0) return -1;
    if (values.length != weights.length || capacity <= 0) return 0;

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