二、动态规划

2.1、概念说明

  • 动态规划，即 Dynamic Programming ，简称 DP ，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
  • 动态规划中每一个状态一定是由上一个状态推导出来的
  • 遍历顺序的确定

对于遍历顺序，我们只需要确定两点

  1. 遍历的过程中，所需的状态必须是已经计算出来的
  2. 遍历的终点必须是存储结果的那个位置。

2.2、使用最小花费爬楼梯

1、题目描述

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

  • 示例一
1
2
3
输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15
  • 示例二
1
2
3
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

2、解题思路

我们首先需要确定 dp 数组中元素的含义，在这道题中 dp[i] 表示到第 i 个台阶需要花费的最少的体力数，且 dp[i] 由 dp[i - 1] 和 dp[i - 2] 决定，我们由示例二可以推导出递推公式，即

1
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]

为什么递推公式中需要加的值为 dp[i] ，这是因为由题意可知，当我们爬上第 i 个楼梯时，就要花费对应的体力值，所以，到达第 i 个体力值需要支付的体力为 cost[i]

同时我们需要注意，最后到达终点的那一步是不需要花费体力的。

3、解题代码

  • 未进行优化前
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minCostClimbingStairs(int[] cost) {
    if (cost == null || cost.length == 0) return 0;
    // 创建 dp 数组
    int[] dp = new int[cost.length];
    // 对 dp 数组中的元素进行初始化，到达第一个台阶所花费的体力为 cost[0] ，到达第二个台阶所花费的最小体力为 cost[1]
    // dp[1] < dp[0] + dp[1]
    dp[0] = cost[0];
    dp[1] = cost[1];
    // 进行状态转移， dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]
    for (int i = 2;i < cost.length;i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    // 注意，由于最后一步，即从倒数第二部到重点的过程中是不用花费体力的，所以我们要进行选择
    // 看是从 cost.length - 2 步一下走两步到达终点花费的体力少，还是从 cost.length - 1 步一步到位花费的体力少
    return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
}

在这道题中，由于 dp[i] 只由前面两个状态的值与所给的 cost[i] 决定，所以我们可以不用使用一整个数组，而是使用两个变量进行滚动更新。

  • 使用两个变量进行滚动优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minCostClimbingStairs(int[] cost) {
    if (cost == null || cost.length == 0) return 0;
    // 使用两个变量进行滚动，其中 one 表示 i - 2 ，second 表示 i - 1
    int one = cost[0];
    int two = cost[1];
    // 在这个循环中，进行状态转移
    for (int i = 2;i < cost.length;i++) {
        int result = Math.min(one, two) + cost[i];
        // 将原本为 i - 1 位置的值赋给 one
        one = two;
        // 将当前位置的值赋值给 two
        two = result;
    }
    // 同理，这里最后也不能返回 result ，而是需要在 one 和 two 之间做出选择
    return Math.min(one, two);
}

2.3、不同路径

1、题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

  1. 示例一

image.png

1
2
输入：m = 3, n = 7
输出：28
  1. 示例二
1
2
3
4
5
6
7
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

2、解题思路

  1. 确定 dp 数组

在这个问题中，我们需要一个二维的 dp 数组，其中 dp[i][j] 表示到达网格第 i 行第 j 列的方法数

  1. 确定状态转移方程

由于机器人只能向右走或者向下走，所以到达网格第 i 行第 j 列的方法数 dp[i][j] 应该为到达它左边的方格的方法数与到达它上边的方格的方法数之和

所以，我们可以得到它的状态转移方程为

1
2
3
// dp[i - 1][j] 为 dp[i][j] 的上边方格
// dp[i][j - 1] 为 dp[i][j] 的左边方格
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  1. 确定 base case

对于第一行第一列上的网格而言，机器人只有一种方法到达该网格，即一直向右走 / 往下走，这种网格我们需要对其进行初始化

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int uniquePaths(int m, int n) {
    // 进行参数校验
    if (m <= 0 || n <= 0) return 0;
    // 创建一个 dp 数组，其中 dp[i][j] 表示到达网格第 i 行第 j 列处可以使用的方法数
    int[][] dp = new int[m][n];
    for (int i = 0;i < m;i++) {
        for (int j = 0;j < n;j++) {
            if (i == 0 || j == 0) {
                // 当 i == 0 或者 j == 0 时，代表在网格的第一行或者第一列，这种情况下，机器人只有一种方法到达
                dp[i][j] = 1;
            } else {
                // 当 i 与 j 均不为 0 时，此时要进行状态转移
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    // 返回 dp 数组中终点位置的值，由于这里的 i 和 j 从 0 开始，所以需要 -1 
    return dp[m - 1][n - 1];
}

2.4、不同路径 II

1、题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

  1. 示例一

image.png

1
2
3
4
5
6
7
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
  1. 示例二

image.png

1
2
输入：obstacleGrid = [[0,1],[0,0]]
输出：1

2、解题思路

这道题与上一道题的解题思路相似，唯一有区别的就是，对于是障碍物的网格，它在 dp 数组中的值为 0 ，转移方程依然与上题相同，但只有对应方格不为障碍物时，才能将值累加到 dp[i][j] 中

image.png

  • 如上图所示，对于第一行中存在障碍及障碍之后的那些网格，我们需要在 dp 数组中初始化为 0 ，对于第一列的网格同理
  • 对于其他网格，只有当该网格上没有障碍物时，我们才去计算该网格对应的 dp 值
  • 当我们求一个不是障碍物网格的 dp 值时，不需要考虑它的左边和上边是否为障碍物，因为有障碍物的网格直接被初始化为 0 了

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
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid == null || obstacleGrid.length == 0) return 0;
    int rowSize = obstacleGrid.length;
    int columnSize = obstacleGrid[0].length;
    int[][] dp = new int[rowSize][columnSize];
    for (int i = 0;i < rowSize;i++) {
        for (int j = 0;j < columnSize;j++) {
            // 保证起点位置没有障碍物
            if (i == 0 && j == 0 && obstacleGrid[i][j] == 0) {
                dp[i][j] = 1;
            }
            // 只有当该网格位置没有障碍物时，才进行运算
            if (obstacleGrid[i][j] == 0) {
                // 保证当前网格的上一行（上边网格）不越界
                if (i - 1 >= 0) {
                    dp[i][j] += dp[i - 1][j];
                }
                // 保证当前网格的前一列（左边网格）不越界
                if (j - 1 >= 0) {
                    dp[i][j] += dp[i][j - 1];
                }
            }
        }
    }
    return dp[rowSize - 1][columnSize - 1];
}

2.5、整数拆分

1、题目描述

给定一个正整数 n ，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

  1. 示例一
1
2
3
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
  1. 示例二
1
2
3
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

2、解题思路

  1. 确定 dp 数组的含义，其中 dp[i] 表示划分整数 i ，可以得到的最大乘积为 dp[i]

对于一个数 i 而言，当我们对它进行第一次划分后，对 i 这个数划分的问题就变成了两个子问题的集合，我们假设它划分后的两个数分别为 i - j 和 j ，假设此时我们要划分的数为 5 ，则 我们只需要将 dp[5] 的所有划分求出来，然后再求这些划分的结果的最大值即可

image.png

1
dp[5] = Math.max(dp[1] * dp[4], dp[2] * dp[3]);
  1. 对于一个整数 N ，它的整数划分能得到的最大乘积 dp[N] 的值为：
1
dp[N] = dp[i] * dp[N - i]

注意，这里的 dp[i] 和 dp[N - i] 也是划分后得到的最大乘积，也就是说，两个子问题会继续划分

  1. 对于上面 dp[N] 的划分， dp[i] 和 dp[N - i] 既可以进行划分，同时可以不进行划分

以 dp[5] 来说，当 i = 2 时，dp[5] = dp[2] * dp[3] ，2 如果进行划分，那么得到的值即为 1 + 1 = 2 ，得到的值是 1 ；3 如果进行划分，那么得到的最大划分值为 1 + 2 = 3，得到的最大划分值为 2；

此时 dp[5] 的子问题在不划分时得到的乘积比划分时得到的乘积大。

  1. 状态转移方程

为什么后面的数是 j * dp[i - j] ? 这是因为由于 j 的范围是 [1, i - 1)

1
dp[i] = Math.max(dp[i] , Math.max(j * (i - j) , dp[i - j] * j));
  1. 初始化 dp 数组的值

由于题目给的 n 的范围大于等于 2 ，所以我们可以算出 dp[2] = 1;dp[3] = 2;这就是 dp 数组的初始值

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int integerBreak(int n) {
    if (n <= 2) return 1;
    if (n == 3) return 2;
    // 初始化一个长度为 n + 1 的数组，我们最后要返回 dp[n]
    // 这个值表示值 n 的整数划分的最大乘积
    int[] dp = new int[n + 1];
    // 初始化 dp 数组

    dp[2] = 1;
    dp[3] = 2;
    // 这里的 i 从 3 开始，且到 n 结束，因为我们要计算 n 的结果
    for (int i = 3;i <= n;i++) {
        // 这里的 j 从 1 开始划分，到达 i - 1 结束
        for (int j = 1;j < i - 1;j++) {
            dp[i] = Math.max(dp[i], Math.max((i - j) * j, j * dp[i - j]));
        }
    }
    return dp[n];
}

2.6、不同的二叉搜索树

1、题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数

  • 示例一

image.png

1
2
输入：n = 3
输出：5
  • 示例二
1
2
输入：n = 1
输出：1

2、解题思路

除了动态规划外，这道题还可以使用递归来解决，在递归时，我们的思路是这样的

  • 当 n == 0 时，此时只有一种结构，即空树
  • 当 n == 1 时，只有一种树结构；当 n == 2 时，此时有两种树结构
  • 当有 n 个节点时，此时我们分情况进行讨论，我们记一棵有 n 个节点的二叉树有 F(n) 种结构
  1. 如果此时根节点的左子树为空，除 root 节点以外的所有节点都分布在右子树上，那么这种情况下有 F(n - 1) 种二叉树结构
  2. 如果此时根节点的左子树只有一个节点，那么除 root 节点和左子树节点以外的所有节点都会分布在右子树上，这种情况下有 1 * F(n - 2) 种结构，其中 1 为左子树的情况
  3. 同理，如果根节点的左子树有 a 个节点，而右子树有 n - a - 1 个节点，那么这种情况下将会有 F(a) * F(n - a - 1) 种结构

将上面的 1，2，3 种情况加起来，就是我们最终要求的答案，接下来，我们使用动态规划来解决这道题

  • 明确 dp 数组的含义，dp[i] 表示有 i 个结点的二叉树结构种数，即有 i 个结点的二叉搜索树有 dp[i] 种结构

  • 初始化 dp 数组，当 n == 0 或 n == 1 时， dp[i] = 1

  • 递推公式

我们假设左子树的结点有 j - 1 个，右子树的结点有 i - j 个，那么我们可以得到如下的递推公式

1
dp[i] += dp[j - 1] * dp[i - j]

为什么使用 += ？ 这是因为 dp[i] 的值应该是左子树结点个数从 [0 , n - 1] 与右子树结点个数从 [n - 1, 0] 的乘积总和

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int numTrees(int n) {
    // base case ，当 n == 0 || n == 1 时，结果为 1 ，当 n == 2 时，结果为 2
    if (n == 0) return 1;
    if (n <= 2) return n;
    // 创建一个 dp 数组，长度为 n + 1 ，我们要返回 dp[n] 的值
    int[] dp = new int[n + 1];
    // 初始化 dp 数组的值，由于我们的 i 从 1 开始，所以只需要初始化 dp[0] 即可
    dp[0] = 1;
    // 外层循环，表示结点个数从 1 - n
    for (int i = 1;i <= n;i++) {
        // 内层循环，表示左子树结点个数从 [0, n - 1]
        for (int j = 1;j <= i;j++) {
            // 状态转移，当前 dp[i] 的值为左子树所有可能出现的情况与右子树所有可能出现情况的乘积累加
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
}

2.7、分割等和子集

1、题目描述

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

  • 示例一
1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
  • 示例二
1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

2、解题思路

  • 如果数组元素的总和 sum 不是偶数，那么证明所给数组无法进行等和分割，直接返回 false

  • 获取数组中的最大元素 max ，如果 max > sum / 2 ，那么直接返回 false ，因为此时无法将数组分割为两个元素和相等的子集。

  • 这道题可以转换为一种 01 背包问题，不过，与普通 01 背包问题不同的是，前者要求选取的物品的重量之和不能超过背包总容量，而这道题要求选取的数字刚好等于整个数组的元素和的一半，即 sum / 2

  • dp 数组的含义

与 01 背包问题相似，我们需要创建一个二维的 dp 数组，其中 dp[i][j] 表示从数组 nums 的下标 [0,i] 范围内选取若干个正整数（可以是 0 个），是否存在着一种选取方案使得被选取的正整数的和等于 j 。

初始时， dp 中的全部元素都为 false

  • dp 数组初始化
  1. 当要寻找的正整数的和为 0 时，那么无论此时 nums 中所给的元素下标范围如何变化，都可以找到选取方案，即 dp[i][0] 应该初始化为 true
  2. 当 i 为 0 ，即 nums 数组仅有第一个元素 nums[0] 可供选择时，此时只有当 j == nums[0] 时，才有选择方案，即 dp[0][nums[0]] 应该初始化为 true
  • 状态转移方程，当 i > 0 且 j > 0 时，我们需要考虑以下两种情况
    • 如果 j >= nums[i] ，则对于当前的数字 nums[i] ，我们可以做出选择，既可以选取也可以不选取，只要两种选择有一种为 true ，那么 dp[i][j] 就为 true
      • 如果不选取 nums[i] ，则 dp[i][j] = dp[i - 1][j]
      • 如果选取 nums[i] ，则 dp[i][j] = dp[i - 1][j - nums[i]]
    • 如果 j < nums[i] ，则在选取的数字的和为 j 的情况下无法选取当前的数字 nums[i] ，因此有 dp[i][j] = dp[i - 1][j]

所以我们可以得到状态转移方程如下

1
2
3
4
5
6
7
8
   if (j >= nums[i]) {
       // 如果要分割的数大于当前数组正在遍历的数，那么我们可以进行选择
// 只要有一个选择的结果为 true ，那么当前的 dp[i][j] 就为 true
       dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
   } else {
       // 否则无法进行选择，直接用上一次遍历的情况代替
       dp[i][j] = dp[i - 1][j];
   }

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
34
35
36
37
38
39
40
public boolean canPartition(int[] nums) {
    if (nums == null || nums.length == 0) return true;
    int sum = 0, max = 0;
    for (int i = 0;i < nums.length;i++) {
        sum += nums[i];
        // 获取数组中的最大值
        max = Math.max(max, nums[i]);
    }
    // 如果 sum 不是偶数，那么直接返回 false
    if (sum % 2 != 0) return false;
    // 将 sum 除以 2 ，如果可以进行等和分割，那么数组中一定有几个元素的和等于 sum 除以 2 后的数
    sum /= 2;
    // 如果数组中的最大值大于数组总和的一半，那么直接返回 false 
    if (max > sum) return false;
    // 创建一个二维的 boolean 类型数组 dp ，这个 dp 数组有 nums.length 行 target + 1 列，其中 target = sum / 2;
    // dp[i][j] 表示在 nums 数组下标 [0,i] 范围内，是否可以找到一种选取方式，使得选取出来的数组值之和等于 j
    // 我们要求的就是 dp[nums.length - 1][target]
    boolean[][] dp = new boolean[nums.length][sum + 1];
    // 初始化 dp 数组中的值，其中，当 j == 0 时，此时无论 nums 下标范围为多少，都可以找到一种分配方案
    for (int i = 0;i < nums.length;i++) {
        dp[i][0] = true;
    }
    // 当 i == 0 时，dp[0][nums[0]] = true
    dp[0][nums[0]] = true;
    // 为什么外层从 1 开始？因为当 i 等于 0 时，只有 dp[0][nums[0]] 才为 true
    for (int i = 1;i < nums.length;i++) {
        int num = nums[i];
        // 内层循环为何从 1 开始，从 sum 结束
        // 因为当 j == 0 时，无论如何都有选取方案，这种情况我们已经在初始化过程中进行排除，所以从 1 开始
        // 同时由于我们循环判断待选取的值为结果的情况，所以需要循环到 sum 
        for (int j = 1;j <= sum;j++) {
            if (j >= num) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[nums.length - 1][sum];
}

2.8、最后一块石头的重量 II

1、题目描述

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出 任意两块石头 ，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

  1. 示例一
1
2
3
4
5
6
7
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
  1. 示例二
1
2
输入：stones = [31,26,33,21,40]
输出：5

2、解题思路

  • 这道题和分割等和子集的思路相似，也可以转换为 01 背包问题，我们需要从数组中选择一些石头为负数，从而使得整个数组的和最小

  • 在数组中，我们记整个数组元素的和为 sum ，负数元素的和为 neg ，则正数元素和为 sum - neg ，当 neg 与 sum - neg 最接近时，碰撞后剩下的石头最小

  • 也就是说， neg 越接近 sum / 2 ，碰撞后的石头越小

  • 所以问题转换为能否从 nums[0:i] 从取出某些石头，让这些石头的质量接近 j

  • 确定 dp 数组的含义

和上题相似，dp[i][j] 的值表示在石头数组下标为 [0, i] 的哪些石头中，是否存在一种选取方案，使得这些石头的重量为 j

  • 状态转移方程和上题的一样
  • dp 数组的初始化

只有 dp[0][0] 可以初始化为 true

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
public int lastStoneWeightII(int[] stones) {
    if (stones == null || stones.length == 0) return 0;
    int sum = 0, size = stones.length;
    for (int num : stones) sum += num;
    int target = sum / 2;
    boolean[][] dp = new boolean[size + 1][target + 1];
    for (int i = 0;i <= size;i++) {
        dp[i][0] = true;
    }
    dp[0][0] = true;
    for (int i = 1;i < size + 1;i++) {
        int curNum = stones[i - 1];
        for (int j = 1;j <= target;j++) {
            if (j >= curNum) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - curNum];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    for (int j = target;;--j) {
        if (dp[size][j]) {
            return sum - 2 * j;
        }
    }
}

2.9、最长递增子序列

1、题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

  • 示例一
1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
  • 示例二
1
2
输入：nums = [0,1,0,3,2,3]
输出：4

2、解题思路

  • 使用动态规划来解决这道题，首先我们需要确定 dp 数组的含义，在这道题中 ，dp[i] 表示以数组 nums[i] 为结尾的最长递增子序列的长度。

  • 我们可以这样思考，对于数组中的元素 nums[i] ，只要我们在 [0,i - 1] 的位置中找到一个小于 nums[i] 的元素 nums[j] ，然后将 num[i] 拼接在 nums[j] 后，就可以得到一个以 nums[i] 为结尾的最长递增子序列，所以我们可以得到以下的递推公式

1
dp[i] = Math.max(dp[i], dp[j] + 1);// 当 nums[j] < nums[i] 且 j < i 时
  • 初始化 dp 数组，对于数组中的每一个元素来说，其都可以单独地作为一个子序列存在，故 dp[i] = 1

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    // 初始化 dp ，为每个位置填充上数值 1 
    Arrays.fill(dp, 1);
    int max = Integer.MIN_VALUE;
    // 遍历数组，为每个数组填充合适的值
    for (int i = 0;i < nums.length;i++) {
        // 内层循环是为外层循环服务的，目的是遍历当前数组 [0, i - 1] 的位置，然后计算出 dp[i] 的真正值
        for (int j = 0;j < i;j++) {
            if (nums[j] < nums[i]) {
                // 不断更新 dp[i] 的值，如果 nums[j] < nums[i] ，那么证明找到一个以 nums[i] 为结尾的递增子序列
                // 我们需要查看这个新的子序列的长度与之前找到了最长递增子序列长度的差别，然后决定是否更新最长递增子序列的值
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

2.10、打家劫舍

1、题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

  • 示例一
1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
  • 示例二
1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

2、解题思路

  • 确定 dp 数组的含义

dp[i] 表示在考虑下标 i （包括 i ）以内的房屋，最多可以偷窃的金额为 dp[i]

  • 确定状态转移方程
  1. 如果选择偷取第 i 间屋子，那么我们就不能偷取第 i - 1 间屋子
  2. 如果选择不偷取第 i 间屋子，那么此时最多能偷窃的金额即为考虑第 i - 1 间屋子时能获取的金额，即此时 dp[i] = dp[i - 1]

我们应该在这两个选择中选取一个比较大的数，将其作为 dp[i] 的值

1
dp[i] = Math.max(dp[i - 2] + value[i], dp[i - 1]);
  • 初始化 dp 数组
  1. 当我们只考虑第 0 间屋子时，我们能得到的最大收益是第 0 间屋子中存放的钱
  2. 当我们只考虑第 0 间屋子与第 1 间屋子时，我们能得到的最大收益为 Math.max(value[0], value[1])

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    // 如果长度为 1 ，那么直接返回 nums[0] 即可
    if (nums.length == 1) return nums[0];
    // 创建一个 dp 数组，长度为 nums.length 
    int[] dp = new int[nums.length];
    // 初始化 dp 数组
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2;i < nums.length;i++) {
        // 进行状态转移，此时我们有两种选择
        //1 选择不偷第 i 间房子，那么 dp[i] 的值即为 dp[i - 1] 的值
        //2 选择偷第 i 间房子，那么我们就不能偷第 i - 1 间房子，此时我们在考虑第 i 间房子时最获取的最大收益即为 dp[i - 2] + 第 i 间屋子中的钱
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    // 返回 dp[nums.length - 1] ，这个值代表在考虑 nums.length - 1 间房子时，能获取的最大收益
    return dp[nums.length - 1];
}

2.11、打家劫舍 II

1、题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

  • 示例一
1
2
3
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
  • 示例二
1
2
3
4
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

2、解题思路

这道题也是基于 打家劫舍 I 的，与打家劫舍 I 不同的是，第一间房屋和最后一间房屋不能同时偷窃，那么需要如何保证第一间房屋和最后一间房屋不同时偷窃呢？

  1. 如果我们偷窃了第 0 间房屋，那么我们就不能偷窃最后一间房屋，所以选择偷窃第 0 间房屋时，我们能偷窃的房屋下标范围为 [0, nums.length - 2] （偷窃第一间到倒数第二间房子）
  2. 如果我们偷窃了最后一间房屋，那么我们就不能偷窃第一间房屋，所以选择偷窃最后一间房屋时，我们能偷窃的房屋下标范围为 [1, nums.length - 1]

所以我们可以进行两次动态规划，动态规划的逻辑与打家劫舍 I 相同，然后取两次动态规划得到结果的最大值即可。

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
public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    if (nums.length == 2) return Math.max(nums[0], nums[1]);
    // 对 nums 中 [0, nums.length - 2] 范围的子集进行动态规划，得到结果 1 
    int firstResult = getMoneyByRange(nums, 0, nums.length - 2);
    // 对 nums 中 [1, nums.length - 1] 范围的子集进行动态规划，得到结果 2 
    int secondResult = getMoneyByRange(nums, 1, nums.length - 1);
    // 返回两个结果的最大值
    return Math.max(firstResult, secondResult);
}

/**
 * 对 nums 数组中下标为 [begin, end] 范围内打家劫舍，得到利益最大值
 */
private int getMoneyByRange(int[] nums, int begin, int end) {
    if ((end - begin + 1) == 0) return 0; 
    if (end == begin) return nums[begin];
    if (end - begin == 1) return Math.max(nums[begin], nums[end]);
    // 创建一个 dp 数组，长度为 nums.length 
    int[] dp = new int[nums.length];
    // 初始化 dp 数组
    dp[begin] = nums[begin];
    dp[begin + 1] = Math.max(nums[begin], nums[begin + 1]);
    for (int i = begin + 2;i <= end;i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[end];
}

2.12、买卖股票的最佳时机

1、题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

  • 示例一
1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
  • 示例二
1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

2、解题思路

使用动态规划求解这道题

  • 明确 dp 数组的含义

对于第 i 天的用户来说，他可以持有股票，也可以不持有股票，我们 使用 0 表示这个用户持有股票，使用 1 表示这个用户未持有股票，所以这里我们需要使用一个二维的 dp 数组来进行求解，其中**dp[i][j] 表示在第 i 天，用户持股状态为 j 时，所获取的最大收益**

  • 明确状态转移方程
  1. 如果第 i 天持有股票，那么可以由两个状态推导出来

第 i - 1 天就持有股票，那么就保持现状，所得利润就是昨天持有股票的所得利润，即此时 dp[i][0] = dp[i - 1][0]

第 i 天买入股票，所得利润应该为负数，此时 dp[i][0] = -prices[i]

需要在上面两个值中选择最大值，即

1
dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
  1. 如果第 i 天没有持有股票，也可以从两个状态推导出来

第 i - 1 天就已经不持有股票，那么保持现状，此时 dp[i][1] = dp[i - 1][1]

第 i - 1 天持有股票，那么所得利润就是前一天持有股票时拥有的利润 dp[i - 1][0] 与今天卖出股票所得利润的总和 prices[i] ，即 dp[i][1] = dp[i - 1][0] + prices[i]

同样需要在以上两个值中选择最大值，即

1
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
  • 初始化 dp 数组

根据方程可知，后面 dp 数组的值都有 dp[0][0] 与 dp[0][1] 推导而来，所以我们需要初始化以上两个值，即

1
2
dp[0][0] = -prices[0];
dp[0][1] = 0;
  • 最终我们要返回的结果为 dp[nums.length - 1][1] ，即最后一天，用户手中没有持有股票时，能获取的最大利润

3、解题代码

  • 未进行空间优化前
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) return 0;
    // 创建一个二维的 dp 数组，其中列数为 2 ，行数为 prices.length
    // 其中 dp[i][0] 表示在第 i 天，用户手中持有股票时，所能获取的最大收益，dp[i][1] 表示在第 i 天，用户手中没有持有股票时，所能获取的最大收益 
    int[][] dp = new int[prices.length][2];
    // 初始化 dp 数组，在第 0 天持有股票，那么收益为 -prices[0]，在第 0 天没有持有股票时，那么收益为 0 
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    // 最终返回的结果为 dp[]
    for (int i = 1;i < prices.length;i++) {
        // 进行状态转移
        //1 第 i 天手中持有股票的状态可以由两个状态得来
        //1.1 第一个状态，即第 i - 1 天就已经持有股票，这种状态下则保持原样
        //1.2 第二个状态，即第 i - 1 天没有持有股票，股票是在第 i 天买入的，此时应该减去价格
        dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
        //2 同理，第 i 天手中没有持有股票的状态也由两个状态得来
        //2.1 第一个状态，即第 i - 1 天就已经卖掉股票了，这种状态下保持原样
        //2.2 第二个状态，即在第 i 天才卖掉股票，此时结果应该为在第 i - 1 天持有股票的利润 + 第 i 天卖出去的利润
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
    }
    return dp[prices.length - 1][1];
}
  • 进行空间优化

由于第 i 天的状态只有第 i - 1 天的状态推导而来，所以我们可以缩减 dp 数组的行数，将 dp 数组改造为一个 2 * 2 的二维数组

  1. 使用 dp[1][0] 表示第 i 天持有股票时获取的最大利润
  2. 使用 dp[0][0] 表示第 i - 1 天持有股票时能获取的最大利润
  3. 使用 dp[1][1] 表示第 i 天没有持有股票时获取的最大利润
  4. 使用 dp[0][1] 表示第 i - 1 天没有持有股票时能获取的最大利润
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) return 0;
    int[][] dp = new int[2][2];
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    for (int i = 1;i < prices.length;i++) {
        dp[1][0] = Math.max(dp[0][0], -prices[i]);
        dp[1][1] = Math.max(dp[0][1], dp[0][0] + prices[i]);
        // 更新滚动数组的值
        dp[0][0] = dp[1][0];
        dp[0][1] = dp[1][1];
    }
    // 返回在最后一天没有持有股票的最大利润
    return dp[1][1];
}

2.13、最长连续递增序列

1、题目描述

给定一个未经排序的整数数组，找到最长且 连续递增的子序列 ，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

  • 示例一
1
2
3
4
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
  • 示例二
1
2
3
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

2、解题思路

  • 与最长递增子序列不同的是，最长连续递增序列要求连续，我们仍然可以延续之前的思路，对于下标为 i 的数组元素来说，如果它的前一个元素是一个最长连续递增序列的末尾且 nums[i - 1] < nums[i]，那么我们就可以将 nums[i] 拼接到 nums[i - 1] 的末尾，形成一个更长的连续序列
  • 确定 dp 数组中的含义

dp[i] 表示以下标为 i 的数组元素为结尾的最长递增序列的长度

  • 确定状态转移方程

对于 nums[i] 来说，如果 nums[i - 1] < nums[i] ，那么证明此时 nums[i] 可以拼接到以 nums[i - 1] 为结尾的最长连续递增序列中，此时递推公式应该为

1
2
3
if (nums[i - 1] < nums[i]) {
	dp[i] = Math.max(dp[i], dp[i - 1] + 1);
}
  • 初始化 dp 数组

对于数组中的任何一个元素，我们都可以将其单独看为一个最长连续递增序列，所以我们需要将 dp 数组全部初始化为 1

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public int findLengthOfLCIS(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int max = 1;
    for (int i = 1;i < nums.length;i++) {
        if (nums[i - 1] < nums[i]) {
            dp[i] = Math.max(dp[i], dp[i - 1] + 1);
        }
        max = Math.max(dp[i], max);
    }
    return max;
}

2.14、最长重复子数组

1、题目描述

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

  • 示例一
1
2
3
4
5
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3, 2, 1] 。

2、解题思路

  • 确定 dp 数组的含义

dp[i][j] 表示数组 nums1 下标范围为 [0, i - 1] 的子数组与 nums2 下标为 [0, j - 1] 的子数组的最长公共数组的长度

  • 确定状态转移方程

对于上面提到的两个子数组，如果此时存在 nums1[i - 1] == nums2[j - 1] ，那么此时这两个子数组的最长公共长度就为 nums1[0: i - 2] 、 nums2[0: j - 2] 两个子数组的最长公共数组长度 + 1，即

1
2
3
if (nums1[i - 1] == nums2[j - 1]) {
	dp[i][j] = dp[i - 1][j - 1] + 1;
}
  • 初始化 dp 数组

根据上面 dp 数组的定义，我们知道在 dp 数组中，dp[i][0] 和 dp[0][j] 是没有意义的，所以我们直接初始化为 0

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findLength(int[] nums1, int[] nums2) {
    // base case 
    if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return 0;
    // 创建一个 dp 数组，其中 dp[i]][j] 表示 nums1 中以 i - 1 下标为结尾的子数组 a ，nums2 中以 j - 1 下标为结尾的子数组 b ，ab 数组中最长公共子数组的长度
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];
    // 使用一个全局变量保存最长公共子数组的长度
    int max = 0;
    // 这里的循环必须从 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;
            }
            // 更新 max
            max = Math.max(max, dp[i][j]);
        }
    }
    return max;
}

2.15、最长公共子序列

1、题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  1. 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
  2. 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
  • 示例一
1
2
3
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
  • 示例二
1
2
3
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

2、解题思路

  • 确定 dp 数组的含义

和上一题一样，我们使用一个二维数组来解决这道题，其中 dp[i][j] 表示字符串 text1 以 i - 1 为结尾的子串与字符串 text2 以 j - 1 为结尾的子串之间最长公共子序列的长度。

  • 确定状态转移方程

在 LCS 问题中，我们设 text1 字符串的子串为 X = <x1,x2…xm>，text2 字符串的子串为 Y = <y1,y2…yn> ，Z = <z1,z2…zk> 为它们的一个公共子序列，经过分析，有

  1. 如果 xm == yn ，则 zk = xm = yn 且 Zk - 1 是 Xm - 1 与 Yn - 1 的一个 LCS （最长公共子序列）
  2. 如果 xm != yn 且 zk != xm ，则 Zk 是 Xm - 1 与 Yn 的一个 LCS
  3. 如果 xm != yn 且 zk != yn ，则 Zk 是 Yn - 1 与 Xm 的一个 LCS

所以我们可以得到以下的状态转移方程

1
2
3
4
5
if (xi == yj) {
	dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
	dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
  • 初始化 dp 数组

当 i == 0 或者 j == 0 时，dp[i][j] 没有意义，此时让 dp[i][j] 为 0 即可

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int longestCommonSubsequence(String text1, String text2) {
    if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) return 0;
    // 创建一个二维的 dp 数组
    int[][] dp = new int[text1.length() + 1][text2.length() + 1];
    // 进行循环，注意，循环应该从下标 1 开始
    for (int i = 1;i <= text1.length();i++) {
        for (int j = 1;j <= text2.length();j++) {
            // 同时这里比较的应该是 i - 1 与 j - 1 的字符，因为循环从 1 开始
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) { // 如果 i - 1 下标与 j - 1 下标的字符相同
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else { // 如果 i - 1 下标与 j - 1 下标的字符不相同
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // 返回 dp[text1.length()][text2.length()] 即可，这个值代表 text1 字符串与 text2 字符串之阿的最长公共子序列的长度
    return dp[text1.length()][text2.length()];
}

2.16、 不相交的线

1、题目描述

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

  1. nums1[i] == nums2[j]
  2. 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

  • 示例 1：
1
2
3
4
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
  • 示例 2：
1
2
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3

2、解题思路

  • 如果我们将数组看为一个字符串，那么这道题其实就是求两个数组的 LCS 问题

直线不能相交，也就是说在数组 A 中找到一个与数组 B 相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，那么链接相同数字的直线就不会相交。

3、解题代码

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

2.17、最大子序和

1、题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

  • 示例一
1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

2、解题思路

  • 确定 dp 数组含义

其中 dp[i] 表示包括下标 i 之间的最大连续子序列和

  • 确定递推公式

对于 dp[i] ，有两个方向可以将其推导出来

  1. dp[i - 1] + nums[i]

这表示将当前元素加入到以 i - 1 为下标的连续子序列和中，此时 dp[i - 1] 大于等于 0

  1. nums[i]

这表示重新计算连续子序列和，以 i - 1 为结尾下标的连续子序列和的值小于 0 ，此时 dp[i - 1] + nums[i] 的值反倒小于 nums[i]

  • 初始化 dp 数组

由于 dp[i] 表示包括下标 i 之间的最大连续子序列和，所以对于 dp[0] ，我们可以将其初始化为 nums[0]

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maxSubArray(int[] nums) {
    // base case 
    if (nums == null || nums.length == 0) return 0;
    // 使用一个变量来表示我们要返回的最大结果，初始化为 nums[0]
    int max = nums[0];
    // 创建一个长度为 nums.length 的 dp 数组
    int[] dp = new int[nums.length];
    // 初始化 dp 数组，dp[i] 表示以 i 下标为结尾的最大子序和的值，所以我们直接初始化 dp[0] 为 nums[0]
    dp[0] = nums[0];
    for (int i = 1;i < nums.length;i++) {
        // 进行选择
        //1 选择一，将 nums[i] 加入到以 i - 1 为结尾的子序列和中
        //2 选择二，直接将 nums[i] 看为一次新的开始
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        // 更新最大结果
        max = Math.max(dp[i], max);
    }
    return max;
}

2.18、判断子序列

1、题目描述

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

  • 示例
1
2
输入：s = "chm", t = "hialchemist"
输出：true

2、解题思路

方法一：使用双指针解决这道题

  • 初始化两个指针，其中 sub 指针指向 s 的第一个字符，main 指针指向 t 的第一个字符
  • 如果 sub 与 main 指向的字符相等，那么 sub 与 main 同时后移
  • 如果不相等，那么此时 sub 保持不动，而 main 后移

方法二：使用动态规划求解这道题，我们可以求解出两个字符串的最长公共子序列长度 len ，然后判断 len 是否等于 s 的长度，所以问题又变为了求两个字符串最长公共子序列的问题。

  • dp 数组的含义，其中， dp[i][j] 表示字符串 s 以 i - 1 下标为结尾的子串与字符串 t 以 j - 1 下标为结尾的子串，它们的最长公共子序列长度

  • 状态转移方程

  1. 如果 s.charAt(i - 1) == t.charAt(j - 1) ，那么 dp[i][j] = dp[i - 1][j - 1] + 1
  2. 如果 s.charAt(i - 1) != t.charAt(j - 1) ，那么 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
  • dp 数组的初始化，由于 dp[i][0] 、 dp[0][j] 无意义，所以初始化为 0

方法三：使用动态规划解决这道题，我们以示例中所给的两个字符串进行打表



HIALCHEMLST
truetruetruetruetruetruetruetruetruetruetruetrue
Cfalsefalse
falsefalsefalsetruetruetruetruetruetruetrue
Hfalsefalse
false
false
false
false
truetruetruetruetruetrue
Mfalsefalse
false
false
false
false
false
false
truetruetruetrue
  1. 在上面的表格中，横向的行上分布着字符串 t ，而纵向的列上分布着字符串 s ，对于第一行，我们全将内容置为 true ，这表示当 s 为空字符串时，无论 t 为什么， s 都是 t 的子序列；对于第一列，我们将除（1，1）以外内容全部置为 false ，这表示当 t 为空字符串时，除了 s 为空串的情况外，s 都不是 t 的子串。
  2. 当 s == "c" 且 t == "hialc" 时，此时我们查看这个格子的左上角，发现这个格子的左上角也为 true ，这表示当 s 与 t 的最后一个字符相等时，此时我们只需要判断 s 去掉最后一个字符的子串 s[0, s.length() - 2] 是不是 t 去掉最后一个字符的子串 t[0, t.length() - 2] 的子序列即可，如果是，则结果为 true ，否则为 false
1
2
3
4
// 假设 dp[i][j] 表示 s[0, i - 1] 是否为 t[0, j - 1] 的子序列
if (s.charAt(i - 1) == t.charAt(i - 1)) {
	dp[i][j] = dp[i - 1][j - 1];
}
  1. 如果有一个元素 dp[i][j] = true ，那么对于该行中该元素后的所有元素，应该全部为 true ，比如说 s = “c” 是 t = “abc” 的子序列，那么 s 就应该是 t = “abcd” 、 “abcde” 的子序列
1
2
3
if (s.charAt(i - 1) != t.charAt(i - 1)) {
	dp[i][j] = dp[i][j - 1];
}

3、解题代码

双指针法

1
2
3
4
5
6
7
8
9
10
11
public boolean isSubsequence(String s, String t) {
    if (t.length() == 0 && s.length() != 0) return false;
    int sub = 0, main = 0;
    while (sub < s.length() && main < t.length()) {
        if (s.charAt(sub) == t.charAt(main)) {
            sub++;
        }
        main++;
    }
    return sub >= s.length();
}

动态规划一，解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isSubsequence(String s, String t) {
    if (t.length() == 0 && s.length() != 0) return false;
    int length1 = s.length(), length2 = t.length();
    int[][] dp = new int[length1 + 1][length2 + 1];
    for (int i = 1;i <= length1;i++) {
        for (int j = 1;j <= length2;j++) {
            if (s.charAt(i - 1) == t.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[length1][length2] == s.length();
}

动态规划二，解法三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isSubsequence(String s, String t) {
    if (t.length() == 0 && s.length() != 0) return false;
    int length1 = s.length(), length2 = t.length();
    boolean[][] dp = new boolean[length1 + 1][length2 + 1];
    // base case ，由于这里行数是 s 长度，所以我们应该将第一列置为 true 
    for (int j = 0;j <= length2;j++) {
        dp[0][j] = true;
    }
    for (int i = 1;i <= length1;i++) {
        for (int j = 1;j <= length2;j++) {
            // 如果 i - 1 与 j - 1 指针指向的字符相等，那么判断 s[0, i - 2] 是否为 t[0, j - 2] 的子串（取左上角的元素）
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 否则直接取它左边的元素即可
                dp[i][j] = dp[i][j - 1];
            }
        }
    }
    return dp[length1][length2];
}

2.19、不同的子序列

1、题目描述

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

  • 示例一

输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabb b it
ra b bbit
rab b bit

  • 示例二

输入：s = “babgbag”, t = “bag”
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 “bag” 的方案。
ba b g bag
ba bgba g
b abgb ag
ba b gb ag
babg bag

2、解题思路

使用动态规划求解这道题

  • 定义 dp 数组的含义

其中 dp[i][j] 表示字符串 s 中下标范围为 [0, i - 1] 的子串，它的子序列中出现字符串 t 中下标范围为 [0, j - 1] 的子串的个数

  • 确定状态转移方程

    • 当 s[i - 1] != t[j - 1] 时，此时我们只能让 s 字符串中下标为 [0, i - 2] 位置的子串与 t 字符串中下标为 [0, j - 1] 的子串进行匹配，因为此时 s[i - 1] 不能用来匹配，所以有 dp[i][j] = dp[i - 1][j]
    • 当 s[i - 1] == t[j - 1] 时，此时我们有两种选择
    1. 使用 s[i - 1] 来与 t[j - 1] 进行匹配，这种情况下， dp[i][j] = dp[i - 1][j - 1]
    2. 不使用 s[i - 1] 来与 t[j - 1] 进行匹配，这种情况下，dp[i][j] = dp[i - 1][j]

这里借用 LeetCode 题解中一位老哥的图进行理解

image.png

  • 初始化 dp 数组
  1. 当 j == 0 时，此时 t 字符串所给的子串 y 为空串，那么对于 s 中的任意一个子串 x ，x 都可以包含 y ，故 dp[i][0] = 1
  2. 当 i == 0 时，此时 s 字符串所给的子串 x 为空串，那么对于 t 中除空串外的任意一个字符串 y ，x 都不可能包含 y ，所以 dp[0][j] = 0 （这里的 j >= 1）

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
public int numDistinct(String s, String t) {
    if (t.length() > s.length()) return 0;
    // 创建一个二维的 dp 数组，其中 dp[i][j] 表示 s 字符串中下标范围为 [0, i - 1] 的子串 a 中，含有 t 字符串中下标范围为 [0,j - 1] 的子串 b 的个数
    int length1 = s.length(), length2 = t.length();
    int[][] dp = new int[length1 + 1][length2 + 1];
    // 初始化 dp 数组，当 j == 0时，dp[0][j] = 1
    for (int i = 0;i <= length1;i++) {
        dp[i][0] = 1;
    }
    for (int i = 1;i <= length1;i++) {
        for (int j = 1;j <= length2;j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                // 如果 s[i - 1] == t[j - 1]，那么此时我们有两种选择
                // 选择 1 ，让 s[i - 1] 与 t[j - 1] 进行匹配，此时得到的结果为 dp[i - 1][j - 1] 
                // 选择 2 ，让 s[i - 1] 不与 t[j - 1] 进行匹配，此时得到的结果为 dp[i - 1][j]
                // 需要将这两个结果综合起来
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                // 如果 s[i - 1] != t[j - 1]，那么此时 s[i - 2] 与 t[j - 1] 进行匹配，因为 s[i - 1] 不能匹配
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[length1][length2];
}

2.20、两个字符串的删除操作

1、题目描述

给定两个单词 word1 和 word2 ，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

  • 示例
1
2
3
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

2、解题思路

动态规划解法一

  • 确定 dp 数组的含义，dp[i][j] 表示以 i - 1 为结尾的字符串 word1 和以 j - 1 为结尾的字符串 word2 ，想要达到相等，所需要删除的元素的最少次数

  • 确定递推公式

  1. 当 word1[i - 1] == word2[j - 1] 时，此时我们称 word1[i - 1] 和 word2[j - 1] 为公共字符，增加公共字符后不会使最少删除次数发生改变，比如 site 与 hae 的最少删除次数和 sit 与 ha 的最少删除次数一致，所以有
1
2
3
if (word1[i - 1] == word2[j - 1]) {
	dp[i][j] = dp[i - 1][j - 1]
}
  1. 当 word1[i - 1] != word2[j - 1] 时，我们需要考虑三种情况
    1. 删除 word1[i - 1] ，此时最少操作数为 dp[i - 1][j] + 1，这里的 1 就是删除 word1[i - 1] 这次操作
    2. 删除 word2[j - 1] ，此时最少操作数为 dp[i][j - 1] + 1
    3. 同时删除 word1[i - 1] 和 word2[j - 1] ，此时最少操作数为 dp[i - 1][j - 1] + 2，其中 2 为删除 word1[i - 1] 和 word2[j - 1] 两次操作，从三者之间取最小值，就是这种情况下的最小删除次数
  • 初始化 dp 数组
  1. 当 j == 0 时， word2 为空串，此时最小删除数等于 word1 的长度，即 dp[i][0] = i
  2. 同理，当 i == 0 时， word1 为空串，此时最小删除数等于 word2 的长度，即 dp[0][j] = j

动态规划解法二

  • 由题意得 word1 与 word2 长度，分别记为 len1 和 len2 ，然后使用动态规划求解 word1 与 word2 的最长公共子序列长度，记为 maxLength ，我们要求的结果为 len1 + len2 - 2 * maxLength

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
34
35
36
37
public int minDistance(String word1, String word2) {
    int length1 = word1.length(), length2 = word2.length();
    if (length1 == 0) return length2;
    if (length2 == 0) return length1;
    int[][] dp = new int[length1 + 1][length2 + 1];
    // 初始化 dp 
    // 当 j == 0 时，word1 和 word2 的最小删除数为 word1 子串的长度，即 i 
    for (int i = 0;i <= length1;i++) {
        dp[i][0] = i;
    }
    // 同理初始化 dp[0][j]
    for (int j = 0;j <= length2;j++) {
        dp[0][j] = j;
    }
    for (int i = 1;i <= length1;i++) {
        for (int j = 1;j <= length2;j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                // 此时 word1[i - 1] 与 word2[i - 2] 相等，所以它是公共字符
                // 当前两个子串的最小删除数与去掉公共字符的最小删除数相等
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 此时有三种情况进行考虑，分别是
                dp[i][j] = Math.min(
                    Math.min(
                        //1 删去 word1[i - 1]
                        dp[i - 1][j] + 1,
                        //2 删去 word2[j - 1]
                        dp[i][j - 1] + 1),
                    //3 同时删去 word1[i - 1] 和 word2[j - 1]
                    dp[i - 1][j - 1] + 2
                );
                // 我们需要取上面三种情况的最小值
            }
        }
    }
    return dp[length1][length2];
}

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minDistance(String word1, String word2) {
    int length1 = word1.length(), length2 = word2.length();
    if (length1 == 0) return length2;
    if (length2 == 0) return length1;
    int[][] dp = new int[length1 + 1][length2 + 1];
    for (int i = 1;i <= length1;i++) {
        for (int j = 1;j <= length2;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 - 1][j], dp[i][j - 1]);
            }
        }
    }
    return length1 + length2 - 2 * dp[length1][length2];
}

2.21、编辑距离

1、题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符
  • 示例一
1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
  • 示例二
1
2
3
4
5
6
7
8
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

2、解题思路

  • 我们以一个例子，通过打表的方式来观察编辑次数与所给字符串的关系

以 CTGCG 与 GATAG 为例



CTGCG
012345
G112234
A222334
T332344
A443345
G554344
  1. 当所给的字符串均为空串时，此时二者的编辑距离为 0
  2. 当 s1 为空串，s2 不为空串时，此时二者之间的最短编辑距离为 s2.lengt()，反之亦然，所以我们可以将表格中的第一行第一列进行初始化
  3. 当 s1 为 “G” 且 s2 为 “C” 时，二者的最小编辑距离为 1 ，此时只需要将 G 修改为 1 即可，我们根据 s1 与 s2 的情况填充表格
  • 定义 dp 数组的含义

其中 dp[i][j] 表示 word1 中下标范围为 [0, i - 1] 的子串 a 与 word2 中下标范围为 [0, j - 1] 的子串 b ，它们二者之间的最短编辑距离。

  • 状态转移方程
  1. 当 word1[i - 1] == word2[j - 1] 时，我们可以将这个相等的字符看为一个公共字符， word1[0. i - 1] 子串与 word2[0, j - 1] 子串的最短编辑距离与二者去掉公共字符后留下来的子串的最短编辑距离相等，比如说 hat 与 het 最短编辑距离和 ha 与 he 的最短编辑距离相等
1
dp[i][j] = dp[i - 1][j - 1]
  1. 当 word1[i - 1] != word2[j - 1] 时，此时我们有多个操作可供选择
    1. word1 删除一个元素，那么就是以下标 word1[0, i - 2] 与 word2[0, j - 1] 的最短编辑距离，再加上一个删除操作，此时得到的式子应该为 dp[i - 1][j] + 1
    2. word2 删除一个元素，那么就是以下标 word1[0, i - 1] 与 word2[0. j - 2] 的最短编辑距离，再加上一个删除操作，此时得到的式子应该为 dp[i][j - 1] + 1
    3. 替换元素，此时 word1 替换 word1[i - 1] ，使其等于 word2[j - 1] ，此时我们又可以将 word1[i - 1] 看为一个公共元素，只不过我们需要原来的基础上加上一次编辑，此时得到的式子为 dp[i - 1][j - 1] + 1
    4. 对于添加操作来说， word1 添加一个字符，就相当于 word2 删除一个字符，比如说，当 word1 为 abce ，word2 为 abc 时，word1 删去 e 与 word2 加上 e 的结果都相同，所以我们只需要考虑删除的情况即可
  • 初始化 dp 数组

当两个字符串有一个为空串时，此时二者的最短编辑距离即为另外一个字符串的长度，我们假设 dp[i][j] 中，i 为 word1 字符串下标的变化情况，而 j 为 word2 字符串下标的变化情况，此时有

  1. 当 j == 0 时，此时我们初始化 dp[i][0] = i
  2. 当 i == 0 时，此时我们初始化 dp[0][j] = j

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
34
35
36
public int minDistance(String word1, String word2) {
    int length1 = word1.length(), length2 = word2.length();
    if (length1 == 0 && length2 == 0) return 0;
    if (length1 == 0 && length2 != 0) return length2;
    if (length2 == 0 && length1 != 0) return length1;
    // 创建一个 dp 数组
    int[][] dp = new int[length1 + 1][length2 + 1];
    // 初始化 dp 数组
    for (int i = 0;i <= length1;i++) {
        dp[i][0] = i;
    }
    for (int j = 0;j <= length2;j++) {
        dp[0][j] = j;
    }
    for (int i = 1;i <= length1;i++) {
        for (int j = 1;j <= length2;j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                // 对于公共字符，直接取去掉公共字符后的最短编辑距离即可
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 对于不是公共字符的情况，我们需要进行选择
                dp[i][j] = Math.min(
                    Math.min(
                        // 选择一：删除 word1[i - 1]
                        dp[i - 1][j] + 1,
                        // 选择二：删除 word2[j - 1]
                        dp[i][j - 1] + 1
                    ),
                    // 选择三：替换 word1[i - 1]
                    dp[i - 1][j - 1] + 1
                );
            }
        }
    }
    return dp[length1][length2];
}

2.22、最长回文子序列

1、题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

  • 示例一
1
2
3
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
  • 示例二
1
2
3
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

2、解题思路

  • 确定 dp 数组的含义

其中 dp[i][j] 表示字符串 s 中下标范围为 [i ,j] 的子串 a 中最长回文子序列的长度

  • 确定递推公式
  1. 如果 s[i] == s[j] ，那么 dp[i][j] = dp[i + 1][j - 1] + 2

image.png

  1. 如果 s[i] != s[j] ，那么此时 s[i] 与 s[j] 同时加入并不能增加 [i, j] 区间回文子序列的长度，那么我们分别加入 s[i] ，s[j] ，查看哪一个可以组成最长的最文子序列

image.png

所以我们可以得出递推公式为

1
2
3
4
5
if (s[i] == s[j]) {
	dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
	dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
  • 初始化 dp 数组

对于 dp[i][j] ，当 i == j 时，子串 s[i] 就 i 是一个回文子序列，长度为 1 ，所以我们初始化 dp[i][i] = 1

  • 确定遍历顺序

根据递推公式，dp[i][j] 需要根据 dp[i + 1][j - 1] 、 dp[i + 1][j] 和 dp[i][j - 1] 退出，如果我们希望得出 dp[i][j] ，那么我们就先有当前行下一行的数据，所以对于外层行遍历，我们需要从尾到头进行遍历，而对于内层列遍历，我们需要从头到尾进行遍历

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int longestPalindromeSubseq(String s) {
    int len = s.length();
    if (len == 0) return 0;
    // 创建一个 dp 数组
    int[][] dp = new int[len][len];
    // 初始化 dp 数组
    for (int i = 0;i < len;i++) {
        dp[i][i] = 1;
    }
    for (int i = len - 1;i >= 0;i--) {
        for (int j = i + 1;j < len;j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][len - 1];
}

2.23、让字符串成为回文串的最少插入次数

1、题目描述

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

  • 示例一
1
2
3
输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
  • 示例二
1
2
3
输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

2、解题思路

  • 确定 dp 数组的含义

其中 dp[i][j] 表示字符串 s 中下标范围为 [i,j] 的子串，要变为回文串所需要的最少插入次数。

  • 确定状态转移方程
  1. 当 s[i] == s[j] 时，此时对于子串 s[i. j] 而言，左右两边的字符不用修改，我们只需要求让下标范围为 [i + 1,j - 1] 的子串变为回文串的最少插入次数即可，此时有 dp[i][j] = dp[i + 1][j - 1]

比如说，对于字符串 abcda ，由于它左右两边的字符相等，所以我们只需要求出让 bcd 变为回文串的最少插入次数，即可求出让整个字符串变为回文串的最少插入次数

  1. 当 s[i] != s[j] 时，此时我们需要选择最优的插入方案，即在下面的结果中选择最小值
    1. 将 s[i] 插入 j - 1 的位置，同时将 s[j] 插入到 i - 1 的位置，此时插入后的字符串中存在以下关系，即 s[i - 1] == s[j] 且 s[i] == s[j - 1] ，比如说对于字符串 abcde ，我们将 s[i] 插入到 e 的左边，将 s[j] 插入到 a 的左边，字符串变为 eabcdae ，此时情况又转为了 s[i] == s[j] 的情况，我们只需要考虑 bcd 变为回文串所需要的最小插入次数即可，即 dp[i][j] = dp[i + 1][j - 1] + 2 ，这种做法可能不是最优解，比如说，对于字符串 aaax ，我们只需要在左边插入一个 x 就可以将其变为回文串。
    2. 我们先将 s[i + 1,j] 或者 s[i, j - 1] 变为回文串。假设将 s[i + 1, j] 变为回文串的代价 a 和将 s[i, j - 1] 变为回文串的代价 b ，此时我们比较两个代价的大小，取代价小的那个子串进行修改，最后将结果 + 1 即得到将字符串 s[i,j] 变为回文串的最小插入次数，这种情况下，式子为 dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1 ；比如说对于字符串 aaax ，我们可以看出，将子串 aaa 变为回文串的代价较小，所以将 aaax 变为回文串的代价即为将 aaa 变为回文串的代价 + 1，即 1 .
  2. 所以，本题的状态转移方程如下
1
2
3
4
5
if (s[i] == s[j]) {
	dp[i][j] = dp[i + 1][j - 1]
} else {
	dp[i][j] = Math.min(Math.min(dp[i + 1][j] + 1, dp[i][j - 1] + 1), dp[i + 1][j - 1] + 2);
}
  • 初始化 dp 数组

当 i == j 时，此时子串中只有一个字符，所以该子串可以自成一个回文串，所以使其称为回文串的最少插入次数为 0 ，即 dp[i][i] == 0

  • 确定遍历顺序

这道题的遍历顺序与最长回文子序列一般，由于 dp[i][j] 依赖于下一行的数据，所以对于外层行遍历来说，我们需要从尾到头遍历，保证我们需要的结果（i + 1 行的数据）都是已经计算出来的。

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
public int minInsertions(String s) {
    int len = s.length();
    if (len == 0 || len == 1) return 0;
    // 创建一个 dp 数组
    int[][] dp = new int[len][len];
    // 初始化 dp 数组
    for (int i = 0;i < len;i++) {
        dp[i][i] = 0;
    }
    // 外层循环从尾到头遍历
    for (int i = len - 1;i >= 0;i--) {
        // 内层循环从头到尾遍历，j 需要严格大于 i，因为 i == j 的情况我们在初始化时已经考虑过了
        for (int j = i + 1;j < len;j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1];
            } else {
                // 这种情况下，我们需要进行选择
                dp[i][j] = Math.min(
                    Math.min(
                        // 选择一：先将子串 s[i + 1,j] 变为回文串，然后在该基础上 + 1
                        dp[i + 1][j] + 1, 
                        // 选择二：先将子串 s[i, j - 1] 变为回文串，然后在基础上  +1
                        dp[i][j - 1] + 1
                    ),
                    dp[i + 1][j - 1] + 2
                );
            }
        }
    }
    return dp[0][len - 1];
}

2.24、俄罗斯套娃信封问题

1、题目描述

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

  • 示例一
1
2
3
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
  • 示例二
1
2
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

2、解题思路

  • 对于这道题来说，我们可以将所给数组的元素进行排序，先将这些信封根据宽度进行从小到大排序，对于宽度相等的信封，根据高度从大到小排序，比如说，对于示例一给的例子，在经过排序后，得到的顺序如下

image.png

  • 求 h 数组的最长递增子序列长度 maxLength，得到的结果就是本题的结果

因为两个 w 相同的信封不能相互包含，所以在 w 相同时，我们将这些信封按照 h 从大到小排序，确保最多只有一个信封被选入到最长递增子序列中，这保证了最终的信封序列中不会出现多个 w 相同的信封

3、解题代码

  • 将传入的信封数组按照 w 从小到大进行排序，对于 w 相同的信封，根据 h 从大到小排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maxEnvelopes(int[][] envelopes) {
    if (envelopes.length == 0) return 0;
    // 对传入的信封数组进行排序，先根据 w 进行升序排序，对于 w 相等的元素，根据 h 进行降序排序
    Arrays.sort(envelopes, (envelopes1, envelopes2) -> envelopes1[0] == envelopes2[0] ? envelopes2[1] - envelopes1[1] : envelopes1[0] - envelopes2[0]);
    // 将所有信封的 h 看为一个数组，求这个数组的最长递增子序列长度
    // 创建一个 dp 数组
    int[] dp = new int[envelopes.length];
    // 初始化 dp 数组
    for (int i = 0;i < envelopes.length;i++) {
        dp[i] = 1;
    }
    // 使用一个变量来保存最长递增子序列长度，初始化为 1 
    int maxLength = 1;
    for (int i = 0;i < envelopes.length;i++) {
        for (int j = 0;j < i;j++) {
            if (envelopes[j][1] < envelopes[i][1]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
            maxLength = Math.max(dp[i], maxLength);
        }
    }
    return maxLength;
}

2.25、正则表达式匹配

1、题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  1. '.' 匹配任意单个字符
  2. '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

  • 示例一
1
2
3
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
  • 示例二
1
2
3
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

2、解题思路

  • 对于 * ，我们需要将它与 * 号的前一个字符 x 看为一个整体，它表示可以匹配零个或者多个 x ，比如说 a* 可以匹配 0 个或者多个 a

使用递归解决这道题

  • 编写一个递归函数 boolean process(char[] str, int si, char[] pattern, int pi) ，这个函数表示的含义为：字符串 str[si, str.length - 1] 能否被字符串 pattern[pi, pattern.length - 1] 完全匹配
  • 编写 process 函数，我们需要保证传入的 pi 下标对应的字符不是 *
  1. base case 1，当 si == str.length 时，此时 str 表示的字符串为空串 “” ，这种情况下，如果 pi == length 或者 pattern 字符串剩下的子串可以与 “” 进行匹配，那么返回 true

如何表示 pattern 字符串剩下的子串可以与 “” 进行匹配呢，即 pattern[pi] != “*“ && pattern[pi + 1] == “*“ && process(str, str.length, pattern, pi + 2)

比如说，如果此时 pattern 剩下的字符串为 a*b*c* 时，就可以与空串进行匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 如果 si == str.length ，那么证明此时进行完全匹配的字符串 str 已经变为一个空串
if (si == str.length) {
    // 此时有两种情况可以返回 true
    // 第一种，此时 pattern 也为一个空串
    if (pi == pattern.length) {
        return true;
    }
    // 第二种，pattern[pi] 不为 * 且 pattern[pi + 1] 为 *
    // 同时 pattern [pi + 2,...] 可以与空串进行匹配
    if (pi + 1 < pattern.length && pattern[pi + 1] == '*') {
        return process(str, si, pattern, pi  +2);
    }
    // 如果无法满足上面的条件，那么直接返回 false
    return false;
}
  1. base case 2 ，当 pi == pattern.length 时，此时 pattern 已经为空串，那么此刻只有 s 为空串时，二者才能进行匹配
  2. 当 si 与 pi 都没有到达最终位置时，此时又可以分为多种情况进行讨论
    1. 如果 pi + 1 位置对应的字符不是 * ，那么有两种情况可以完全匹配成功，第一种就是 str[si] == pattern[pi] 且 后面的字符串可以完全匹配；第二种就是 pattern[pi] == '.' 且后面的字符串可以完全匹配
    2. 如果 pi + 1 位置对应的字符是 * 且 str[si] != pattern[pi] ，那么此时只能让 pattern[pi]* 变为 0 个 pattern[pi]，且需要满足 str[si] 及之后的字符串可以与 pattern[pi + 2] 及之后的字符串完全匹配
    3. 当 pi + 1 位置对应的字符是 * 且 str[si] == pattern[pi] 时 ，此时就算 str[si] == pattern[pi] ，pattern[pi] * 也可能变为 0 个 pattern[pi]
    4. 接下来我们就要判断 pattern[pi]* 变为一个 pattern[pi]、多个 pattern[pi] 的情况了

使用动态规划解决这道题

  • 对于上面的 process 函数中，只有两个可变参数，即 si 与 pi ，当这两个参数确定后，得到的值（返回值）也就确定了，所以我们可以以 pi 为行， si 为列，以结果为值，将三者映射到一张二维表中
  • 确定 dp 数组的含义

其中 dp[i][j] 表示字符串 str[i, ...] 与 pattern[j, ...] 是否可以进行完全匹配

  1. dp[i][j] == -1 ，表示 str[i, ...] 与 pattern[j, ...] 的匹配结果没有计算过
  2. dp[i][j] == 0 ，表示 str[i, ...] 与 pattern[j, ...] 的匹配结果已经计算过了，且返回值为 false
  3. dp[i][j] == 1 ，表示 str[i, ...] 与 pattern[j, ...] 的匹配结果已经计算过了，且返回值为 true
  • 初始化 dp 数组，根据上面我们提到的 dp 数组的含义，我们需要将 dp 数组中所有的元素都初始化为 -1
  • 在进行递归的过程中，我们需要将这张缓存表一起放入到递归函数中，然后对这张表进行存取
  1. 在进行递归时，如果发现当前参数对应的值已经在缓存中出现（dp[i][j] != -1），那么不用计算，直接返回表中的值

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public boolean isMatch(String s, String p) {
    if (s == null || p == null) return false;
    char[] str = s.toCharArray();
    char[] pattern = p.toCharArray();
    return process(str, 0, pattern, 0);
}

/**
 * 判断 str[si, str.length - 1] 的子串能否被 pattern[pi, pattern.length - 1] 完全匹配
 */
public boolean process(char[] str, int si, char[] pattern, int pi) {
    // 如果 si == str.length ，那么证明此时进行完全匹配的字符串 str 已经变为一个空串
    if (si == str.length) {
        // 此时有两种情况可以返回 true
        // 第一种，此时 pattern 也为一个空串
        if (pi == pattern.length) {
            return true;
        }
        // 第二种，pattern[pi] 不为 * 且 pattern[pi + 1] 为 *
        // 同时 pattern [pi + 2,...] 可以与空串进行匹配
        if (pi + 1 < pattern.length && pattern[pi + 1] == '*') {
            return process(str, si, pattern, pi  +2);
        }
        // 如果无法满足上面的条件，那么直接返回 false
        return false;
    }
    // base case 2 ，当 pi == pattern.length 时，此时 pattern 已经为空串，那么此刻只有 s 为空串时，二者才能进行匹配
    if (pi == pattern.length) {
        return si == str.length;
    }
    // si 没有终止，pi 也没有终止
    //1 当 pi + 1 位置对应的字符不是 * 时
    if (pi + 1 >= pattern.length || pattern[pi + 1] != '*') {
        // 如果 si 对应的字符和 pi 对应的字符相等，或者 pi 对应的字符为 . ，且 si + 1 后的字符串可以与 pi + 1 后的字符串进行匹配，那么返回 true ，否则返回false
        return ((str[si] == pattern[pi]) || (pattern[pi] == '.')) && process(str, si + 1, pattern, pi + 1);
    }
    //2 当 pi + 1 位置对应的字符是 * 且 str[si] != pattern[pi] 时，此时只能让 pattern[pi]* 变为 0 个 pattern[pi]
    if (pattern[pi] != '.' && str[si] != pattern[pi]) {
        return process(str, si, pattern, pi + 2);
    }
    //3 当 pi + 1 位置对应的字符是 * 且 str[si] == pattern[pi] 时，
    // 此时就算 str[si] == pattern[pi] ，pattern[pi] * 也可能变为 0 个 pattern[pi]
    if (process(str, si, pattern, pi + 2)) {
        return true;
    }
    // 往下，我们判断 pattern[pi]* 变为一个或者多个 pattern[pi] 的情况
    while (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')) {
        if (process(str, si + 1, pattern, pi + 2)) {
            return true;
        }
        si++;
    }
    // 否则直接返回 false
    return false;
}

动态规划

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
public boolean isMatch(String s, String p) {
    if (s == null || p == null) return false;
    char[] str = s.toCharArray();
    char[] pattern = p.toCharArray();
    int[][] dp = new int[str.length + 1][pattern.length + 1];
    for (int i = 0;i <= str.length;i++) {
        for (int j = 0;j <= pattern.length;j++) {
            dp[i][j] = -1;
        }
    }
    return process(str, 0, pattern, 0, dp);
}

/**
 * 判断 str[si, str.length - 1] 的子串能否被 pattern[pi, pattern.length - 1] 完全匹配
 */
public boolean process(char[] str, int si, char[] pattern, int pi, int[][] dp) {
    // 先查找缓存是否已经计算过，如果不等于 -1 ，那么证明计算过
    if (dp[si][pi] != -1) {
        return dp[si][pi] == 1;
    }
    // 下面，在我们进行返回前，需要将值存入缓存中然后再返回
    // 如果 si == str.length ，那么证明此时进行完全匹配的字符串 str 已经变为一个空串
    if (si == str.length) {
        // 此时有两种情况可以返回 true
        // 第一种，此时 pattern 也为一个空串
        if (pi == pattern.length) {
            dp[si][pi] = 1;
            return true;
        }
        // 第二种，pattern[pi] 不为 * 且 pattern[pi + 1] 为 *
        // 同时 pattern [pi + 2,...] 可以与空串进行匹配
        if (pi + 1 < pattern.length && pattern[pi + 1] == '*') {
            boolean result = process(str, si, pattern, pi  +2, dp);
            dp[si][pi] = result ? 1 : 0;
            return result;
        }
        // 如果无法满足上面的条件，那么直接返回 false
        dp[si][pi] = 0;
        return false;
    }
    // base case 2 ，当 pi == pattern.length 时，此时 pattern 已经为空串，那么此刻只有 s 为空串时，二者才能进行匹配
    if (pi == pattern.length) {
        boolean result = si == str.length;
        dp[si][pi] = result ? 1 : 0;
        return result;
    }
    // si 没有终止，pi 也没有终止
    //1 当 pi + 1 位置对应的字符不是 * 时
    if (pi + 1 >= pattern.length || pattern[pi + 1] != '*') {
        // 如果 si 对应的字符和 pi 对应的字符相等，或者 pi 对应的字符为 . ，且 si + 1 后的字符串可以与 pi + 1 后的字符串进行匹配，那么返回 true ，否则返回false
        boolean result = ((str[si] == pattern[pi]) || (pattern[pi] == '.')) && process(str, si + 1, pattern, pi + 1, dp);
        dp[si][pi] = result ? 1 : 0;
        return result;
    }
    //2 当 pi + 1 位置对应的字符是 * 且 str[si] != pattern[pi] 时，此时只能让 pattern[pi]* 变为 0 个 pattern[pi]
    if (pattern[pi] != '.' && str[si] != pattern[pi]) {
        boolean result = process(str, si, pattern, pi + 2, dp);
        dp[si][pi] = result ? 1 : 0;
        return result;
    }
    //3 当 pi + 1 位置对应的字符是 * 且 str[si] == pattern[pi] 时，
    // 此时就算 str[si] == pattern[pi] ，pattern[pi] * 也可能变为 0 个 pattern[pi]
    if (process(str, si, pattern, pi + 2, dp)) {
        dp[si][pi] = 1;
        return true;
    }
    // 往下，我们判断 pattern[pi]* 变为一个或者多个 pattern[pi] 的情况
    while (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')) {
        if (process(str, si + 1, pattern, pi + 2, dp)) {
            dp[si][pi] = 1;
            return true;
        }
        si++;
    }
    // 否则直接返回 false
    dp[si][pi] = 0;
    return false;
}

2.26、礼物的最大价值

1、题目描述

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

  • 示例
1
2
3
4
5
6
7
8
输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

2、解题思路

  • 确定 dp 数组的含义

其中 dp[i][j] 表示到达棋盘上的 [i , j] 位置时，所能拿到的礼物的总价值

  • 状态转移方程

对于棋盘上的某个位置 (i, j) 来说 ，它的状态可以由两个状态得来，即它的上方元素 （i - 1,j） 和左边元素 （i, j - 1） 得到，同时还需要加上当前位置礼物的价值 nums[i][j] ，我们需要在上面的选择中取较大值。

1
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + nums[i][j];
  • 初始化 dp 数组

我们需要初始化第一行和第一列的元素

  1. 其中第一行的元素为 nums[0,i] 上的元素累加值，比如说，在例子中， dp[0][0] 应该初始化为 nums[0][0] ，dp[0][1] 应该初始化为 nums[0][0] + nums[0][1] ，dp[0][2] = nums[0][0] + nums[0][1] + nums[0][2]
  2. 同理，第一列的元素也应该按照上面的规则初始化，只不过变为向下累加。
  • 遍历顺序

这道题是最常规的动态规划问题，我们只需要按照从头到尾的顺序进行遍历即可，可以看到 dp[i][j] 是由上一行、前一列的元素推导出来的。

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
   public int maxValue(int[][] grid) {
       if (grid == null || grid.length == 0) return 0;
       int row = grid.length;
       int column = grid[0].length;
       int[][] dp = new int[row][column];
       int value = 0;
// 初始化 dp 数组
       for (int i = 0;i < row;i++) {
           value += grid[i][0];
           dp[i][0] = value;
       }
       value = 0;
       for (int j = 0;j < column;j++) {
           value += grid[0][j];
           dp[0][j] = value;
       }
       for (int i = 1;i < row;i++) {
           for (int j = 1;j < column;j++) {
               dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
           }
       }
       return dp[row - 1][column - 1];
   }

2.27、最长不含重复字符的子字符串

1、题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

  • 示例一
1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
  • 示例二
1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

2、解题思路

  • 明确 dp 数组的含义

其中 dp[i] 表示以字符 s.charAt(i) 结尾的最长不含重复字符的子字符串的长度。

  • 明确状态转移方程

对于 i 位置的字符 x 来说，我们需要找到 x 在 s 中的上一个位置 index ，然后根据 index 来判断下一步该如何选择

  1. 如果 index == -1 ，此时代表 x 字符串在 [0, i - 1] 位置内不曾出现，那么 x 字符可以加入到以 i - 1 字符为结尾的最长不含重复字符的子字符串中，即此时有 dp[i] = dp[i - 1] + 1 ，比如说当前字符串为 abcde ，此时 e 为 x ，e 未曾在之前的字符串中出现，那么将其加入到以 d 结尾的子字符串中，不会打破原来的不重复规则。
  2. 如果找到了一个不为 -1 的 index ，那么证明 x 字符在 [0, i - 1] 位置内出现过，如果
    1. dp[i - 1] < i - index ，此时说明字符 s[index] 在子字符串 dp[i - 1] 区间之外，此时将 s[i] 加入到以 s[i - 1] 为结尾的最长不重复子串中，不会破坏规则，此时 dp[i] = dp[i - 1] + 1 ，比如说对于字符串 axxbcda 中，s[i] = 'a' ，而前一个 'a' 出现在 dp[i - 1] 的最长不重复子串之外，所以将 s[i] 加入到 s[i - 1] 结尾的最长不重复子串中不会破坏规则
    2. dp[i - 1] >= i - index ，说明字符串 s[index] 在子字符串 dp[i - 1] 的区间之内，所以此时以 s[i] 为结尾的最长不重复子串的长度由 s[index] 中 index 的位置决定，即 dp[i] = i - index
  • 我们使用一个 Map 来保存字符 s[i] 的上一个出现位置，如果不存在，那么返回 -1 ，在循环过程中，需要更新这个 Map

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) return 0;
    Map<Character, Integer> memo = new HashMap<>();
    // 由于 dp[i] 只与前一个状态 dp[i - 1] 有关，所以使用一个变量进行滚动
    int temp = 0, result = 0;
    for (int i = 0;i < s.length();i++) {
        // 如果没有对应的 key ，那么返回 -1
        int index = memo.getOrDefault(s.charAt(i), -1);
        // 更新 map 
        memo.put(s.charAt(i), i);
        temp = temp < i - index ? temp + 1 : i - index;
        result = Math.max(temp, result);
    }
    return result;
}

2.28、把数字翻译成字符串

1、题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

  • 示例一
1
2
3
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

2、解题思路

  • 使用动态规划解决这道题
  • 明确 dp 数组的含义

**我们设 **dp[i] 的含义为：下标范围为 [0, i] 的那部分数字有 dp[i] 种翻译方法

  • 明确状态转移方程

**对于 **dp[i] 而言，我们需要进行分类讨论

  1. 当数字中的最后两个数字，即 [i - 1, i] 范围的数字可以被翻译为一个数时，0 =< (i - 1) * 10 + i <= 25 时，那么我们有两种选择，我们即可以直接将最后一个数字翻译为一个字母，此时存在等式 dp[i] = dp[i - 1] ；又可以将最后两个数字直接翻译成一个字母，此时存在等式 dp[i] = dp[i - 2]

**情况 1 需要综合两个选择进行考虑，所以这种情况下 **dp[i] = dp[i - 1] + dp[i - 2]

image-20211207133422850

  1. **当数字中的最后两个数字无法直接被翻译为一个数时，此时我们别无选择，只有将最后一个数直接翻译成一个字母，此时存在等式 **dp[i] = dp[i - 1]

image-20211207133456609

故我们可以得到以下的状态转移方程

1
2
3
4
5
if (最后两个数可以翻译为一个字母) {
    dp[i] = dp[i - 1] + dp[i - 2];
} else {
    dp[i] = dp[i - 1];
}
  • 数组初始化，对于第一个数字，我们只有将它直接转换为一个字母，此时 dp[0] = 1

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    public int translateNum(int num) {
        //1 先将 num 转换为字符串
        String str = String.valueOf(num);
        // 创建一个 dp 数组，长度为 str.length()
        int[] dp = new int[str.length()];
        // 初始化 dp 数组
        dp[0] = 1;
        // 从 1 开始
        for (int i = 1;i < str.length();i++) {
            // 如果前一个数等于 1 ，或者前一个数等于 2 且当前数小于等于 5 
            if (str.charAt(i - 1) == '1' || (str.charAt(i - 1) == '2' && str.charAt(i) <= '5')) {
                if (i == 1) {
                    // 如果 i == 1，那么直接初始化为 2 
                    dp[i] = 2;
                } else {
                    dp[i] = dp[i - 2] + dp[i - 1];
                }
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[str.length() - 1];
    }

2.29、删除并获得点数

1、题目描述

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

  • 示例一
1
2
3
4
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。
  • 示例二
1
2
3
4
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。总共获得 9 个点数。

2、解题思路

这道题与打家劫舍的思路差不多，如果我们在原来数组的基础上构造一个新数组，这个数组以 元素的值为下标，nums[i] 表示 i 出现的次数，以示例二的数组为例，构造出来的新数组为：

1
2
nums = {2,2,3,3,3,4}
temp = {0,0,2,3,1}

代表原来的数组中有 0 个 0 ，0 个 1 ，2 个 2 ，3 个 3 ，一个 4

这样就变成了打家劫舍问题。

  • dp 数组的含义

其中 dp[i] 表示面对值为 i 的数时，能获得的最大点数为 dp[i]

  • 状态转移方程

和打家劫舍一样，我们在选择值为 i 的数时，不需要考虑 i + 1 的数，只需要考虑 i - 1 的情况，此时 dp[i] 有两个选择

  1. 第一个选择就是选择获取 i - 1 的点数，此时 i 的点数已经不能选择（因为 i 的值），所以此时有式子为 dp[i] = dp[i - 1]
  2. 第二个选择就是选择获取 i - 2 的点数，此时可以选择 i 的点数，此时存在式子 dp[i] = dp[i - 2] + i * temp[i]

所以状态转移方程如下

1
dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * temp[i]);
  • 数组初始化

和打家劫舍的 dp 数组初始化一样，但注意这里需要对构造出来的新数组进行初始化

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
public int deleteAndEarn(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    //1 先找出数组中的最大数，用于构造新数组
    int max = Integer.MIN_VALUE;
    for (int num : nums) {
        max = Math.max(max, num);
    }
    if (max <= 0) return 0;
    // 必须是最大值 + 1 长度
    int[] temp = new int[max + 1];
    for (int num : nums) {
        temp[num]++;
    }
    // 接下来，就按照打家劫舍的方法做
    if (temp.length == 1) return temp[0];
    if (temp.length == 2) return Math.max(temp[0], temp[1]);
    int one = temp[0];
    int two = Math.max(temp[0], temp[1]);
    int cur = 0;
    for (int i = 2;i < temp.length;i++) {
        cur = Math.max(two, one + i * temp[i]);
        one = two;
        two = cur;
    }
    return cur;
}

2.30、接雨水

1、题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

2、解题思路

  • dp 数组的含义，其中 dp[i] 表示在下标为 i 的柱子上可以装的水

我们设第 i 根柱子左边最高的柱子高度为 maxLeft， 同时记第 i 根柱子右边最高的柱子高度为 maxRight ，则第 i 根柱子上能承载的水量为

1
dp[i] = Math.max(0, Math.min(maxLeft, maxRight) - height[i])

如果我们每次都需要向左右两边遍历找寻最大值，那么时间复杂度就会非常高。

创建两个长度为 n 的数组 leftMax 和 rightMax ， 对于 0 <= i < n ，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度；而 rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。

  1. leftMax[0] = height[0] ， rightMax[n - 1] = height[n - 1]

  2. 当 1 <= i <= n - 1 时，leftMax[i] = Math.max(leftMax[i - 1], height[i])

  3. 当 0 <= i <= n - 2 时，rightMax[i] = Math.max(rightMax[i - 1], height[i])

因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值，反向遍历数组 height 得到数组 rightMax 的每个元素值。

这道题中，我们不需要使用到 dp 数组，只需要使用一个变量进行保存同时累加即可。

  • 状态转移方程

我们设在第 i 根柱子上能存的水为 count ，则

1
int count = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i])

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int trap(int[] height) {
    if (height == null || height.length <= 2) return 0;
    int[] leftMax = new int[height.length];
    leftMax[0] = height[0];
    // 正向遍历，获取每根柱子左边的最大高度
    for (int i = 1;i < height.length;i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }
    int[] rightMax = new int[height.length];
    // 反向遍历，获取每根柱子右边的最大高度
    rightMax[height.length - 1] = height[height.length - 1];
    for (int i = height.length - 2;i >= 0;i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }
    // 使用一个变量来计算总水量
    int sum = 0;
    // 第一根和最后一根柱子没有结果，直接跳过
    for (int i = 1;i < height.length - 1;i++) {
        int count = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
        sum += count;
    }
    return sum;
}

2.31、丑数 II

1、题目描述

给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是只包含质因数 2、3 和/或 5 的正整数。（1 也可以看为一个丑数）

  • 示例
1
2
3
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
  • 丑数计算思路

由于 1 也是丑数，那么我们可以将 1 作为基础乘以 2,3,5 ，得到的结果也是丑数，再将这些得到的结果分别乘以 2,3,5 ，得到的结果也都是丑数，然后按照从小到大取到第 n 个结果，就是第 n 个丑数

image-20211211214928486

2、解题思路

  • 使用最小堆

在这个解决思路中，我们需要创建一个小顶堆和一个集合，其中集合用于取出重复的丑数，比如说上图中生成的丑数存在相同的情况，我们需要进行去重。

  1. 初始化时，最小堆中只存在丑数 1
  2. 循环遍历，将 1 从最小堆中取出，然后将 1 乘以三个质因子，然后将结果放入最小堆中（需要先到集合中看一下有没有这个元素，如果有那么就不加入到最小堆中）

不断从堆中取出元素，然后乘以质因子，再将没出现过的结果放入到最小堆中，循环 n 次，拿到的就是第 n 个丑数。

  • 动态规划
  1. dp 数组的含义

其中 dp[i] 表示第 i 个丑数的值，则第 n 个丑数即为 dp[n]

  1. 状态转移方程

定义三个指针 p2,p3,p5 ，表示下一个丑数是当前指针指向的丑数乘以对应的质因子。初始化时，三个指针的值均为 1 ，当 2 <= i <= n 时，有

1
dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3),dp[p5] * 5);

然后我们需要比较 dp[i] 与 dp[p2] * 2 ，dp[p3] * 3 ，dp[p5] * 5 是否相等，如果相等则将对应的指针 + 1

从上面的图中，当求第二个丑数时，结果从 {2,3,5} 中 诞生，我们得到第二个丑数为 2 ，求第三个丑数时，我们在{3,5,4} 中求结果，可以看到 {3,5} 是上次求丑数留下来的结果，而 4 正是 2 * 2 ，即 1 后移（ + 1）后 * 2 的结果

  1. dp 数组初始化

dp[1] 表示第一个丑数，初始化为 1

3、解题代码

  • 最小堆

这里为了防止溢出，使用的是 Long 型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int nthUglyNumber(int n) {
    if (n == 1) return 1;
    // 创建一个最小堆，用于存放丑数
    PriorityQueue<Long> minHeap = new PriorityQueue<>();
    // 创建一个数组，用于存放质因子。
    int[] nums = {2, 3, 5};
    Set<Long> set = new HashSet<>();
    // 初始化，我们需要将 1 放入最小堆中
    minHeap.add(1L);
    long result = 0;
    for (int i = 0;i < n;i++) {
        result = minHeap.poll();
        for (int num : nums) {
            long uglyNum = num * result;
            // 只有集合中不存在时，才将结果加入到最小堆中
            if (!set.contains(uglyNum)) {
                minHeap.add(uglyNum);
                set.add(uglyNum);
            }
        }
    }
    return (int)result;
}
  • 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int nthUglyNumber(int n) {
    if (n == 1) return 1;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1;
    for (int i = 2;i <= n;i++) {
        dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);
        if (dp[i] == dp[p2] * 2) {
            p2++;
        }
        if (dp[i] == dp[p3] * 3) {
            p3++;
        }
        if (dp[i] == dp[p5] * 5) {
            p5++;
        }
    }
    return dp[n];
}

2.32、跳跃游戏 I

1、题目描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

2、解题思路

  • dp 数组的含义

其中 dp[i] 表示能否到达下标为 i 的位置，所以 dp 应该是一个 boolean 类型的数组

  • 状态转移方程

遍历 [0, i - 1] ，我们需要找到一个位置 j ，如果小人能到达 j 位置且满足条件 j + nums[j] >= i，那么证明 i 是可以到达的，此时我们可以使 dp[i] = true ，然后我们需要跳出循环

1
2
3
if(dp[j] && j + nums[j] > i) {
	dp[i] = true;
}
  • dp 数组的初始化

我们需要初始化 dp[0] = true，因为小人从 0 位置开始，同时需要返回 dp[nums.length - 1]

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean canJump(int[] nums) {
    if (nums == null || nums.length <= 1) return true;
    boolean[] dp = new boolean[nums.length];
    dp[0] = true;
    for (int i = 1;i < nums.length;i++) {
        for (int j = 0;j < i;j++) {
            if (dp[j] && nums[j] + j >= i) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[nums.length - 1];
}

2.33、跳跃游戏 II

1、题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

  • 示例
1
2
3
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

2、解题思路

  • dp 数组的含义

其中 dp[i] 表示到达 i 位置所用的最小步数，我们需要返回 dp[nums.length - 1]

  • 状态转移方程

当我们处于第 i 个位置时，我们遍历 [0. i - 1] 位置，然后寻找在哪个位置可以直接用一步到达 i 位置。

1
2
3
4
if (j + nums[j] >= i) {
    // 如果在 j 位置可以直接到达 i 位置，那么直接在到达 j 所需要的最少步数 dp[j] 的基础上 + 1即可，但我们需要和 dp[i] 做比较，取最小值
    dp[i] = Math.min(dp[i], dp[j] + 1);
}
  • 初始化 dp 数组

由于在状体转移方程中，我们需要使用 min 函数来选择最小值，那么我们给数组的初始化值就不能是简单的 0 ，为了方便，我们先将数组中的所有元素全部置为 Integer,MAX_VALUE

  1. 当 i 为 0 时，我们只需要 0 步就可以到达，所以 dp[0] = 0
  2. 当 i 为 1 时，我们只需要一步就可以到达，所以 dp[1] = 1

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int jump(int[] nums) {
    int len = nums.length;
    if (len <= 1) return 0;

    // 创建一个大小为 len 的数组，并对它的值进行初始化
    int[] dp = new int[len];
    // 初始化数组的值为 Integer.MAX_VALUE ，因为我们需要与 0 作比较取最小值，所以要初始化一个值
    Arrays.fill(dp, Integer.MAX_VALUE);
    // 初始化 dp[0] 和 dp[1] ，当 i 等于 0 时，至少花 0 步就可以到达，当 i 等于 1 时，只需要一步就可以到达 1 
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2;i < len;i++) {
        for (int j = 0;j < i;j++) {
            // 如果在 [0, i - 1] 范围内有位置可以一步到达 i ，那么我们需要进行选择，
            if (j + nums[j] >= i) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[len - 1];
}

2.34、环形子数组的最大和

1、题目描述

给定一个由整数数组 A 表示的**环形数组 C**，求 C 的非空子数组的最大可能和。

在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）

此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], …, C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）

  • 示例一
1
2
3
输入：[1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
  • 示例二
1
2
3
输入：[5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
  • 示例三
1
2
3
输入：[3,-1,2,-1]
输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4

2、解题思路

  • 对于一个环形数组来说，它的最大连续子数组其实只有两种情况
  1. 第一种，最大连续子数组分布在数组中间，比如说下面的情况

对于这种情况，我们只需要按照求普通数组的最大连续子数组的和的思路做即可。

image-20211213221450727

  1. 第二种，最大连续子数组首尾相连，比如说下面的情况

这种情况下，我们要求的值 answer 满足 answer = totalSum - min_so_far，其中 min_so_far 表示图中灰色部分的和，即普通数组中最小连续子数组的和，我们可以借由最大连续子数组的和来做。

image-20211213221549112

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
34
35
36
37
38
39
40
41
42
43
public int maxSubarraySumCircular(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int first = maxSubarray(nums);
    int total = 0;
    // 计算 total 的值
    for (int num : nums) {
        total += num;
    }
    int min = minSubarray(nums);
    int second = total - min;
    // 如果 total 等于 min ，那么证明差为 0 ，那么此时如果 first 返回的值是负数，那么就会返回错误的 0 
    if (total == min) return first;
    return Math.max(first, second);
}


private int minSubarray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int len = nums.length;
    int[] dp = new int[len];
    dp[0] = nums[0];
    int min = Integer.MAX_VALUE;
    for (int i = 1;i < len;i++) {
        dp[i] = Math.min(dp[i - 1] + nums[i], nums[i]);
        min = Math.min(dp[i], min);
    }
    return min;
}

private int maxSubarray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int len = nums.length;
    int[] dp = new int[len];
    int max = Integer.MIN_VALUE;
    dp[0] = nums[0];
    for (int i = 1;i < len;i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        max = Math.max(dp[i], max);
    }
    return max;
}

2.35、乘积最大子数组

1、题目描述

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

  • 示例一
1
2
3
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
  • 示例二
1
2
3
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

2、解题思路

  • 与和最大子数组不一样的是，在本题中，我们需要根据当前遍历的元素来进行更新 dp 数组的值，我们设置两个变量，其中 preMax 为 nums[0: i - 1] 中最大的乘积，而 preMin 为 nums[0: i - 1] 中最小的乘积（可能为负数）
  • 当 nums[i] 为正数时，此时由于正正得正，我们需要更新 preMax = Math.max(preMax * nums[i], nums[i])，同时更新 preMin = Math.min(preMax * nums[i], nums[i])
  • 当 nums[i] 为负数时，此时由于负负为正得正，我们需要更新 preMax = Math.max(preMin * nums[i], nums[i])，同时更新 preMin = Math.min(preMin * nums[i], nums[i])

我们使用一个 max 变量来记录全局最大值，将其与 preMax 比较

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int preMax = nums[0], preMin = nums[0], max = nums[0];
    int curMax = 0, curMin = 0;
    for (int i = 1;i < nums.length;i++) {
        if (nums[i] > 0) {
            curMax = preMax * nums[i];
            curMin = preMin * nums[i];
        } else {
            curMax = preMin * nums[i];
            curMin = preMax * nums[i];
        }
        preMax = Math.max(curMax, nums[i]);
        preMin = Math.min(curMin, nums[i]);
        max = Math.max(preMax, max);
    }
    return max;
}

2.36、乘积为正数的最长子数组长度

1、题目描述

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。

一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组，请你返回乘积为正数的最长子数组长度。

  • 示例一
1
2
3
输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。
  • 示例二
1
2
3
输入：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。

2、解题思路

  • 与上一题相同，我们在遍历到某个元素时，根据这个元素的情况进行判断
  • 确定 dp 数组的含义

我们需要创建两个数组，其中

  1. pos[i] 表示以 i 结尾的乘积为正数的最长子数组长度
  2. neg[i] 表示以 i 结尾的乘积为负数的最长子数组长度
  • 状态转移方程
  1. 当 nums[i] > 0 时，此时 nums[i] 的值不会影响之前子数组乘积的值的正负

所以，如果 pos[i - 1] 大于 0 ，那么此时它可以放心乘上 nums[i] ，如果 pos[i - 1] 等于 0 ，那么子数组 {nums[i]} 就是以 i 结尾的乘积为正数的最长子数组，即此时 pos[i] = 1，所以我们可以直接列出当 nums[i] 大于 0 的状态转移方程；

而如果 neg[i - 1] 大于 0 ，那么它也可以放心乘上 nums[i]，如果 neg[i - 1] 等于 0，那么 neg[i ] 依然为 0

1
2
3
4
if (nums[i] > 0) {
    pos[i] = pos[i - 1] + 1;
    neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
}
  1. 当 nums[i] < 0 时，此时 nums[i] 的值会影响之前子数组乘积的值的正负

如果 pos[i - 1] 大于 0，那么此时我们将 nums[i] 放入以 i - 1 结尾的子数组中，整个子数组的乘积变为了负数，所以此时有 neg[i] = pos[i - 1] + 1；如果 pos[i - 1] 等于 0 ，那么此时如果我们将 nums[i] 放入以 i - 1 结尾的子数组中，可能会导致整个子数组乘积变为正，所以此时我们直接记 neg[i] 为 1 ；

如果 neg[i - 1] 大于 0，那么此时将 nums[i] 放入以 i - 1 结尾的子数组中，整个子数组的乘积变为了正数，所以此时 pos[i] 的值应该更新为 neg[i - 1] + 1 ，如果 neg[i - 1] 的值等于 0 ，那么应该将 pos[i] 置为 0

1
2
3
4
if (nums[i] < 0) {
    neg[i] = pos[i - 1] + 1;
    pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
}

所以，我们可以得出状态转移方程如下：

1
2
3
4
5
6
7
8
9
if (nums[i] > 0) {
    pos[i] = pos[i - 1] + 1;
    neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
} else if (nums[i] == 0) {
    pos[i] = neg[i] = 0;
} else {
    neg[i] = pos[i - 1] + 1;
    pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
}
  • dp 数组的初始化

这个需要根据 nums[0] 的值进行判断

  1. 当 nums[0] 大于 0 时， pos[0] = 1，neg[0] = 0
  2. 当 nums[0] 等于 0 时，直接初始化为 0
  3. 当 nums[0] 小于 0 时，neg[0] = 1，pos[i] = 0

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
public int getMaxLen(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0] > 0 ? 1 : 0;
    int[] pos = new int[nums.length];
    int[] neg = new int[nums.length];
    int max = Integer.MIN_VALUE;
    if (nums[0] > 0) {
        pos[0] = 1;
    } else if (nums[0] < 0) {
        neg[0] = 1;
    }
    for (int i = 1;i < nums.length;i++) {
        if (nums[i] > 0) {
            pos[i] = pos[i - 1] + 1;
            neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
        } else if (nums[i] == 0) {
            pos[i] = 0;
            neg[i] = 0;
        } else {
            neg[i] = pos[i - 1] + 1;
            pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
        }
        max = Math.max(max, pos[i]);
    }
    return max;
}

由于在状态转移方程中， dp[i] 的值只与前一个状态相关，所以我们可以使用一个变量进行滚动更新

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
public int getMaxLen(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0] > 0 ? 1 : 0;
    int posMax = 0;
    int negMax = 0;
    int max = Integer.MIN_VALUE;
    if (nums[0] > 0) {
        posMax = 1;
    } else if (nums[0] < 0) {
        negMax = 1;
    }
    int curPos = 0;
    int curNeg = 0;
    for (int i = 1;i < nums.length;i++) {
        if (nums[i] > 0) {
            curPos = posMax + 1;
            curNeg = negMax > 0 ? negMax + 1 : 0;
        } else if (nums[i] == 0) {
            curPos = 0;
            curNeg = 0;
        } else {
            curNeg = posMax + 1;
            curPos = negMax > 0 ? negMax + 1 : 0;
        }
        // 进行滚动
        negMax = curNeg;
        posMax = curPos;
        max = Math.max(max, curPos);
    }
    return max;
}

2.37、最佳观光组合

1、题目描述

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

  • 示例一
1
2
3
输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
  • 示例二
1
2
输入：values = [1,2]
输出：2

2、解题思路

  • 当我们遍历到第 j 个元素时，由于此时我们知道 value[j] 与 j 的值，所以原题的值可以转换为求 [0, j - 1] 中最大的 value[i] + i 的值
  • 确定 dp 数组的含义

dp[i] 表示以 i 结尾的子数组中 value[i] + i 的最大值

  • 确定状态转移方程
1
dp[i] = Math.max(dp[i - 1], value[i] + 1);
  • 初始化 dp 数组，dp[0] = value[0] + 0 = value[0]

3、解题代码

  • 未优化前（这种解法会超时）
1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxScoreSightseeingPair(int[] values) {
    if (values == null || values.length == 0) return 0;
    int[] dp = new int[values.length];
    dp[0] = 0;
    int max = Integer.MIN_VALUE;
    for (int i = 1;i < values.length;i++) {
        for (int j = 0;j < i;j++) {
            dp[i] = Math.max(dp[i], values[i] + values[j] + j - i);
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}
  • 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
public int maxScoreSightseeingPair(int[] values) {
    if (values == null || values.length == 0) return 0;
    int[] dp = new int[values.length];
    dp[0] = values[0];
    int max = Integer.MIN_VALUE;
    for (int j = 1;j < values.length;j++) {
        dp[j] = Math.max(dp[j - 1], values[j] + j);
        // 更新结果的值，其中 dp[j - 1] 就是公式中 values[i] + i 的值
        max = Math.max(dp[j - 1] + values[j] - j, max);
    }
    return max;
}
  • 空间优化

由于 dp[i] 的值只与 dp[i - 1] 相关，所以可以使用一个变量进行滚动优化

1
2
3
4
5
6
7
8
9
10
11
public int maxScoreSightseeingPair(int[] values) {
    if (values == null || values.length <= 1) return 0;
    int preMax = values[0];
    int max = Integer.MIN_VALUE;
    for (int j = 1;j < values.length;j++) {
        int curMax = Math.max(preMax, values[j] + j);
        max = Math.max(preMax + values[j] - j, max);
        preMax = curMax;
    }
    return max;
}

2.38、单词划分

1、题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。

  • 示例一
1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
  • 示例二
1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

2、解题思路

对于一个字符串 s ，我们只考虑那些在 wordDict 中找得到前缀的那些分支，比如说，现在存在 wordDict = {a, aa, aab, b} ，s = "aaaabaab" ，此时对于 s 而言，如果我们考虑它的前缀为 a 时，此时由于前缀 a 存在于 wordDict 中，所以此时对 s 的分割就变为了 s 剔除掉前缀后剩下字符串的划分情况；同理，对于其他前缀也是如此

image-20211217221212365

  1. 以 a 作为前缀的分割情况有多少种，我们设 f(s, 0, s.length() - 1) 为 s 可被 wordDict 划分的种数，那么以 a 作为前缀就有 f(s, 1, s.length() - 1) 种分割情况
  2. 同理，我们可以得到合法前缀 aa 的分割种数，它的值为 f(s, 2, s.length() - 1)

所以，前缀为 prefix 的 s 字符串存在 f(s, prefix.length() + 1, s.length() - 1) 种分割方式

  • dp 数组的含义

dp[i] 表示 s[i, s.length() - 1] 可以被 wordDict 分割的种数

  • 状态转移方程

根据 dp[i] 的含义，我们可以得出 dp[i] 的计算方法，也就是找出 s[i, s.length() - 1] 的所有合法前缀，然后再通过计算各个合法前缀下剩下字符串的分割种数的总和，即：

1
dp[i] += dp[i + x]

其中 x 表示合法前缀长度

  • dp 数组的初始化

dp[s.length() - 1] 等于 1

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
public boolean wordBreak(String s, List<String> wordDict) {
    if (s == null || s.length() == 0 || "".equals(s)) return true;
    // 创建一个 dp 数组，其中 dp[i] 的值表示 s[index, s.length() - 1] 可被 wordDict 分解的种数
    int len = s.length();
    int[] dp = new int[len + 1];
    // 使用 set 来判断某个元素是否存在的效率要高于 List
    Set<String> wordSet = new HashSet<>(wordDict);
    // 初始化 dp 数组，其中 dp[s.length()] 的值为 1 
    dp[len] = 1;
    // 进行反向遍历，因为我们最后要得到的值是 dp[0] ，所以我们需要从后往前计算出 dp[0] 的值
    for (int i = len - 1;i >= 0;i--) {
        // 用于累加 dp[i] 的值，因为当前 s[i, len - 1] 的分割情况可能由多个前缀得到
        int ways = 0;
        for (int offset = i;offset < len;offset++) {
            // 如果前缀 s[i, offset] 存在于 wordSet 种，那么我们就可以继续计算下去，得到 s[i, len] 去除前缀 s[i, offset] 剩下子串的分割种数
            if (wordSet.contains(s.substring(i, offset + 1))) {
                ways += dp[offset + 1];
            }
        }
        // 在累加完成后，ways 中就是 dp [i] 的值
        dp[i] = ways;
    }
    // 最后返回结果，我们只需要判断 dp[0] 的值是否大于 0 即可
    return dp[0] > 0;
}

2.39、买卖股票的最佳时机含手续费

1、题目描述

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了，返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

  • 示例一
1
2
3
4
5
6
7
8
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
  • 示例二
1
2
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

2、解题思路

  • dp 数组的含义

创建一个长度为 prices.length ，宽度为 2 的数组，其中 dp[i][0] 表示在第 i 天持有股票的利润， dp[i][1] 表示在第 i 天没持有股票的利润。

  • 状态转移方程
  1. 第 i 天持有股票时， dp[i][0] 可以由两个状态推导出来，如果在 i - 1 天就持有股票，那么 dp[i][0] 的值就是昨天持有股票时的所得利润，即 dp[i][0] = dp[i - 1][0]；如果是在第 i 天买入股票，那么 dp[i][0] = dp[i - 1][0] - prices[i]
  2. 第 i 天没有股票， dp[i][1] 的值同样可以由两个状态推导出来，如果第 i - 1 天没有持有股票，那么 dp[i][1] = dp[i - 1][1]；同理，如果在 i - 1 天卖出股票，那么 dp[i][1] = dp[i - 1][0] + prices[i] - fee，在卖出的时候我们需要交出一份手续费。
  • dp 数组初始化

dp[0][0] = -prices[0]；

dp[0][1] = 0

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
public int maxProfit(int[] prices, int fee) {
    if (prices == null || prices.length <= 1) return 0;
    int len = prices.length;
    int[][] dp = new int[len][2];
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    for (int i = 1;i < len;i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
    }
    return dp[len - 1][1];
}

使用滚动数组进行优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProfit(int[] prices, int fee) {
    if (prices == null || prices.length <= 1) return 0;
    int len = prices.length;
    int[][] dp = new int[2][2];
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    for (int i = 1;i < len;i++) {
        dp[1][0] = Math.max(dp[0][0], dp[0][1] - prices[i]);
        dp[1][1] = Math.max(dp[0][1], dp[0][0] + prices[i] - fee);
        dp[0][0] = dp[1][0];
        dp[0][1] = dp[1][1];
    }
    return dp[1][1];
}

2.40、等差数列划分

1、题目描述

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数，子数组 是数组中的一个连续序列。

  • 示例
1
2
3
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

2、解题思路

  • 明确 dp 数组的含义

其中 dp[i] 表示以 nums[i] 为结尾的等差递增数列的个数，如果满足条件 nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ，那么 nums[i - 2]，nums[i - 1]，nums[i] 就可以构成一个等差递增数列，这表明，在以 nums[i - 1] 为结尾的等差递增数列后添加上一个 nums[i] ，那么一样可以构成一个最新的等差递增子数组

1
2
3
4
5
dp[2] = 1：
	[0, 1, 2]
dp[3] = dp[2] + 1
	[0, 1, 2, 3] // 在 [0, 1, 2] 后加上一个 3 
	[1, 2, 3] // 新的等差递增数列
  • 状态转移方程

对于一个以 nums[i - 1] 为结尾的等差递增数列来说，如果存在 nums[i] 满足nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]，那么存在以下状态转移关系

1
2
3
if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
    dp[i] = dp[i - 1] + 1;
}
  • 初始化 dp 数组

由于题目中要求等差递增数列的长度最少为 3 ，那么以 0 为结尾的等差递增数列的个数为 0 ，同理，以 1 为结尾的等差递增数列的个数为 0

  • 收集答案

在本题中，由于问的是等差递增数组的个数，所以我们需要收集以 i 为结尾的等差递增数列个数，其中 i 满足 0 <= i <= nums.length - 1

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int numberOfArithmeticSlices(int[] nums) {
    // base case
    if (nums == null || nums.length <= 2) return 0;
    int len = nums.length;
    // dp[i] 表示以 i 下标为结尾的等差递增数组的个数
    int[] dp = new int[len];
    int total = 0;
    // 初始化 dp 数组，dp[0] = dp[1] = 0;
    // 这里的下标从 2 开始，因为等差递增数组的长度要求至少为3 
    for (int i = 2;i < len;i++) {
        // 如果满足 nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ，那么我们就i找到了一个等差递增数列 {nums[i - 2], nums[i - 1], nums[i]}
        if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
            dp[i] = dp[i - 1] + 1;
        }
        // 进行答案收集，将以 i 下标为结尾的等差递增数组的个数收集到答案中
        total += dp[i];
    }
    return total;
}

使用滚动变量代替原来的一维数组，进行优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int numberOfArithmeticSlices(int[] nums) {
    if (nums == null || nums.length <= 2) return 0;
    int len = nums.length;
    int total = 0;
    // 使用一个 preNum 来表示 dp[i - 1]
    int preNum = 0;
    for (int i = 2;i < len;i++) {
        int curNum = 0;
        if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
            curNum = preNum + 1;
        }
        // 对b
        preNum = curNum;
        total += curNum;
    }
    return total;
}

2.41、解码方法

1、题目描述

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

  1. "AAJF" ，将消息分组为 (1 1 10 6)

  2. "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

  • 示例一
1
2
3
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
  • 示例二
1
2
3
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

2、解题思路

这道题的解题思路与 2.28 将数组翻译为字符串 一题的解题思路差不多，只不过只有当遍历到的字符不为 0 时，才能进行翻译处理

  • dp 数组的含义

dp[i] 表示下标范围为 [0, i] 那部分的数字 存在的翻译方法

  • 状态转移方程

我们需要确保遍历到的 s.charAt(i) 不为 0 ，本题的状态转移方程与 2.28 的一样

1
2
3
4
5
6
if (s.charAt(i) != '0') {
    dp[i] += dp[i - 1];
}
if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= 6)) {
    dp[i] += dp[i - 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
27
28
29
30
public int numDecodings(String s) {
    if (s == null || s.length() == 0 || "".equals(s)) return 0;
    int len = s.length();
    int[] dp = new int[len];
    if (s.charAt(0) == '0') {
        // 如果第一个字符为 '0' ，那么初始化 dp[0] 为 0 
        dp[0] = 0;
    } else {
        // 否则初始化为 1 
        dp[0] = 1;
    }
    for (int i = 1;i < len;++i) {
        if (s.charAt(i) != '0') {
            dp[i] += dp[i - 1];
        }
        if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')) {
            if (i == 1) {
                // 如果第二个字符为 '0' ，那么就将 dp[1] 初始化为 1 ，因为此时 x0 只能有一种翻译方式
                if (s.charAt(i) == '0') {
                    dp[i] = 1;
                } else {
                    dp[i] = 2;
                }
            } else {
                dp[i] += dp[i - 2];
            }
        }
    }
    return dp[len - 1];
}

2.42、最佳买卖股票时机含冷冻期

1、题目描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  1. 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  2. 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
  • 示例
1
2
3
输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

2、解题思路

  • 在这道题中，我们需要明确在第 i 天可能处于的几种状态
  1. dp[i][0]：在第 i 天时持有股票的最大收益
  2. dp[i][1]：在第 i 天时不持有股票，且处于冷冻期的最大收益
  3. dp[i][2]：在第 i 天时不持有股票，且不处于冷冻期的最大收益
  • 明确 dp 数组的含义

dp[i] 表示在第 i 天时可以收到的最大收益

  • 明确状态转移方程

我们需要知道这几个状态是怎么转变来的

  1. 第 i 天持有股票，那么有两种情况

即第 i - 1 天就已经持有股票，此时 dp[i][0] = dp[i - 1][0]

在第 i 天买入股票，那么要求在第 i - 1 天不处于冷冻期，因为如果 i - 1 天处于冷冻期，那么证明在 i - 2 天时卖出了股票，而题目要求一次最多持有一股，此时 dp[i][0] = dp[i - 1][2] - prices[i]

  1. 第 i 天不持有股票，且处于冷冻期

这个状态只能由一个状态推导而来，那就是在第 i - 1 天卖出了股票，此时 dp[i][1] = dp[i - 1][0] + prices[i]，那么要求在第 i - 1 天持有股票

  1. 第 i 天不持有股票，且不处于冷冻期，这个状态可以由两个状态推导而来

如果在第 i - 1 天处于冷冻期，那么在第 i 天就不处于冷冻期了，此时存在 dp[i][2] = dp[i - 1][1]

如果在第 i - 1 天就不处于冷冻期了，那么在第 i 天也不处于冷冻期，此时存在 dp[i][2] = dp[i - 1][2]

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

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) return 0;
    int len = prices.length;
    // 创建一个三维的数组，其中：
    //1 dp[i][0]：在第 i 天持有股票所能获取的最大收益
    //2 dp[i][1]：在第 i 天没有持有股票，同时处于冷冻期所能获取的最大收益
    //3 dp[i][2]：在第 i 天没有持有股票，同时不处于冷冻期所能获取的最大收益
    int[][] dp = new int[len][3];
    dp[0][0] = -prices[0];
    for (int i = 1;i < len;i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
        dp[i][1] = dp[i - 1][0] + prices[i];
        dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
    }
    // 最终结果将在没有持有股票的两个状态中获取
    return Math.max(dp[len - 1][1], dp[len - 1][2]);
}

由于第 i 天的状态只与第 i - 1 天的状态相关，所以可以使用滚动变量进行空间优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) return 0;
    int len = prices.length;
    int[][] dp = new int[2][3];
    dp[0][0] = -prices[0];
    for (int i = 1;i < len;i++) {
        dp[1][0] = Math.max(dp[0][0], dp[0][2] - prices[i]);
        dp[1][1] = dp[0][0] + prices[i];
        dp[1][2] = Math.max(dp[0][1], dp[0][2]);
        // 进行数据滚动更新
        dp[0][0] = dp[1][0];
        dp[0][1] = dp[1][1];
        dp[0][2] = dp[1][2];
    }
    return Math.max(dp[1][1], dp[1][2]);
}

2.43、杨辉三角

1、题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

2、解题思路

  • 杨辉三角的第 i 行有 i 个元素，我们需要循环 numRows 次，为每一行元素赋值，对于每一行，我们需要循环 i 次
  • 对于杨辉三角中的一行元素而言，当该元素为第一个或最后一个元素时，对应位置的元素为 1 ，即 nums[i][j] = 1（when j == 0 || j == i）
  • 当 1 <= j <= i - 1 时，对于 nums[i][j] 存在以下关系
1
nums[i][j] = nums[i - 1][j - 1] + nums[i - 1][j];

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> generate(int numRows) {
    // 使用一个列表来存放最终结果
    List<List<Integer>> result = new ArrayList<>();
    // 我们需要循环 numRows 次，为每一行元素赋值
    for (int i = 0;i < numRows;i++) {
        // 使用一个列表，用来存放本行的元素
        List<Integer> curResult = new ArrayList<>();
        // 在本行中，我们需要循环 i + 1 次，因为这里的 i 从 0 开始
        for (int j = 0;j <= i;j++) {
            if (j == 0 || j == i) { // 本行的第一个元素和最后一个元素需要赋值为 1 
                curResult.add(1);
            } else { // 本行的剩下元素按照上面的规则进行获取
                curResult.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
            }
        }
        // 将本行元素加入到最终结果中
        result.add(curResult);
    }
    return result;
}

2.44、杨辉三角 II

1、题目描述

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

2、解题思路

这道题与上一道题的思路一致，但是可以使用一个滚动列表来进行更新

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> getRow(int rowIndex) {
    List<Integer> result = new ArrayList<>();
    List<Integer> preResult = new ArrayList<>();
    for (int i = 0;i <= rowIndex;i++) {
        for (int j = 0;j <= i;j++) {
            if (j == 0 || j == i) {
                result.add(1);
            } else {
                result.add(preResult.get(j - 1) + preResult.get(j));
            }
        }
        // 滚动更新
        preResult = result;
        // 清除上一个 result 的值
        result = new ArrayList<>();
    }
    return preResult;
}

三、01 背包

3.1、01 背包回顾

1、题目描述

有 N 件物品和一个最多能负重 W 的背包，其中第 i 件物品的重量是 weight[i]，价值是 value[i]**。每件物品只能使用一次**，求解将哪些物品装入背包里，得到的物品价值总和最大？

image.png

2、使用动态规划求解 01 背包问题

  • 明确选择和状态

在这个问题中，状态包含两个变量，即背包的重量及所得到的价值，而选择也非常简单，就是是否选择将某件物品放入背包中。

  • 明确 dp 数组的含义，这里使用一个二维的 dp 数组来解决这个问题，其中 dp[i][j] 表示从下标 [0, i] 的物品中任意取，放入容量为 j 的背包中，所能获得价值的最大总和为多少

  • 明确递推公式

  1. 对于第 i 件物品，当剩余背包容量无法容纳该物品，或者我们选择不将其放入到背包中时，此时有关系如下
1
dp[i][j] = dp[i - 1][j]
  1. 对于第 i 件物品，当剩余背包容量可以容纳该物品，且我们选择将其放入到背包时，此时存在关系如下，其中 weight[i] 、 value[i] 分别指 i 物品的重量与价值。
1
dp[i][j] = dp[i - i][j - weight[i]] + value[i];

因此我们可以得到以下的递推公式

1
2
3
4
5
if (j < weight[i]) {
	dp[i][j] = dp[i - 1][j]
} else {
	dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
}
  • 初始化 dp 数组
  1. 当 j 为 0 时，此时背包容量为 0 ，因此可获取的最大价值也为 0 ，即 dp[i][0] = 0
  2. 当 i 为 0 时，即只有第一件物品可供选择时，如果此时背包容量 j >= weight[0] ，那么应该初始化对应的 dp[0][j] 为 value[0]

3.2、使用一维滚动数组优化背包问题

1、优化思路

当使用二维数组时，背包问题的递推公式为 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

  • 可以看到，如果我们将 dp[i - 1] 那一层都拷贝到 dp[i] 上，那么表达式完全可以是 dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i]] + value[i])

  • 当前层的状态完全由上一层状态推导而来，对于这种情况，我们可以考虑使用滚动数组进行优化，这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

2、含义介绍

  • 确定 dp 数组的含义

在一维 dp 数组中， dp[j] 表示：容量为 j 的背包，所背的物品价值可以最大为 dp[j]

  • 确定递推公式
  1. 当我们选择不放物品 i 时，所得到的最大价值为 dp[j]，这里可以类比我们使用二维数组的时候，如果选择不放物品 i 时，我们得到的最大价值为 dp[i - 1][j] ， 等于是把 dp[i][j] 的上一层数据拷贝下来
  2. 当我们选择放物品 i 时，所得到的最大价值为 dp[j - weight[i]] + value[i]

所以，我们可以得到使用一维数组时，01 背包问题的递推公式为

1
2
3
4
5
if (j < weight[i]) {
	dp[j] = dp[j];
} else {
	dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
  • dp 数组初始化

当 j 为 0 时，此时背包容量为 0 ，所以所能装的物品的最大价值也是 0 ，即 dp[0] = 0；

对于其他位置的值，我们同样将其初始化为 0 ，避免因初始化值过大导致递推公式计算出来的值无法将初始值覆盖（将整个数组都初始化为 0 ）

  • 遍历顺序

在二维数组中，无论是先遍历物品，还是先遍历背包都是可以的，但是在一维 dp 数组中，我们需要先遍历物品，然后再遍历背包，同时需要注意的是，我们在遍历背包时，需要进行倒序遍历

  • 为什么要倒序遍历背包？

这是为了保证物品只被添加一次，在使用二维数组时，当前层和上一层的数据是完全隔离开的，所以正序遍历和倒序遍历都可以，但当我们使用一维数组时， 如果先计算 dp[j - 1] ，那么它可能会影响到后面 dp [j] 的数据，我们可以来举一个例子，其中 weight = {1,3,4} ，values = {15,20,30} ，同时最大容量 capacity = 4.

  1. 当我们使用正序遍历时， dp[1] = Math.max(dp[1], dp[1 - weight[0]] + values[0]) = Math.max(dp[1], dp[1 - 1] + 15) = 15; dp[2] = Math.max(dp[2], dp[2 - weight[0]] + values[0]) = Math.max(dp[2], dp[2 - 1] + 15) = 30

可以看到，如果我们使用正序遍历，那么在计算 dp[2] 时，递推公式中的 dp[2 - 1] = dp[1] 是我们在上一次计算出来的 15 ，而且得到的结果也是 30 ，这相当于我们将第 0 件物品重复加入到了背包中。

  1. 当我们使用倒序遍历时， dp[2] = max(dp[2], dp[2 - weight[0]] + values[0]) = max (0, dp[1] + 15) = 15；dp[1] = max(dp[1], dp[1 - weight[0]] + values[0]) = max(0, dp[0] + 15) = 15

此时可以看到，第 0 件物品只被加入到了一次，这是因为此时在计算 dp[j] 时， dp[j - 1] 的结果还没有被计算出来，所以不会影响 dp[j] 的计算。

3、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int knapsack(int number, int capacity, int[] weight, int[] values) {
    if (weight == null || values == null || weight.length != values.length) return 0;
    // 创建一个一维的 dp 数组，dp[j] 表示，当背包容量为 j 时，该背包能容纳物品的最大价值
    int[] dp = new int[capacity + 1];
    // 外层循环，先遍历物品
    for (int i = 0;i < number;i++) {
        // 内层循环，需要倒序遍历背包
        for (int j = capacity;j >= weight[i];j--) {
            // 使用递推公式，从右至左计算 dp[j] 的值
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]);
        }
    }
    // 最后返回 dp[capacity] ，就是 capacity 容量的背包所能容纳的物品的最大价值
    return dp[capacity];
}

3.3、目标和

1、题目描述

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

  • 示例一
1
2
3
4
5
6
7
8
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3
  • 示例二
1
2
输入：nums = [1], target = 1
输出：1

2、解题思路

  • 使用动态规划来解决这道题，这道题也可以转换为 01 背包问题，与 01 背包问题不同的是，前者可以选择是否将这件物品装入背包中，而本题要求全部数字都被选中，但可以选择 + 和 -
  • 将这个数组分割为两部分，其中被赋予 + 的那一部分称为 P ，而被赋予 - 的那一部分称为 N ，所以我们可以得到以下结论
  1. sum(P) - sum(N) = S
  2. sum(P) + sum(N) = 数组中所有元素的和 sum
  3. 将上面的式子相加，有 2 * sum(P) = target + sum，移项有 sum(P) = (target + sum) / 2，我们记这个值为 result，即 result = (target + sum) / 2

所以问题就转换为求容量为 result 的 01 背包问题，要装满容量为 result 的背包，有几种方案

  • 如果 target 的值大于 sum ，那么直接返回 0 ，因为此时无法找到一种可能的实现
  • 如果 sum(P) 不是正数，即 (target + sum) 不是偶数，那么返回 0
  • 确定 dp 数组的含义

dp[j] 表示在数据 nums 中，凑出 j 的方法有 dp[j] 种，换成背包问题就是，如果要填充 j 这么大容积的包，有 dp[j] 种方法

  • 确定递推公式
  1. 填满容量为 j - nums[i] 的背包，有 dp[j - nums[i]] 种方法
  2. 那么只需要获得 nums[i] ，我们就可以凑出 dp[j] ，此时得到 dp[j] 的方法有 dp[j - nums[i]] ，这里有点类似凑硬币

比如说，如果我们当前需要计算 dp[5] ，同时我们手中有一个重量为 2 的物品，此时我们只需要计算出 dp[3] 就可以得到在我们有 重量为 2 的物品的前提下，能填满容量为 5 的背包的方法，所以我们可以得到以下的递推公式

1
dp[j] += dp[j - nums[i]]
  • 初始化 dp 数组

这道题中，由于我们要求 dp[result] ，所以我们需要初始化一个长度为 result + 1 的数组，同时，当 j == 0 时，使用 nums 数组中的元素可以有一种方法凑出 0 ，故 dp[0] = 1;

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
public int findTargetSumWays(int[] nums, int target) {
    if (nums == null || nums.length == 0) return 0;
    //1 计算数组元素和
    int sum = gengerateSumByArray(nums);
    //2 如果 sum 小于 target 或者 （sum + target） 不是偶数，那么直接返回 0 
    if (sum < target || (sum + target) % 2 == 1) return 0;
    //3 使用一个变量保存 (sum + target) / 2;
    target = (sum + target) / 2;
    //这里需要进行判断，如果计算出来的 target 小于 0 ，那么需要将其变为相反数
    target = Math.abs(target);
    //4 创建一个长度为 target + 1 的数组，并进行初始化
    int[] dp = new int[target + 1];
    // 当 j == 0 时，此时在 nums 中，只能找出一种方案凑出 0 ，所以 dp[0] = 1
    dp[0] = 1;
    //5 外层循环遍历物品
    for (int num : nums) {
        //6 内层循环倒序遍历背包
        for (int j = target;j >= num;j--) {
            // 使用递推公式累加 dp[j] 的值
            dp[j] += dp[j - num];
        }
    }
    return dp[target];
}

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

3.4、使用一维滚动数组优化分割等和子集问题

1、优化思路

  • 使用一维滚动数组代替原来的二维数组
  • dp 数组的含义

dp 是一个一维的 boolean 数组，其中 dp[j] 表示在数组中，是否可以找到一个子集，使得这些子集的和等于 j

  • 递推公式

当我们知道数组元素 nums[i] 时，此时如果 dp[j] 或 dp[j - nums[i]] 有一个为 true ，那么就代表 dp[j] 为 true ，即

1
dp[j] = dp[j] || dp[j - nums[i]]

2、解题代码

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
/**
 * 这道题可以看为，在 nums 中，是否可以找到几个数，这几个数的和为 sum / 2 ，其中 sum 为数组元素和
 */
public boolean canPartition(int[] nums) {
    if (nums == null || nums.length == 0) return true;
    //1 计算数组元素和
    int sum = gengerateSumByArray(nums);
    // 如果数组元素和不是一个偶数，那么直接返回 false
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    //2 我们需要在数组 nums 中，找到是否存在几个数字，满足这几个数字的和为 target
    // dp[j] 表示在数组 nums 中，是否存在几个数字，满足这几个数字的和为 j
    boolean[] dp = new boolean[target + 1];
    // 初始化 dp 数组，当 j == 0 时，此时可以找到几个数字，满足这几个数字的和为 0 
    dp[0] = true;
    for (int num : nums) {
        for (int j = target;j >= num;j--) {
            // 如果 dp[j] 或 dp[j - num] 有一个为真，那么 dp[j] 即为真，此时代表存在...
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}
private int gengerateSumByArray(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    return sum;
}

3.5、最后一块石头的重量 II

1、解题思路

  • 在上面有提到，这道题其实就是尽量将石头分成重量相同的两堆，然后让相撞之后剩下的石头最小。

  • 这道题其实就是求，给你一个大小为 sum / 2 的背包，其中 sum 为 nums 的元素和，然后尽可能地往背包中装东西，我们假设最多往背包中装了 maxWeight 重量的石头，那么我们要求的结果就是 sum - 2 * maxWeight;

  • 确定 dp 数组

使用一个一维的 boolean 类型的 dp 数组，其中 dp[j] 的含义、状态转移方程与 分割等和子集 问题中 dp 数组的含义相同，即在数组 nums 中，能否找到一个子集，使得这个子集的元素和的值等于 j 。

  • 当计算好 dp 数组后，我们需要反向遍历 dp 数组，寻找第一个为 true 的元素值，然后得到结果并返回，结果为 sum - 2 * j

2、解题代码

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
public int lastStoneWeightII(int[] stones) {
    if (stones == null || stones.length == 0) return 0;
    int sum = generateSumByArray(stones);
    // 计算出 target 的值，我们要尽可能装满这个容量为 target 的包
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    // 外层循环遍历物品
    for (int stone : stones) {
        // 内层循环反向遍历背包
        for (int j = target;j >= stone;j--) {
            dp[j] = dp[j] || dp[j - stone];
        }
    }
    // 填完表后，我们需要找到最接近 target 的一个 j 值
    for (int j = target;;j--) {
        // 找到第一个为 true 的j
        if (dp[j]) {
            return sum - 2 * j;
        }
    }

}
private int generateSumByArray(int[] stones) {
    int sum = 0;
    for (int stone : stones) sum += stone;
    return sum;
}

3.6、一和零

1、题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

  • 示例 1：
1
2
3
4
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
  • 示例 2：
1
2
3
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

2、解题思路

这道题也可以看为 01 背包问题，其中字符串数组中的每一个字符串都是一件物品，而 m 和 n 相当于一个二维的背包

  • 确定 dp 数组的含义，这里使用滚动数组进行优化，其中 dp[i][j] 表示最多有 i 个 0 和 j 个 1 的 strs 的最大子集的大小为 dp[i][j]
  • 对于 dp[i][j] 而言，它可以由前一个 strs 里的字符串推导出来，假设该字符串中含有 zeroNum 个 0 ，同时含有 oneNum 个 1 ，那么有以下的递推公式
1
dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)
  • 如何初始化 dp 数组？

只需要将 dp 初始化为 0 即可

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
public int findMaxForm(String[] strs, int m, int n) {
    if (strs == null || strs.length == 0) return 0;
    // 创建一个二维数组，其中 dp[i][j] 表示子集最多能有 i 个 0 ，j 个 1 时，最大子集的长度
    int[][] dp = new int[m + 1][n + 1];
    // 外层循环遍历物品，在这道题中，一个字符串就是一件物品
    for (String str : strs) {
        // 获取这个字符串中 1 的个数和 0 的个数
        int zeroNum = countCharNum(str, '0');
        int oneNum = countCharNum(str, '1');
        // 内层循环遍历背包，这里有两个背包需要进行遍历，分别为容量为 m 的背包和 容量为 n 的背包，倒序遍历
        for (int i = m;i >= zeroNum;i--) {
            for (int j = n;j >= oneNum;j--) {
                // 使用递推公式计算 dp[i][j] 的值
                dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
            }
        }
    }
    return dp[m][n];
}

private int countCharNum(String str, char ch) {
    int num = 0;
    for (int i = 0;i < str.length();i++) {
        if (str.charAt(i) == ch) {
            num++;
        }
    }
    return num;
}

四、完全背包问题

4.1、完全背包问题理论说明

1、题目描述

设有 n 种物品，每种物品都有一个重量及一个价值，其中第 i 件物品的重量为 weight[i]，价值为 value[i]。且每种物品的数量是无限的，同时有一个背包，最大载重量为 M ，今从 n 种物品种选取若干个物品（同一种物品可以被多次选取）放入背包中，使其重量的和小于等于 M ，而价值的和为最大。

  • 与 01 背包不同的是，前者每件物品只有一个，而完全背包问题中每种物品可以有无限多个。

2、解题思路

  • 在完全背包问题中，对于第 i 件物品，我们有几种选择
  1. 选择将 0 个物品装入到背包中
  2. 选择将 n 个该物品装入到背包中，我们可以不断往背包中添加该物品，直到背包被装满，也就是说，在完全背包问题中，同一件物品被装入背包的次数是有上下限的，下限为 0 ，上限为 M / n （向下取整）

当当前背包容量为 j 时，对于第 i 件物品装入背包的次数范围为 [0, j / w[i]] ，其中 j / w[i] 需要向下取整

  • 在之前使用一维滚动数组优化 01 背包问题时，我们有谈及到为什么内层循环需要进行反向遍历 – 为了避免一个物品被重复添加到背包中多次；而完全背包问题里的物品完全可以多次添加到背包中，所以对于完全背包问题的内层循环，我们可以正序遍历背包。

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
/**
 * 求解完全背包问题
 * @param number 物品个数
 * @param capacity 背包容量
 * @param weight 物品重量数组
 * @param value 物品价值数组
 * @return 能获取到的最大收益
 */
public int completeBackpack(int number, int capacity, int[] weight, int[] value) {
    if (weight == null || value == null || weight.length != value.length) {
        return 0;
    }
    // 创建一个一维数组 dp
    int[] dp = new int[capacity + 1];
    // 外层数组遍历物品
    for (int i = 0;i < number;i++) {
        // 内层物品遍历背包，这里需要从左往右遍历
        for (int j = weight[i];j <= capacity;j++) {
            // 使用递推公式
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[capacity];
}

4.2、零钱兑换

1、题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 ，你可以认为每种硬币的数量是无限的

  • 示例一
1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
  • 示例二
1
2
输入：coins = [2], amount = 3
输出：-1

2、解题思路

  • 这个问题可以看为一个完全背包问题，在这道题中，我们需要求解最值问题
  • 确定 dp 数组含义

其中 dp[j] 表示，要想在 coins 中凑出金额为 j 的零钱，最少需要 dp[j] 个硬币

  • 状态转移方程

如果我们手一个 coins[i] ，那么我们只需要计算出凑出 j - coins[i] 的最少硬币数，然后 + 1，即可得到凑出 j 的最少硬币数，所以，我们得到的状态转移方程如下：

1
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);// 注意，这里需要当子问题有解时才进行状态转移，即 dp[j - coins[i]] 不为 Integer.MAX_VALUE 时
  • 初始化 dp 数组
  1. 当 j 为 0 时，此时只需要 0 个硬币就可以凑出，所以 dp[0] = 0;
  2. 当 j 不为 0 时，我们需要将其初始化为一个非常大的数，避免后面在求出一个大于 0 的数时，在经由 Math.min (0, dp[j]) 进行选择时，让 0 覆盖了结果值，比如说，我现在求出了 dp[1] 为 1 ，但是我的 dp[1] 在初始化时初始化为 0 了，所以导致我在进行取最小值时，无法将 dp[1] = 1 这个值正确地更新到数组中。
  • 什么样的子问题才需要进行求解？

在我们进行遍历时，只有当子问题有解时，我们才考虑进行递推，所以，如果 dp[j - coin] 的值为 Integer.MAX_VALUE ，那么我们没必要进行状态转移，因为此时代表这个问题无解

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int coinChange(int[] coins, int amount) {
    if (coins == null || coins.length == 0) return -1;
    if (amount == 0) return 0;
    // 创建一个 dp 数组，长度为 amount + 1 ，其中 dp[amount] 就是在 coins 数组中，凑出 amount 所需的最少硬币数，也就是我们要求的结果
    int[] dp = new int[amount + 1];
    // 初始化 dp 数组，dp[0] = 1，这一步可以省略，我们需要将 dp 数组中非 0 位置的元素 初始化为 Integer.MAX_VALUE
    for (int i = 1;i < dp.length;i++) {
        dp[i] = Integer.MAX_VALUE;
    }
    // 外层遍历，遍历物品，也即硬币
    for (int coin : coins) {
        // 内层遍历，正向遍历背包，
        for (int j = coin;j <= amount;j++) {
            //  dp[j - coin] 不为 Integer.MAX_VALUE 时，证明此时 j - coin 可以被凑出，即这个问题有解，此时才需要进行求解。
            if (dp[j - coin] != Integer.MAX_VALUE) {
                // 使用状态转移方程求解 dp[j] 的值，这里求得是最小值
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

4.3、零钱兑换 II

1、题目描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 ，假设每一种面额的硬币有无限个。

  • 示例一
1
2
3
4
5
6
7
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
  • 示例二
1
2
3
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

2、解题思路

使用动态规划解决这道题，在本题中，由于每一种面额的硬币有无限个，我们将给定的 coins 数组看为物品数组，coins 数组中每个硬币的数额看为物品的重量，我们要做的就是寻找出凑齐 amount 重量的背包的方案数，这是一个完全背包问题。

  • 确定 dp 数组的含义

dp[j] 指的是，在 coins 数组中，有 dp[j] 种凑出 amount 数值的方案。

  • 状态转移方程

这是典型的组合问题，当我们手上有一颗数值为 coins[i] 的硬币时，此时我们只需要知道在 coins 中凑出 amount - nums[i] 的方案数，就可以得到该条件下的方案数，所以状态转移方程应该如下

1
dp[j] += dp[j - nums[i]]
  • 初始化 dp 数组，当 j 为 0 时，此时有一种方案可以凑出 0 ，所以
1
dp[0] = 1;

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int change(int amount, int[] coins) {
    if (coins == null || coins.length == 0) return 0;
    // 创建一个 dp 数组，其中 dp[j] 表示在 coins 中，能凑出数额为 j 的方案数
    int[] dp = new int[amount + 1];
    // 初始化 dp 数组，当 j 为 0 时， dp[j] == 1
    dp[0] = 1;
    // 外层遍历，遍历物品
    for (int i = 0;i < coins.length;i++) {
        // 内层遍历，对于完全背包问题，我们需要正向遍历背包
        for (int j = coins[i];j <= amount;j++) {
            // 使用递推公式计算出 dp[j]
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

4.4、组合总和 IV

1、题目描述

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

请注意，顺序不同的序列被视作不同的组合。

  • 示例 1：
1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
  • 示例 2：
1
2
输入：nums = [9], target = 3
输出：0

2、解题思路

  • 这道题是典型的完全背包问题，同时求的是排列数，所以外层循环需要遍历背包，内层循环需要遍历物品
  • 确定 dp 数组的含义

dp[i] 表示凑成正整数为 i 的排列个数为 dp[i]

  • 确定递推公式

dp[i] 可以由 dp[i - nums[j]] 推导出来，其中 dp[i] 考虑了 nums[j] ，而 dp[i - nums[j]] 不考虑 nums[j] ，因为只要得到 nums[j]，排列个数 dp[i - nums[j]]，就是 dp[i]的一部分

我们可以确定递推公式如下：

1
dp[i] += dp[i - nums[j]];
  • 初始化 dp 数组

由于递推公式为 dp[i] += dp[i - nums[j]] 的缘故，所以 dp[0] 要初始化为 1 ，这样递归其他 dp[i] 时才会有数值基础。

这里需要注意， dp[0] 是没有意义的。

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
   public int combinationSum4(int[] nums, int target) {
       if (nums == null || nums.length == 0) return 0;
       // 创建一个 dp 数组，其中 dp[i] 表示能在 nums 中能组成 i 的排列数
       int[] dp = new int[target + 1];
// 初始化 dp[0] = 1 ，这个 dp[0] 是没有含义的
       dp[0] = 1;
       // 外层循环遍历背包
       for (int i = 0;i <= target;i++) {
           // 内层循环遍历物品
           for (int j = 0;j < nums.length;j++) {
               // 只有当背包容量大于第 j 件物品时，才需要进行分割子问题
               if (i >= nums[j]) {
                   dp[i] += dp[i - nums[j]];
               }
           }
       }
       return dp[target];
   }

4.5、爬楼梯

1、题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

  • 示例一
1
2
3
4
5
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
  • 示例二
1
2
3
4
5
6
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

2、解题思路

  • 使用完全背包的思路解决这道题，这道题又是一道排列数的问题
  • 此时，背包中只有两件物品，即 1 和 2 ，我们需要找出装满容量为 n 的背包的方案数
  • 确定 dp 数组的含义

其中 dp[i] 表示爬上 n 阶楼梯有 dp[i] 种不同的排列方案。

  • 确定递推公式

由于此时球的是排列方法，所以我们可以得到本体的递推公式

1
dp[i] += dp[i - nums[j]];
  • 初始化 dp 数组

与上题相同，由于此时递推公式是 dp[i] += dp[i - nums[j]] ，所以我们需要初始 dp[0] = 1 ，这是递推的基础值

  • 本题中的物品

在本题中，只有两个物品，其中第一个物品的重量为 1 ，第二个物品的重量为 2。

3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int climbStairs(int n) {
    if (n == 1 || n == 2) return n;
    // 初始化一个 dp 数组，长度为 n + 1，其中 dp[i] 表示爬上 i 阶楼梯的方案排列数
    int[] dp = new int[n + 1];
    // 初始化 dp 数组
    dp[0] = 1;
    // 外层循环，在求排列的过程中需要遍历背包
    for (int i = 0;i <= n;i++) {
        // 内层循环，需要遍历物品，这里只有两件物品，其中第一件物品的重量为 1 ，第二件物品的重量为 2 
        for (int j = 1;j <= 2;j++) {
            // 如果当前背包的容量大于物品重量，这里为 j 
            if (i >= j) {
                dp[i] += dp[i - j];
            }
        }
    }
    return dp[n];
}

4.6、完全平方数

1、题目描述

给定正整数 n ，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n 。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

  • 示例一
1
2
3
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
  • 示例二
1
2
3
输入：n = 13
输出：2
解释：13 = 4 + 9

2、解题思路

  • 这道题中，n 可以有多个相同的完全平方数 x^2 组成，也就是说，如果我们将 x 看为背包问题中的物品，那么每个 x 可以被多次加入到背包中
  • 我们可以将这道题转换为，给你一个容量为 n 的背包，同时给你一些物品，而物品由 n 决定，物品为 [1, b] ，其中满足 b * b <= n 且 (b + 1) * (b + 1) > n
  • 明确 dp 数组含义

其中 dp[j] 表示 j 最少可以由 dp[j] 个完全平方数组成

  • 确定状态转移方程，这道题是一道求最值问题，所以状态转移方程为
1
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);

当我们手中握有 i * i 这个平方数时，我们只需要求出组成 j - i * i 最少需要多少个平方数，然后再这个结果的基础上加上一，就得到了我们想要的结果。

  • 初始化 dp 数组
  1. dp[0] 可以由 0 个平方数组成，所以 dp[0] = 0;
  2. dp[1] 可以由一个平方数组成，所以 dp[1] = 1;
  3. 对于其他下标的元素，在使用递推公式进行运算时，我们不希望它的真正结果被 0 覆盖，所以我们将其他下标的值都初始化为 Integer.MAX_VALUE

在进行子问题分割时，只有当 dp[j - i * i] 不为 Integer.MAX_VALUE 时（此时子问题存在有效解），才进行递推公式的计算。

3、解题代码

  • 首先，我们需要根据 n 找到本次问题所有所需的物品，即 [1, b] ，其中满足 b * b <= n 且 (b + 1) ^ 2 > n
1
2
3
4
5
6
7
8
9
10
11
12
private int getSizeByN(int n) {
    int size = 0;
    // 比如说 size 为 10 ，那么比 10 小的平方数有 1、4和9，可供选择的物品有 1 2 3 
    while (true) {
        // 如果 size + 1 的平方大于 n ，那么此时直接 break ，得到的 size 就是我们要寻找的值，当前物品的个数就是 1 - n 
        if ((size + 1) * (size + 1) > n) {
            break;
        }
        size++;
    }
    return size;
}
  • 使用两个循环来解决这道题，先遍历物品后遍历背包，只有当当前背包容量大于 i * i 且子问题有效时，才能进行状态转移
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int numSquares(int n) {
    if (n == 1) return 1;
    // 创建一个 dp 数组，其中 dp[i] 表示和为 i 的完全平方数的最少数量
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    // 初始化 dp 数组
    dp[0] = 0;
    // 计算出当前物品的个数，即 size 
    int size = getSizeByN(n);
    // 外层循环遍历物品
    for (int i = 1;i <= size;i++) {
        // 内层循环正序遍历背包，只有当当前背包容量大于等于物品重量的平方时且子问题有解时，才能进行状态转移
        for (int j = 0;j <= n;j++) {
            if (j >= i * i && dp[j - i * i] != Integer.MAX_VALUE) {
                // 此时可以进行状态转移
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
    }
    return dp[n];
}

五、背包问题总结

背包问题大体的接替模板是两层循环，分别是外层循环遍历物品，然后内层循环遍历背包，然后在循环中写状态转移方程。

在我现在的学习中，背包问题可以根据所给条件和待求项分为以下几类

5.1、根据所给条件分类

根据所给物品的个数，可以分为 01 背包问题和完全背包问题，在使用一维数组进行空间优化时，二者的区别是内层循环的遍历顺序，其中：

  • 对于 01 背包问题而言，内层循环在遍历背包时需要逆序遍历，保证物品只被加入到背包中一次
  • 对于完全背包问题而言，内层循环在遍历背包时需要正序遍历。

5.2、根据待求项分类

1、最值问题 I

问背包最多能装多少，状态转移方程一般如下：

1
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);

2、存在问题

当我们求解存在问题时，状态转移方程一般如下：

1
dp[j] = dp[j] || dp[j - nums[i]];

比如说上面我们就是将 分割等和子集 、 最后一块石头重量 II 看为存在问题解决。

3、组合问题

当我们求解存在问题时，状态转移方程一般如下：

1
dp[j] += dp[j - nums[i]];

比如说上面提到的零钱兑换 II 、 目标和 就是这类问题

4、最值问题 II

问装满背包所有物品的最小个数，状态转移方程一般如下：

1
dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);

零钱问题 I 就是这样的问题

5.3、组合问题和排列问题

1、组合问题

  • 组合数的概念：从 n 个不同元素中，任取 m（m≤n）个元素不计顺序的组成一组，则所有不同的组合个数，称为组合数。
  • 如果求组合数，那么就是外层循环遍历物品，内层循环遍历背包

2、排列问题

  • 排列数的概念：从 n 个不同元素中，任取 m（m≤n）个元素有顺序的排成一列，则所有不同的排列个数，称为排列数。
  • 如果求组合数，那么就是外层循环遍历背包，内层循环遍历物品

六、编辑距离问题总结

在使用动态规划求解字符串相关问题时， dp[i][j] 的含义通常是指字符串 s1 下标范围为 [0. i - 1] 的子串 a ，与字符串 s2 下标范围为 [0, j - 1] 的子串 b ，二者之间的某些指标。

个人觉得是为了考虑空串，同时为了 初始化工作的方便

6.1、判断子序列

  • dp 数组含义：dp[i][j] 表示字符串 s 中范围下标为 [0, i - 1] 的子串 a ，是否为字符串 t 中范围下标为 [0, j - 1] 的字符串 b 的子序列， dp 数组是一个二维的 boolean 数组

  • 当 s[i - 1] == t[j - 1] 时，此时表示 s 与 t 找到了一个公共字符，此时我们只需要判断当前 s 的子串 a ，在去掉公共字符后，是否为去掉公共字符的 b 的子序列即可（其中 b 为 t 的子串）

此时 s[0, i - 1] 是否为 t[0, j - 1] 的子序列，这个结果完全由 s[0, i - 2] 与 t[0, j - 2] 的关系决定。

如果此时 a 是 b 的子序列，那么证明 s[0, i - 1] 是 t[0, j - 1] 的子序列；反之则不是

  • 当 s[i - 1] != t[j - 1] ，此时我们需要删去 t 子串中的最后一个字符 t[j - 1] ，因为此时 s[0, i - 1] 是否为 t[0,j - 1] 的子序列与 t[j - 1] 完全没有关系

如果 s[0, i - 1] 已经是 t[0, j - 2] 的子序列，那么 s[0, i - 1] 也必定为 t[0, j - 1] 的子序列；

如果 s[0, i - 1] 并不是 t[0, j - 2] 的子序列，那么此时 t[j - 1] 这个字符于事无补，所以 s[0, i - 1] 也一定不为 t[0, j - 1] 的子序列；

  • 本题递推公式
1
2
3
4
5
if (s[i - 1] == t[i - 1]) {
	dp[i][j] = dp[i - 1][j - 1]
} else {
	dp[i][j] = dp[i][j - 1]
}

6.2、不同的子序列

  • dp 数组含义：dp[i][j] 表示字符串 s 中范围下标为 [0, i - 1] 的子串 a ，在字符串 t 中范围下标为 [0, j - 1] 的字符串 b 中作为子序列出现的次数，dp 数组是一个二维的 int 数组
  • 当 s[i - 1] == t[j - 1] 时，此时出现了公共字符，那么我们有两个选择
  1. 第一个选择就是让 s[i - 1] 字符直接与 t[j - 1] 进行匹配，比如说 s = bag , t = baagg ，我们可以选择让 t 中的最后一个 g 与 s 的最后一个 g 进行匹配，这是其中一种选择，这种选择下得到的个数为 dp[i][j] = dp[i - 1][j - 1] ，即我们只需要查找 s[0, i - 2] 在 t[0,j - 1] 中作为子序列出现的次数即可
  2. 第二种选择就是让 s[i - 2] 字符与 t[j - 1] 进行匹配，而 s[i - 1] 不参与匹配，比如说 s = bag , t = baagg ，让 t 中倒数第二个 g 与 s 中的最后一个 g 进行匹配，这也是其中一种情况，这种情况下得到的个数为 dp[i][j] = dp[i][j - 1] ，我们需要查找 s[0. i - 1] 在 t[0, j - 2] 中作为子序列出现的次数

由于本题中我们需要求出所有情况下出现次数之和，所以我们需要将上面两种选择得到的结果进行汇总

  • 当 s[i - 1] != t[j - 1] 时，此时我们只能舍弃 t 中最后一个字符，然后用剩下的字符进行匹配，此时式子为 dp[i][j] = dp[i][j - 1]
  • 递推公式
1
2
3
4
5
6
7
8
if (s[i - 1] == t[i - 1]) {
	// 两种情况汇总
	dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]
} else {
	// 去掉 t 中最后一个字符，然后尝试进行匹配
	dp[i][j] = dp[i][j - 1]
}

6.3、两个字符串中的删除操作

  • dp 数组含义：dp[i][j] 表示字符串 s 中范围下标为 [0, i - 1] 的子串 a ，变为字符串 t 中范围下标为 [0, j - 1] 的子串 b ，所需要进行的删除操作次数
  • 当 s[i - 1] == t[j - 1] 时，此时我们此刻相等的字符为公共字符，从 a[0, i - 1] 变为 b[0, j - 1] 所需的最小删除次数与 a[0, i - 2] 变为 b[0. j - 1] 所需的最小删除次数相等，也就是说，公共字符的存在与否并不会对两个字符串的最小删除次数造成影响，所以我们可以得出此时的式子为 dp[i][j] = dp[i - 1][j - 1]
  • 当 s[i - 1] == t[j - 1] 时，此时我们用三种做法可供选择，此时我们假设 s 的子串为 a ，t 的子串为 b
  1. 删去 a 中的某一个字符，此时得到的式子为 dp[i - 1][j] + 1 ，1 表示删去 a 中字符的那一次操作
  2. 删去 b 中的某一个字符，此时得到的式子为 dp[i][j - 1] + 1 ，1 表示删去 b 中字符的那一次操作
  3. 同时删去 a 和 b 中的字符，此时得到的式子为 dp[i - 1][j - 1] + 2

由于我们要求最小删除次数，所以我们需要在上述的三种情况中选择一个最小的结果

  • 递推公式
1
2
3
4
5
if (s[i - 1] == t[i - 1]) {
	dp[i][j] = dp[i - 1][j - 1];
} else {
	dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + 2);
}

6.4、编辑距离

  • dp 数组含义：dp[i][j] 表示字符串 s 中范围下标为 [0, i - 1] 的子串 a ，与字符串 t 中范围下标为 [0, j - 1] 的子串 b 之间的最小编辑距离
  • 当 s[i - 1] == t[j - 1] 时，此时子串 a 和 子串 b 二者的编辑距离与去掉公共字符的编辑距离相等，即 dp[i][j] = dp[i - 1][j - 1]
  • 当 s[i - 1] == t[j - 1] 时，此时我们有几种做法可供选择
  1. word1 删除一个元素，那么就是以下标 word1[0, i - 2] 与 word2[0, j - 1] 的最短编辑距离，再加上一个删除操作，此时得到的式子应该为 dp[i - 1][j] + 1
  2. word2 删除一个元素，那么就是以下标 word1[0, i - 1] 与 word2[0. j - 2] 的最短编辑距离，再加上一个删除操作，此时得到的式子应该为 dp[i][j - 1] + 1
  3. 替换元素，此时 word1 替换 word1[i - 1] ，使其等于 word2[j - 1] ，此时我们又可以将 word1[i - 1] 看为一个公共元素，只不过我们需要原来的基础上加上一次编辑，此时得到的式子为 dp[i - 1][j - 1] + 1
  4. 对于添加操作来说， word1 添加一个字符，就相当于 word2 删除一个字符，比如说，当 word1 为 abce ，word2 为 abc 时，word1 删去 e 与 word2 加上 e 的结果都相同，所以我们只需要考虑删除的情况即可
  • 递推公式
1
2
3
4
5
if (s[i - 1] == t[i - 1]) {
	dp[i][j] = dp[i - 1][j - 1];
} else {
	dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}