算法训练3.2.1 基础DP

斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：
0 <= n <= 30

题目解析

此题是动态规划最简单的题目之一。

状态转移方程式：题目已经明确告诉我们，F(n) = F(n - 1) + F(n - 2)
容器规模：数组表示的范围是 [0, n]，因此数组大小定义为n+1
base case：对于任意的 i，都只依赖于 i - 1 和 i - 2 ，因此我们只需要将数组下标为 0 和下标为 1 预先填好，后面所有的值都按照式子即可填满表中所有的值。
填表顺序：从下标为 2 开始往后填表即可

过程如下：

代码展示

class Solution {
    public int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int[] dp = new int[n + 1];
        dp[0] = 0; dp[1] = 1;
        for (int i = 2 ; i <= n ; i++) dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
}

打家劫舍

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

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

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

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400

题目解析

此题本质上是斐波那契数列。

状态转移方程式：dp[i] 表示考虑 [0, i] 的子数组按照规则进行偷窃，能获取的最大价值。对于下标为 i 的元素，可以选和不选，如果选的话则只能考虑 i - 2（因为不能偷相邻的），否则则考虑 i - 1，因此式子为：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
容器规模：i 的含义是数组下标，因此范围是 [0, nums.length - 1]，因此容器大小是 nums.length
base case：对于任意一个元素 i 只依赖 i - 1 和 i - 2，因此只需要预先填上 nums[0] 和 nums[1] 即可。
填表顺序：从下标为 2 开始按序填满数组即可。

代码展示

class Solution {
    /**
     * 计算能够偷到的最大金额
     * @param nums 表示每个房屋存放的金额的数组
     * @return 偷到的最大金额
     */
    public int rob(int[] nums) {
        // 如果只有一个房屋，则直接返回该房屋存放的金额
        if (nums.length == 1) return nums[0];
        // 初始化动态规划数组，dp[i] 表示偷到第 i 个房屋时能够得到的最大金额
        int[] dp = new int[nums.length];
        // 初始化动态规划数组的前两个元素
        dp[0] = nums[0]; 
        dp[1] = Math.max(nums[0], nums[1]);
        // 从第三个房屋开始遍历，计算每个房屋能够得到的最大金额
        for (int i = 2 ; i < nums.length ; i++) 
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); // 状态转移方程
        // 返回最后一个房屋能够得到的最大金额
        return dp[nums.length - 1];
    }
}

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

示例1

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

题目解析

状态转移方程式：dp[i][j] 表示走到 (i, j) 这个位置的最小路径和的值。而走到位置 (i, j) 只有两个位置可以走过来，也就是 (i - 1, j) 和 (i, j - 1)，因此我们取最小的即可，也就是 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
容器规模：i 和 j 的范围分别是 m 和 n ，因此定义 dp[m][n] 即可
base case：对于任意一个位置 (i, j) 都依赖于 (i - 1, j) 和 (i, j - 1)。因此我们只需要填满第一行 f(0, j) 即可，接下来依次填满填满即可 (f(1, j), f(2, j))。有一定基础的同学不难看出，这个依赖关系与“完全背包”一致。
填表顺序：从 i 等于 1 开始，一行一行从左往右填表即可。

代码展示

class Solution {
    /**
     * 计算从左上角到右下角的最小路径和
     * @param grid 表示网格的二维数组，grid[i][j] 表示第 i 行第 j 列的格子上的数字
     * @return 最小路径和
     */
    public int minPathSum(int[][] grid) {
        // 获取网格的行数和列数
        int m = grid.length, n = grid[0].length;
        // 计算第一行每个格子的最小路径和
        for (int i = 1 ; i < n ; i++) 
            grid[0][i] += grid[0][i - 1]; // 每个格子的路径和等于当前格子的值加上左边格子的路径和
        // 计算第一列每个格子的最小路径和
        for (int i = 1 ; i < m ; i++) 
            grid[i][0] += grid[i - 1][0]; // 每个格子的路径和等于当前格子的值加上上方格子的路径和
        // 计算其他格子的最小路径和
        for (int i = 1 ; i < m ; i++) {
            for (int j = 1 ; j < n ; j++) 
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); // 每个格子的路径和等于当前格子的值加上上方格子和左边格子中的较小路径和
        }
        // 返回右下角格子的最小路径和
        return grid[m - 1][n - 1];
    }
}

不同路径

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

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

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

示例 1：

示例1

输入：m = 3, n = 7
输出：28

示例 2：

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

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9

题目解析

状态转移方程式：dp[i][j] 表示走到位置 (i, j) 有多少种走法。走到位置 (i, j) 只有两个方向 (i - 1, j) 和 (i, j - 1)
容器规模：i 和 j 的范围分别是 [0, m - 1] 和 [0, n - 1]，因此 dp[m][n]
base case：对于任意位置 (i, j) 都依赖于 (i - 1, j) 和 (i, j -1)，因此我们只需要填满第一行f(0, j)即可，接下来依次填满填满即可 (f(1, j), f(2, j) … f(m - 1, j))。有一定基础的同学不难看出，这个依赖关系与“完全背包”一致。
填表顺序：从i等于1开始，一行一行从左往右填表即可。

代码展示

class Solution {
    // uniquePaths 方法用于计算在 m 行 n 列的网格中，从左上角到右下角的路径数量
    // 只能向下或向右移动
    public int uniquePaths(int m, int n) {
        // 初始化一个 m 行 n 列的动态规划数组 dp，所有元素初始化为 0
        int[][] dp = new int[m][n];
        // 对于第一行的每个位置，由于只能从左边到达，因此路径数量初始化为 1
        Arrays.fill(dp[0], 1); // base case
        
        // 遍历动态规划数组，填充路径数量
        for (int i = 1; i < m; i++) {
            // 对于第一列，由于只能从上面到达，因此路径数量等于上一行的路径数量
            dp[i][0] = dp[i - 1][0];
            // 遍历动态规划数组的当前行
            for (int j = 1; j < n; j++) {
                // 对于当前位置 dp[i][j]，其路径数量等于左边位置 dp[i][j - 1] 和上面位置 dp[i - 1][j] 的路径数量之和
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        // 返回到达右下角的路径数量，即 dp[m - 1][n - 1]
        return dp[m - 1][n - 1];
    }
}

不同路径 II

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

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

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

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

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

示例 2：

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

提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

代码展示

class Solution {
    // uniquePathsWithObstacles 方法用于计算在包含障碍物的网格中，从左上角到右下角的路径数量
    // 障碍物由 1 表示，空地由 0 表示，只能向下或向右移动
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 获取网格的行数 m 和列数 n
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        // 初始化一个 m 行 n 列的动态规划数组 dp，所有元素初始化为 0
        int[][] dp = new int[m][n];
        
        // 遍历 dp 数组的第一行，如果遇到障碍物（obstacleGrid[0][j] == 1），则终止遍历
        // 如果没有障碍物，则将 dp[0][j] 设置为 1，因为只能从左边到达
        Arrays.fill(dp[0], 0);
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                break;
            }
            dp[0][j] = 1;
        }
        
        // 遍历 dp 数组，从第二行开始
        for (int i = 1; i < m; i++) {
            // 对于每一行，先假设列索引为 0 的位置的路径数量为 0，因为第一行已经初始化
            dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
            
            // 遍历当前行的每个位置
            for (int j = 1; j < n; j++) {
                // 如果当前位置没有障碍物，则当前位置的路径数量是从上方和左方到达的路径数量之和
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] += dp[i - 1][j];
                    if (j > 0) {
                        dp[i][j] += dp[i][j - 1];
                    }
                } else {
                    // 如果当前位置有障碍物，则当前位置的路径数量为 0
                    dp[i][j] = 0;
                }
            }
        }
        
        // 返回到达右下角的路径数量，即 dp[m - 1][n - 1]
        return dp[m - 1][n - 1];
    }
}

杨辉三角

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

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

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:
1 <= numRows <= 30

题目解析

状态转移方程式：dp[i][j] 表示位置 i 和 j 的值。dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
容器规模：第 i 层是一个长度为 i 的数组。
base case：任意一个位置 (i, j) 都依赖于 (i - 1, j) 和 (i, j -1)，因此只需要填满第一行即可。
填表顺序：一行一行填即可。

代码展示

class Solution {
    // generate 方法用于生成一个包含 numRows 行的杨辉三角
    public List<List<Integer>> generate(int numRows) {
        // 初始化结果列表 res，使用 LinkedList 来存储杨辉三角的每一行
        List<List<Integer>> res = new LinkedList<>();
        // 添加杨辉三角的第一行，只有一个元素 1
        res.add(Arrays.asList(1));
        // 从第二行开始循环，直到生成 numRows 行
        for (int i = 1; i < numRows; i++) {
            // 初始化当前行的列表 cur，使用 LinkedList 来存储当前行的数字
            List<Integer> cur = new LinkedList<>();
            // 循环生成当前行的每个数字
            for (int j = 0; j < i + 1; j++) {
                // 如果是当前行的第一个或最后一个数字，值为 1
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    // 否则，当前数字是上一行相邻两个数字的和
                    // 通过 res.get(i - 1).get(j) 和 res.get(i - 1).get(j - 1) 获取上一行的相邻数字
                    cur.add(res.get(i - 1).get(j) + res.get(i - 1).get(j - 1));
                }
            }
            // 将当前行添加到结果列表 res 中
            res.add(cur);
        }
        // 返回生成的杨辉三角
        return res;
    }
}

三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11

解释：如下面简图所示：

2

3 4

6 5 7

4 1 8 3

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：
1 <= triangle.length <= 200

triangle[0].length == 1

triangle[i].length == triangle[i - 1].length + 1

-10^4 <= triangle[i][j] <= 10^4

题目解析

此题与杨辉三角一致。

状态转移方程式：dp[i][j] 表示走到位置 (i, j) 的最小路径和。因此 dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
容器规模：第 i 层是一个长度为 i 的数组。
base case：任意一个位置 (i, j) 都依赖于 (i - 1, j) 和 (i, j - 1)，因此只需要填满第一行即可。
填表顺序：一行一行填即可。

代码展示

class Solution {
    // minimumTotal 方法用于计算从三角形顶部到底部的最小路径和
    public int minimumTotal(List<List<Integer>> triangle) {
        // 获取三角形的行数
        int n = triangle.size();
        // 如果三角形只有一行，则直接返回第一行的第一个元素作为结果
        if (n == 1) {
            return triangle.get(0).get(0);
        }
        // 初始化一个二维数组 dp，用于存储动态规划的中间结果
        int[][] dp = new int[n][n];
        // 将三角形顶部的元素值赋给 dp 第一行的第一个元素
        dp[0][0] = triangle.get(0).get(0);
        // 初始化答案 ans 为一个足够大的数，用于记录遍历过程中的最小路径和
        int ans = 10000010;
        
        // 从三角形的第二行开始遍历
        for (int i = 1; i < n; i++) {
            // 对于每一行，遍历该行的每个元素
            for (int j = 0; j <= i; j++) {
                // 将当前元素的值赋给 dp[i][j]
                dp[i][j] = triangle.get(i).get(j);
                // 如果当前元素是行的第一个元素，则其路径和为 dp[i - 1][j] 加上当前元素的值
                if (j == 0) {
                    dp[i][j] += dp[i - 1][j];
                // 如果当前元素是行的最后一个元素，则其路径和为 dp[i - 1][j - 1] 加上当前元素的值
                } else if (j == i) {
                    dp[i][j] += dp[i - 1][j - 1];
                } else {
                    // 如果当前元素既不是行的第一个元素，也不是行的最后一个元素，
                    // 则其路径和为当前元素的值加上上一行相邻两个元素路径和的较小值
                    dp[i][j] += Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
                }
                // 如果当前已经到达三角形的最后一行，则更新答案 ans 为当前行的最小路径和
                if (i == n - 1) {
                    ans = Math.min(ans, dp[i][j]);
                }
            }
        }
        // 返回三角形的最小路径和
        return ans;
    }
}

完全平方数

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

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

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：
1 <= n <= 10^4

题目描述

状态转移方程式：dp[i] 的含义为 i 的完全平方数的最少数量。枚举思路是把 [1, i] 的每个数字都尝试一次。也就是 dp[i] = min(dp[i - j^2] + 1)，其中， $j \in [1,\sqrt{i}]$
容器规模：i 的范围是 [0, n]，因此 dp[n + 1]
base case：dp[1] = 1，i 的完全平方数的数量是 1
填表顺序，从 2 开始往后填即可。

代码展示

class Solution {
    // numSquares 方法用于计算将整数 n 表示为恰好几个完全平方数之和的最少数量
    public int numSquares(int n) {
        // 初始化一个长度为 n + 1 的数组 dp，用于存储动态规划的中间结果
        int[] dp = new int[n + 1];
        // 将 dp[1] 初始化为 1，因为 1 本身就是一个完全平方数
        dp[1] = 1;
        
        // 从 2 到 n 遍历所有整数
        for (int i = 2; i <= n; i++) {
            // 计算 i 的平方根，用于后续循环中判断是否可以表示为某个完全平方数之和
            int sqrt = (int) Math.sqrt(i);
            // 初始化 dp[i] 为一个足够大的数，确保后续可以找到更小的值
            dp[i] = 10001;
            
            // 从 1 到 sqrt 遍历所有可能的完全平方数
            for (int j = 1; j <= sqrt; j++) {
                // 更新 dp[i] 为 dp[i - j * j] + 1 和当前 dp[i] 的较小值
                // dp[i - j * j] 表示 i 减去 j 的平方后的值对应的完全平方数个数加 1
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        
        // 返回 dp[n]，即为 n 表示为完全平方数之和的最少数量
        return dp[n];
    }
}

组合总和 Ⅳ

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

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：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：

输入：nums = [9], target = 3
输出：0

提示：

1 <= nums.length <= 200

1 <= nums[i] <= 1000

nums 中的所有元素 互不相同

1 <= target <= 1000

题目描述

此题的枚举思路如下：

以样例1为例：对于数字7，我们可以选择1、2或者3，不同的选择最后求和的即可。

状态转移方程式：dp[i] 表示用 nums 组成 i 有多少种组合方式。dp[i] = Σ(dp[i - num]) 其中 num∈nums。
容器规模：i 的范围是 [0, n]。
base case：dp[0] = 1，0 的组合就只有一种（什么都不选）
顺序：从 1 到 n 填表

代码展示

class Solution {

    // combinationSum4 方法用于找出所有和为 target 的不同组合的数量
    // nums 是一个升序排列的整数数组，从中选出一些数字，使得它们的和为 target
    public int combinationSum4(int[] nums, int target) {
        // 获取数组 nums 的长度
        int n = nums.length;
        // 初始化一个大小为 target + 1 的 dp 数组，用于存储动态规划的中间结果
        // dp[i] 表示和为 i 的组合数量
        int[] dp = new int[target + 1];
        // 根据题目，和为 0 的组合只有一种，即空集，因此初始化 dp[0] 为 1
        dp[0] = 1;
        // 遍历 dp 数组，从 1 到 target
        for (int i = 1; i <= target; i++) {
            // 遍历数组 nums
            for (int num : nums) {
                // 对于 dp[i]，我们需要检查每个 num 是否可以从 i 中减去
                // 如果 i 大于等于 num，则说明 num 可以作为和为 i 的一部分
                // 因此，dp[i] 应该加上 dp[i - num]，即和为 i - num 的组合数量
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        // 返回 dp[target]，即和为 target 的不同组合的数量
        return dp[target];
    }
}

最长递增子序列

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

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

示例 1：

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

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
10^4 <= nums[i] <= 10^4

题目解析

状态转移方程式：dp[i] 表示包含第 i 位的最长递增子序列的长度。因此 dp[i] = max(dp[i], dp[j] + 1)，其中 j∈[0, i - 1]
容器规模：i∈[0, length - 1]
base case：dp 数组全部赋值为 1（最少肯定是1）
顺序：从 1 开始往后填表即可

代码展示

class Solution {
    // lengthOfLIS 方法用于计算数组 nums 中最长递增子序列的长度
    public int lengthOfLIS(int[] nums) {
        // 初始化一个 dp 数组，其长度与 nums 相同，所有元素初始值设为 1
        // dp[i] 表示以 nums[i] 结尾的最长递增子序列的最大长度
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        
        // 初始化 ans 为 1，用于存储遍历过程中发现的最长递增子序列的长度
        int ans = 1;
        
        // 外层循环从数组的第二个元素开始遍历
        for (int i = 1; i < nums.length; i++) {
            // 内层循环从当前元素的前一个元素开始向前遍历
            for (int j = i - 1; j >= 0; j--) {
                // 如果当前元素 nums[i] 大于其前一个元素 nums[j]，则存在递增关系
                if (nums[i] > nums[j]) {
                    // 更新 dp[i] 为 dp[j] + 1 和当前 dp[i] 的较大值
                    // 表示以 nums[i] 结尾的最长递增子序列长度至少为 dp[j] + 1
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    // 更新 ans 为遍历过程中的最长递增子序列长度
                    ans = Math.max(ans, dp[i]);
                }
            }
        }
        
        // 返回 ans，即为数组 nums 中最长递增子序列的长度
        return ans;
    }
}

最长连续递增序列

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

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

示例 1：

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

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

提示：

1 <= nums.length <= 104
-10^9 <= nums[i] <= 10^9

题目解析

状态转移方程式：dp[i] 表示包含第 i 位的最长连续递增序列的长度。if nums[i] > nums[i - 1]: dp[i] = dp[i - 1] + 1
容器规模：i∈[0, nums.length - 1]
base case：dp 数组全部赋值为 1
顺序：i 从 1 往后

代码展示

class Solution {
    // findLengthOfLCIS方法用于找出最长递增子序列的长度
    public int findLengthOfLCIS(int[] nums) {
        // n表示数组nums的长度
        int n = nums.length;
        // ans用于记录最长递增子序列的长度，初始值为1
        int ans = 1;
        // 创建一个长度为n的数组dp，用于存储到当前位置为止的最长递增子序列的长度
        int[] dp = new int[n];
        // 将dp数组的所有元素初始化为1，因为每个元素至少是一个长度为1的递增子序列
        Arrays.fill(dp, 1);
        // 从数组的第二个元素开始遍历，因为单个元素的递增子序列长度为1
        for (int i = 1 ; i < n ; i++) {
            // 如果当前元素nums[i]大于前一个元素nums[i-1]，则说明存在递增关系
            if (nums[i] > nums[i - 1]) {
                // 更新dp[i]为dp[i-1]+1，即当前位置的最长递增子序列长度为前一个位置的递增子序列长度加1
                dp[i] = dp[i - 1] + 1;
                // 更新ans为dp[i]和ans中的最大值，即记录到目前为止找到的最长递增子序列的长度
                ans = dp[i] > ans ? dp[i] : ans;
            }
        }
        // 返回最长递增子序列的长度
        return ans;
    }
}

最长重复子数组

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

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

题目解析

LCS属于经典的动态规划问题，同时也是面试场考题，同学们一定要熟悉！

状态转移方程式：dp[i][j] 表示包含 nums1 的第 i 个数字和包含 nums2 的第 j 个数字的最长重复子数组的长度。if nums1[i] == nums[j]: dp[i][j] = dp[i - 1][j - 1] + 1; else: dp[i][j] = 0
容器规模：i 的范围是 [0, len1] ，j 的范围是 [0, len2]
base case：由于依赖关系如下因此 basecase 应该是第一行和第一列（红色部分）因此，basecase是 dp[0][j] 和 dp[i][0]，二者均为 0。
填表顺序：从[1, 1]开始从左往右，从上到下填表即可。

代码展示

class Solution {
    // findLength方法用于找出两个数组nums1和nums2的最长公共子序列的长度
    public int findLength(int[] nums1, int[] nums2) {
        // len1和len2分别表示数组nums1和nums2的长度
        int len1 = nums1.length, len2 = nums2.length;
        // 创建一个二维数组dp，用于存储动态规划过程中的中间结果
        // dp[i][j]表示包含nums1的第i个数字和包含nums2的第j个数字的最长重复子数组的长度
        int[][] dp = new int[len1 + 1][len2 + 1];
        // ans用于记录最长公共子序列的长度，初始值为0
        int ans = 0;
        
        // 外层循环遍历nums1数组，从1开始，因为dp[0][j]和dp[i][0]都是0
        for (int i = 1 ; i <= len1 ; i++) {
            // 内层循环遍历nums2数组，同样从1开始
            for (int j = 1 ; j <= len2 ; j++) {
                // 如果nums1[i-1]和nums2[j-1]相等，说明找到了一个公共元素
                if (nums1[i - 1] == nums2[j - 1]) {
                    // 更新dp[i][j]为dp[i-1][j-1]+1，即当前元素的最长公共子序列长度为不包含当前元素时的最长公共子序列长度加1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    // 更新ans为ans和dp[i][j]中的最大值，即记录到目前为止找到的最长公共子序列的长度
                    ans = Math.max(ans, dp[i][j]);
                }
                // 如果nums1[i-1]和nums2[j-1]不相等，则dp[i][j]保持为0，因为公共子序列不能包含不匹配的元素
            }
        }
        // 返回最长公共子序列的长度
        return ans;
    }
}

最长公共子序列

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

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

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

示例 2：

输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。

示例 3：

输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

题目解析

同样属于LCS问题中的一类，属于面试常考题，一定要熟悉。

状态转移方程式：dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。如果 text1[i - 1] 与 text2[j - 1] 相同，那么找到了一个公共元素，所以 dp[i][j] = dp[i - 1][j - 1] + 1;如果 text1[i - 1] 与 text2[j - 1] 不相同，那就看看 text1[0, i - 2] 与 text2[0, j - 1] 的最长公共子序列和 text1[0, i - 1] 与 text2[0, j - 2] 的最长公共子序列，取最大的。即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) ;
容器规模：i 属于[0, text1.length] ，j 属于[0, text2.length]
base case：dp[0][j] 和 dp[i][0] 二者均为0。
填表顺序：从 [1, 1] 开始从左往右，从上到下填表即可。

代码展示

class Solution {
    // longestCommonSubsequence方法用于计算两个字符串text1和text2的最长公共子序列的长度
    public int longestCommonSubsequence(String text1, String text2) {
        // len1和len2分别表示字符串text1和text2的长度
        int len1 = text1.length();
        int len2 = text2.length();
        
        // 创建一个二维数组dp，用于存储动态规划过程中的中间结果
        // dp[i][j]表示以text1的前i个字符和text2的前j个字符结尾的最长公共子序列的长度
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        // 外层循环遍历text1字符串，从1开始，因为dp[0][j]和dp[i][0]都是0
        for (int i = 1 ; i <= len1; i++) {
            // 内层循环遍历text2字符串，同样从1开始
            for (int j = 1 ; j <= len2; j++) {
                // 如果text1的第i个字符和text2的第j个字符相同
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // 更新dp[i][j]为dp[i - 1][j - 1] + 1，即当前字符的最长公共子序列长度为不包含当前字符时的最长公共子序列长度加1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 如果当前字符不同，则dp[i][j]取dp[i - 1][j]和dp[i][j - 1]中的较大值
                    // 即选择不包含text1的第i个字符或不包含text2的第j个字符的最长公共子序列长度
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 返回dp[len1][len2]，即text1和text2的最长公共子序列的长度
        return dp[len1][len2];
    }
}

两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的 最小步数。

每步可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = “sea”, word2 = “eat”
输出: 2
解释: 第一步将 “sea” 变为 “ea” ，第二步将 “eat”变为 “ea”

示例 2:

输入：word1 = “leetcode”, word2 = “etco”
输出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

题目解析

状态转移方程式：dp[i][j] 考虑 word1 的前 i 个字符和 word2 的前 j 个字符转为相同的最小步数。如果 word1[i]==word2[j] 那么说明这一位是不需要删除的，此时 dp[i][j]=dp[i-1][j-1]。否则，要么删除 word1 的第 i 个字符，要么删除 word2 的第 j 个字符，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
容器规模：i 属于 [0,len1]，j 属于 [0,len2]
base case：依赖关系与“最长公共子序列”一致，因此basecase是 dp[0][j] 和 dp[i][0]，其中dp[0][j] = j, dp[i][0] = i
填表顺序：从 [1, 1] 开始从左往右，从上到下填表即可。

代码展示

class Solution {
    // minDistance方法用于计算将字符串word1转换为字符串word2所需的最少操作次数
    // 操作包括插入、删除和替换字符
    public int minDistance(String word1, String word2) {
        // len1和len2分别表示字符串word1和word2的长度
        int len1 = word1.length(), len2 = word2.length();
        
        // 创建一个二维数组dp，用于存储动态规划过程中的中间结果
        // dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最少操作次数
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        // 初始化dp数组的第一列，表示word1为空字符串，转换为word2的任意前缀所需的操作数
        for (int j = 1 ; j <= len2 ; j++) dp[0][j] = j;
        
        // 初始化dp数组的第一行，表示word2为空字符串，将word1的任意前缀转换为空所需的操作数
        for (int i = 1 ; i <= len1 ; i++) dp[i][0] = i;

        // 外层循环遍历word1字符串，从1开始，因为dp[i][0]已经初始化
        for (int i = 1 ; i <= len1 ; i++) {
            // 内层循环遍历word2字符串，从1开始，因为dp[0][j]已经初始化
            for (int j = 1 ; j <= len2 ; j++) {
                // 如果word1的第i个字符和word2的第j个字符相同，则不需要任何操作
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 如果字符不同，则考虑两种情况：
                    // 1. 删除word1的第i个字符，此时操作数为dp[i - 1][j] + 1
                    // 2. 删除word2的第j个字符，此时操作数为dp[i][j - 1] + 1
                    // 取两种情况中的最小值，然后加1，得到dp[i][j]
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        
        // 返回dp[len1][len2]，即word1转换为word2所需的最少操作次数
        return dp[len1][len2];
    }
}

编辑距离

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

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

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

示例 2：

输入：word1 = “intention”, word2 = “execution”
输出：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

题目解析

状态转移方程式：dp[i][j] 考虑 word1 的前 i 个字符和 word2 的前 j 个字符转为相同的最小步数。如果 word1[i]==word2[j] 那么说明这一位是不需要删除的，此时 dp[i][j]=dp[i-1][j-1]。否则，要么删除 word1 的第 i 个字符，此时 dp[i][j] = dp[i - 1][j] + 1；要么插入一个字符在 word1 后面，与 word2 匹配，此时 dp[i][j] = dp[i][j - 1] + 1; 要么将 word1 的第 i 个字符替换成与 word2 的第 j 个字符一致，此时 dp[i][j] = dp[i - 1][j - 1] + 1，在三种操作中选取最小的即可。
容器规模：i 属于 [0,len1]，j 属于 [0,len2]
base case：依赖关系与“最长公共子序列”一致，因此basecase是 dp[0][j] 和 dp[i][0]，其中 dp[0][j] = j, dp[i][0] = i
填表顺序：从 [1, 1] 开始从左往右，从上到下填表即可。

代码展示

class Solution {
    // minDistance方法用于计算将字符串word1转换为字符串word2所需的最少操作次数
    // 操作包括插入、删除和替换字符
    public int minDistance(String word1, String word2) {
        // len1和len2分别获取字符串word1和word2的长度
        int len1 = word1.length(), len2 = word2.length();
        
        // 创建一个二维数组dp，用于存储动态规划过程中的中间结果
        // dp[i][j]表示word1的前i个字符转换为word2的前j个字符所需的最少操作数
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        // 初始化dp数组的第一行，表示word1为空字符串时，转换为word2的任意前缀所需的操作数
        // 即word2的前j个字符需要插入j次
        for (int j = 1 ; j <= len2 ; j++) dp[0][j] = j;
        
        // 初始化dp数组的第一列，表示word2为空字符串时，将word1的任意前缀删除所需的操作数
        // 即word1的前i个字符需要删除i次
        for (int i = 1 ; i <= len1 ; i++) dp[i][0] = i;

        // 外层循环遍历word1字符串，从1开始，因为dp[i][0]已经初始化
        for (int i = 1 ; i <= len1 ; i++) {
            // 内层循环遍历word2字符串，从1开始，因为dp[0][j]已经初始化
            for (int j = 1 ; j <= len2 ; j++) {
                // 如果word1的第i个字符和word2的第j个字符相同，则不需要任何操作
                // dp[i][j]等于dp[i - 1][j - 1]，即word1的前i-1个字符和word2的前j-1个字符的最少操作数
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 如果字符不同，则考虑三种情况：
                    // 1. 删除word1的第i个字符，此时操作数为dp[i - 1][j] + 1
                    // 2. 在word2的第j个字符前插入一个字符，此时操作数为dp[i][j - 1] + 1
                    // 3. 替换word1的第i个字符为word2的第j个字符，此时操作数为dp[i - 1][j - 1] + 1
                    // 取三种情况中的最小值，然后加1，得到dp[i][j]
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1])) + 1;
                }
            }
        }
        
        // 返回dp[len1][len2]，即word1转换为word2所需的最少操作数
        return dp[len1][len2];
    }
}

回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

题目解析

所谓的区间 dp 就是我们定义的 dp 状态是一个区间，然后通过区间的收缩进行状态的转移。

状态转移方程式：dp[i][j] 表示区间 [i,j] 内的子串是否是回文串，这个子串是否是回文串取决于区间端点 s[i] 和 s[j] 是否相等，且 [i + 1, j - 1] 是否为回文串。即 dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]
容器规模：i 和 j 的范围均为 [0,length - 1]
base case：i == j 和 i + 1==j 的时候。依赖关系如下任何区间 (i, j) 最终都会依赖值对角线的值上（蓝色和黄色的格子），因此 i==j 和 i+1==j 是basecase。当 i==j 的时候，dp[i][j] 表示的是只有一个字符，dp[i][j]=true；当 i + 1==j 的时候，dp[i][j] 表示的是两个连续的字符，因此 dp[i][j] 是 true 或者 false 取决于 s[i]==s[j]。
填表顺序：先遍历 j ，再遍历 i，i 逆序遍历。（这样才可以保证我们填表的时候依赖的值已经填好了）

代码展示

class Solution {
    // countSubstrings方法用于统计一个字符串s中所有回文子串的数量
    public int countSubstrings(String s) {
        // 获取字符串s的长度
        int len = s.length();
        // 初始化结果res为0，用于计数回文子串的数量
        int res = 0;
        
        // 创建一个二维布尔数组dp，用于存储动态规划过程中的中间结果
        // dp[i][j]表示字符串s从索引i到j的子串是否为回文
        boolean[][] dp = new boolean[len][len];
        
        // 外层循环遍历字符串s的每个字符，j表示子串的结束索引
        for (int j = 0; j < len; j++) {
            // 内层循环从j向前遍历，i表示子串的开始索引
            for (int i = j; i >= 0; i--) {
                // 如果开始索引和结束索引相同，即子串长度为1，那么一定是回文
                if (i == j) dp[i][j] = true;
                // 如果子串长度为2，那么只需要检查两个字符是否相同
                else if (j - i == 1)  dp[i][j] = (s.charAt(i) == s.charAt(j));
                // 如果子串长度大于2，那么需要检查去掉首尾字符后子串是否为回文，
                // 并且首尾字符相同
                else dp[i][j] = (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j));
                // 如果当前子串是回文，那么结果res加1
                if (dp[i][j]) res++;
            }
        }
        // 返回回文子串的总数
        return res;
    }
}

最长回文子序列

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

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

示例 1：

输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

题目解析

状态转移方程式：dp[i][j] 表示区间 [i,j] 内的回文子序列的长度，如果区间端点 s[i] 和 s[j] 相等，则说明这两个端点属于回文子序列中的一部分，即 dp[i][j] = dp[i + 1][j - 1] + 2；否则要么包含 s[i]，要么包含 s[j]，取最大即可，也就是 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
容器规模：i 和 j 的范围均为 [0,length - 1]
base case：i == j 和 i + 1==j 的时候。依赖关系如下任何区间 (i, j) 最终都会依赖值对角线的值上（蓝色和黄色的格子），因此 i==j 和 i+1==j 是basecase。当 i==j 的时候，dp[i][j] 表示的是只有一个字符，dp[i][j]=1；当 i + 1==j 的时候，dp[i][j] 表示的是两个连续的字符，因此 dp[i][j] 是取决于 s[i]==s[j]，相等的时候是 2，不等则为 1。
填表顺序：先遍历 j，再遍历 i，i 逆序遍历。（这样才可以保证我们填表的时候依赖的值已经填好了）

代码展示

class Solution {
    
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        
        // dp[i][j]表示字符串s从索引i到j的子串的最长回文子序列长度
        int[][] dp = new int[n][n];
        
        // 使用两层循环遍历字符串s，外层循环固定子串的结束索引j
        for (int j = 0 ; j < n ; j++) {
            // 内层循环从j向开始遍历，固定子串的开始索引i
            for (int i = j ; i >= 0 ; i--) {
                // 如果子串只有一个字符，则最长回文子序列长度为1
                if (i == j) dp[i][j] = 1;
                // 如果子串长度为2，且两个字符相同，则最长回文子序列长度为2
                // 如果两个字符不同，则最长回文子序列长度为1
                else if (i + 1 == j) dp[i][j] = s.charAt(i) == s.charAt(j) ? 2 : 1;
                else {
                    // 如果子串两端的字符相同，则最长回文子序列长度为去掉两端字符后的最长回文子序列长度加2
                    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]);
                }
            }
        }
        
        // 返回dp[0][n - 1]，即整个字符串s的最长回文子序列的长度
        return dp[0][n - 1];
    }
}

计算机基础 > 算法

#算法

算法训练3.2.1 基础DP

https://blog.fulequn.online/2024/05/Article202405181/

作者

Fulequn

发布于

2024年5月18日

许可协议

算法训练3.2.2 背包模型上一篇

算法训练3.1 单调栈自顶向下的动态规划（记忆化搜索）第二部分下一篇