神马都会亿点点的毛毛张

一万次悲伤，依然会有Dream

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 7.6k 阅读时长 ≈ 13 分钟
动态规划练习题

题目1：121. 买卖股票的最佳时机

1.题目描述

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

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

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

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • $1 <= prices.length <= 10^5$
  • $0 <= prices[i] <= 10^4$

2.题解

题目2：122. 买卖股票的最佳时机 II

1.题目描述

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

1
2
3
4
5
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

1
2
3
4
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

提示：

  • $1 <= prices.length <= 3 * 10^4$
  • $0 <= prices[i] <= 10^4$

2.题解

题目3：123. 买卖股票的最佳时机 III

1.题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

1
2
3
4
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

1
2
3
4
5
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

1
2
3
输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

1
2
输入：prices = [1]
输出：0

提示：

  • $1 <= prices.length <= 10^5$
  • $0 <= prices[i] <= 10^5$

2.题解

题目4：188. 买卖股票的最佳时机 IV

1.题目描述

2.题解

题目5：309. 买卖股票的最佳时机含冷冻期

1.题目描述

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。

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

  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

1
2
3
输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

1
2
输入: prices = [1]
输出: 0

提示：

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

2.题解

  • 图解：

image-20241015190852283

2.1 动态规划-二维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int maxProfit(int[] prices) {
        // dp数组，用于记录在不同状态下的最大利润
        // dp[i][0] 表示第i天结束时，持有股票的状态
        // dp[i][1] 表示第i天结束时，未持有股票，且未卖出股票的状态
        // dp[i][2] 表示第i天结束时，今天卖出股票的状态
        // dp[i][3] 表示第i天结束时，处于冷冻期的状态（即今天不能买股票的状态）
        int[][] dp = new int[prices.length][4];

        // 初始化第1天的状态
        dp[0][0] = -prices[0]; // 买入股票，成本是prices[0]
        dp[0][1] = 0;          // 第一天未持有股票，且未进行任何操作，所以利润为0
        dp[0][2] = 0;          // 第一天无法卖出，所以利润为0
        dp[0][3] = 0;          // 第一天不可能处于冷冻期，利润为0

        // 从第2天开始更新dp数组
        for(int i = 1; i < prices.length; i++) {
            // 第i天结束时持有股票，可能是前一天已经持有股票（dp[i-1][0]），
            // 或者今天买入股票（从dp[i-1][1]或dp[i-1][3]减去今天的股价）。
            dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][1] - prices[i], dp[i-1][3] - prices[i]));

            // 第i天结束时未持有股票，且未卖出股票的状态，可能是前一天未持有股票（dp[i-1][1]），
            // 或者前一天处于冷冻期（dp[i-1][3]）。
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]);

            // 第i天卖出股票，利润等于前一天持有股票的状态加上今天的股价
            dp[i][2] = dp[i-1][0] + prices[i];

            // 第i天结束时处于冷冻期的状态，意味着前一天卖出了股票（dp[i-1][2]）。
            dp[i][3] = dp[i-1][2];
        }

        // 返回最后一天的最大利润，可以是未持有股票的状态（dp[prices.length-1][1]），
        // 或者今天卖出股票的状态（dp[prices.length-1][2]），
        // 也可以是处于冷冻期的状态（dp[prices.length-1][3]）。
        return Math.max(dp[prices.length-1][1], Math.max(dp[prices.length-1][2], dp[prices.length-1][3]));
    }
}

2.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
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // 使用滚动数组优化空间复杂度，将原本的dp数组简化为只有2行
        // dp[i % 2][0] 表示第i天结束时，持有股票的状态
        // dp[i % 2][1] 表示第i天结束时，未持有股票，且未卖出股票的状态
        // dp[i % 2][2] 表示第i天结束时，今天卖出股票的状态
        // dp[i % 2][3] 表示第i天结束时，处于冷冻期的状态
        int[][] dp = new int[2][4];

        // 初始化第1天的状态
        dp[0][0] = -prices[0]; // 买入股票，成本是prices[0]
        dp[0][1] = 0;          // 第一天未持有股票，且未进行任何操作，所以利润为0
        dp[0][2] = 0;          // 第一天无法卖出股票，利润为0
        dp[0][3] = 0;          // 第一天不可能处于冷冻期，利润为0

        // 从第2天开始更新dp数组
        for (int i = 1; i < n; i++) {
            // 使用滚动数组，dp[i % 2] 表示第i天的状态，dp[(i - 1) % 2] 表示第i-1天的状态
            // 第i天结束时持有股票，可能是前一天已经持有股票（dp[(i - 1) % 2][0]），
            // 或者今天买入股票（从dp[(i - 1) % 2][1]或dp[(i - 1) % 2][3]减去今天的股价）。
            dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0],
                    Math.max(dp[(i - 1) % 2][1] - prices[i], dp[(i - 1) % 2][3] - prices[i]));

            // 第i天结束时未持有股票，且未卖出股票，可能是前一天未持有股票（dp[(i - 1) % 2][1]），
            // 或者前一天处于冷冻期（dp[(i - 1) % 2][3]）。
            dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][3]);

            // 第i天卖出股票，利润等于前一天持有股票的状态加上今天的股价。
            dp[i % 2][2] = dp[(i - 1) % 2][0] + prices[i];

            // 第i天处于冷冻期，意味着前一天卖出了股票（dp[(i - 1) % 2][2]）。
            dp[i % 2][3] = dp[(i - 1) % 2][2];
        }

        // 返回最后一天的最大利润，可以是未持有股票的状态（dp[(n - 1) % 2][1]），
        // 或者今天卖出股票的状态（dp[(n - 1) % 2][2]），
        // 也可以是处于冷冻期的状态（dp[(n - 1) % 2][3]）。
        return Math.max(dp[(n - 1) % 2][1], Math.max(dp[(n - 1) % 2][2], dp[(n - 1) % 2][3]));
    }
}

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
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // dp数组用来记录四种状态下的最大利润
        // dp[0] 表示持有股票的状态
        // dp[1] 表示未持有股票且未卖出股票的状态
        // dp[2] 表示今天卖出股票的状态
        // dp[3] 表示处于冷冻期的状态
        int[] dp = new int[4];

        // 初始化第1天的状态
        dp[0] = -prices[0]; // 买入股票，成本是prices[0]
        dp[1] = 0;          // 第一天未持有股票，且未进行任何操作，利润为0
        dp[2] = 0;          // 第一天不能卖出股票，利润为0
        dp[3] = 0;          // 第一天不可能处于冷冻期，利润为0

        // 从第2天开始更新dp数组
        for (int i = 1; i < n; i++) {
            // 临时保存上一天的dp[0]和dp[2]的值，用于计算新的状态
            int temp1 = dp[0]; // 昨天持有股票的状态
            int temp2 = dp[2]; // 昨天卖出股票的状态

            // 计算今天持有股票的状态，可能是昨天已经持有股票(dp[0])，
            // 或者今天买入股票（从未持有状态dp[1]或冷冻期dp[3]减去今天的股价）。
            dp[0] = Math.max(dp[0], Math.max(dp[1] - prices[i], dp[3] - prices[i]));

            // 计算今天未持有股票且未卖出的状态，可能是昨天未持有股票(dp[1])，
            // 或者昨天处于冷冻期(dp[3])。
            dp[1] = Math.max(dp[1], dp[3]);

            // 计算今天卖出股票的状态，等于昨天持有股票的状态加上今天的股价。
            dp[2] = temp1 + prices[i];

            // 计算今天处于冷冻期的状态，等于昨天卖出股票的状态。
            dp[3] = temp2;
        }

        // 返回最后一天的最大利润，可能是未持有股票的状态(dp[1])，
        // 或者今天卖出股票的状态(dp[2])，或者处于冷冻期的状态(dp[3])。
        return Math.max(dp[1], Math.max(dp[2], dp[3]));
    }
}

题目6：714. 买卖股票的最佳时机含手续费

1.题目描述

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

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

返回获得利润的最大值。

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

示例 1：

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

示例 2：

1
2
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

  • $1 <= prices.length <= 5 * 10^4$
  • $1 <= prices[i] < 5 * 10^4$
  • $0 <= fee < 5 * 10^4$

2.题解

2.1 动态规划-二维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int maxProfit(int[] prices, int fee) {
        // 定义dp数组，其中dp[i][0]表示第i天持有股票的状态下的最大利润
        // dp[i][1]表示第i天未持有股票的状态下的最大利润
        int[][] dp = new int[prices.length][2];

        // 初始化第1天的状态
        dp[0][0] = -prices[0]; // 第一天买入股票，初始利润为 -prices[0]
        dp[0][1] = 0;          // 第一天没有卖出股票，利润为0

        // 从第2天开始计算每一天的最大利润
        for (int i = 1; i < prices.length; i++) {
            // 第i天持有股票的最大利润：
            // 1. 可以选择不买入，保持前一天持有股票的状态（dp[i-1][0]）
            // 2. 也可以选择今天买入股票（前一天未持有股票的利润减去今天的股价：dp[i-1][1] - prices[i]）
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);

            // 第i天未持有股票的最大利润：
            // 1. 可以选择不卖出，保持前一天未持有股票的状态（dp[i-1][1]）
            // 2. 也可以选择今天卖出股票（前一天持有股票的利润加上今天的股价，减去交易费：dp[i-1][0] + prices[i] - fee）
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }

        // 最终返回的是最后一天未持有股票的最大利润，即dp[prices.length - 1][1]
        return dp[prices.length - 1][1];
    }
}

2.2 动态规划-二维数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[2][2];

        // 初始化第1天的状态
        dp[0][0] = -prices[0]; // 第一天买入股票，初始利润为 -prices[0]
        dp[0][1] = 0;          // 第一天没有卖出股票，利润为0

        // 从第2天开始计算每一天的最大利润
        for (int i = 1; i < n; i++) {
            dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
            dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i] - fee);
        }

        return dp[(n - 1) % 2][1];
    }
}

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
class Solution {
    public int maxProfit(int[] prices, int fee) {
        // 定义dp数组，其中dp[0]表示持有股票时的最大利润
        // dp[1]表示未持有股票时的最大利润
        int[] dp = new int[2];

        // 初始化第1天的状态
        dp[0] = -prices[0]; // 第一天买入股票，初始利润为 -prices[0]
        dp[1] = 0;          // 第一天没有卖出股票，利润为0

        // 从第2天开始计算每一天的最大利润
        for (int i = 1; i < prices.length; i++) {
            // 第i天持有股票的最大利润：
            // 1. 可以选择不买入，保持前一天持有股票的状态（dp[0]）
            // 2. 也可以选择今天买入股票，前一天未持有股票的利润减去今天的股价（dp[1] - prices[i]）
            dp[0] = Math.max(dp[0], dp[1] - prices[i]);

            // 第i天未持有股票的最大利润：
            // 1. 可以选择不卖出，保持前一天未持有股票的状态（dp[1]）
            // 2. 也可以选择今天卖出股票，前一天持有股票的利润加上今天的股价，减去交易费（dp[0] + prices[i] - fee）
            dp[1] = Math.max(dp[1], dp[0] + prices[i] - fee);
        }

        // 最终返回的是最后一天未持有股票的最大利润，即dp[1]
        return dp[1];
    }
}

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 24k 阅读时长 ≈ 40 分钟
动态规划练习题

题目1：300. 最长递增子序列

1.题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

2.题解

2.1 动态规划-错解

  • 这样求解的是以nums[nums.length-1]结尾的最长递增子序列的长度，题目要求的是全局的，最后一个不一定是全局最长递增子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);

        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i] > nums[j]) dp[i] = Math.max(dp[i],dp[j] + 1);
            }
        }
        return dp[n-1];
    }
}

2.2 动态规划-正解

  • 思路：
    • 初始化：创建一个长度与输入数组相同的动态规划数组 dp，每个元素初始化为1。这表示每个元素至少可以构成长度为1的递增子序列（即它自身）。
    • 遍历：从数组的第二个元素开始，对每个元素进行遍历。
    • 比较：对于当前遍历到的元素，与它之前的所有元素进行比较。
    • 更新：如果当前元素比前面的元素大，说明有潜力构成更长的递增子序列。更新 dp 数组，dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。
    • 记录：在更新 dp 数组的同时，记录下遍历过程中找到的最长递增子序列的长度。
    • 返回结果：遍历结束后，dp 数组中的最大值即为整个数组的最长递增子序列的长度。
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
class Solution {
    public int lengthOfLIS(int[] nums) {
        // 获取数组的长度
        int n = nums.length;
        // 创建一个长度与nums相同的数组，用于动态规划
        int[] dp = new int[n];
        // 初始化dp数组，每个元素的值都设为1
        Arrays.fill(dp,1);
        // 初始化结果变量，用于记录最长递增子序列的长度
        int result = 1;

        // 遍历数组，从第二个元素开始
        for(int i=1;i<n;i++){
            // 对于每个元素nums[i]，遍历其之前的所有元素
            for(int j=0;j<i;j++){
                // 如果当前元素大于之前的元素nums[j]，则更新dp[i]的值
                // dp[i]表示以nums[i]结尾的最长递增子序列的长度
                if(nums[i] > nums[j]) dp[i] = Math.max(dp[i],dp[j] + 1);
            }
            // 更新结果变量，记录遍历过程中找到的最长递增子序列的长度
            result = Math.max(dp[i],result);
        }
        // 返回结果变量，即整个数组的最长递增子序列的长度
        return result;
    }
}

2.3 贪心 + 二分查找

  • 核心逻辑：
    1. 使用 dp 数组来存储递增子序列的最小结尾元素，以此动态更新递增子序列的长度。
    2. 每次遍历新元素时，如果新元素比当前最长递增子序列的末尾元素大，直接将其追加在 dp 的末尾；否则通过二分查找找到一个可以替换的元素，保持 dp 中递增子序列的最小性。
    3. 最终，result 记录了最长递增子序列的长度。
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
class Solution {
    public int lengthOfLIS(int[] nums) {
        // 获取数组长度
        int n = nums.length;
        // 用于记录最长递增子序列的长度
        int result = 1;
        // 动态规划数组，dp[i] 表示长度为 i 的递增子序列的末尾元素的最小值
        int[] dp = new int[n + 1];
        // 初始化 dp 数组的第一个元素为 nums[0]
        dp[result] = nums[0];

        // 遍历数组中的每一个元素
        for(int i = 1; i < n; i++) {
            // 如果当前元素大于 dp 中已知的最长递增子序列的最后一个元素
            if(nums[i] > dp[result]) {
                // 递增子序列的长度加 1
                result += 1;
                // 更新 dp 数组，记录新的最长递增子序列的最后一个元素
                dp[result] = nums[i];
            } else {
                // 如果当前元素小于或等于 dp 中已知的最长递增子序列的最后一个元素，
                // 我们需要找到 dp 中大于等于 nums[i] 的最小元素进行替换，以维持 dp 的有序性
                int left = 1, right = result, pos = 0;

                // 进行二分查找，找到第一个大于等于 nums[i] 的位置
                while(left <= right) {
                    int mid = left + (right - left) / 2;
                    // 找到 dp 中大于等于 nums[i] 的最靠左的元素的索引
                    if(nums[i] <= dp[mid]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                // 使用 nums[i] 更新 dp 数组中第一个大于等于它的位置
                dp[left] = nums[i];
            }
        }
        // 返回最长递增子序列的长度
        return result;
    }
}

  • 实例打印：

    • 输入：{1, 2, 3, 5, 6, 4}

    • 输出dp数组：

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

题目2：674. 最长连续递增序列

1.题目描述

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

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

示例 1：

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

示例 2：

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

提示：

  • $1 <= nums.length <= 10^4$
  • $-10^9 <= nums[i] <= 10^9$

2.题解

2.1 动态规划

  • 思路：
    • dp[i] 表示以 nums[i] 结尾的最长连续递增子序列长度。
    • 遍历数组，每次遇到比前一个元素大的数时，将当前 dp[i] 更新为 dp[i-1] + 1，否则保持不变。
    • 最终返回 result，即数组中的最长连续递增子序列长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        // 获取数组的长度
        int n = nums.length;
        // 动态规划数组 dp，dp[i] 表示以 nums[i] 结尾的最长连续递增子序列的长度
        int[] dp = new int[n];
        // 结果变量 result 用于存储最长连续递增子序列的长度，初始化为 1，因为最短子序列长度为 1
        int result = 1;
        // 初始化 dp 数组，所有元素的初始值都是 1，因为单个元素也是长度为 1 的递增子序列
        Arrays.fill(dp, 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; // 将 dp[i] 更新为 dp[i-1] 加 1
            // 更新结果 result，取 result 和 dp[i] 的最大值
            result = Math.max(result, dp[i]);
        }
        // 返回最终结果，即最长连续递增子序列的长度
        return result;
    }
}

2.2 贪心算法 & 双指针 & 滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        // 贪心算法 & 双指针 & 滑动窗口方法
        // 左指针初始化为数组的第一个位置
        int left = 0;
        // 结果变量 result，用于存储最长连续递增子序列的长度
        int result = 0;
        // 右指针从数组的第一个元素开始遍历
        for(int right = 0; right < nums.length; right++) {
            // 如果当前元素小于或等于前一个元素，重置左指针到当前元素位置
            // 这是因为连续递增子序列必须是严格递增的
            if(right > 0 && nums[right] <= nums[right - 1]) 
                left = right;
            // 更新结果 result，计算当前窗口（从 left 到 right）的长度并取最大值
            result = Math.max(result, right - left + 1);
        }
        // 返回最长连续递增子序列的长度
        return result;
    }
}

题目3：718. 最长重复子数组

1.题目描述

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

示例 1：

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

示例 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

2.题解

2.1 暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        //暴力解法
        int n = nums1.length;
        int m = nums2.length;
        int result = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(nums1[i] == nums2[j]){
                    int subLength = 1;
                    while(i + subLength < n && j + subLength < m && nums1[i+ subLength] == nums2[j + subLength]){
                        subLength++;
                    }
                    result = Math.max(subLength,result);
                }
            }
        }
        return result;
    }
}

2.2 动态规划-二维数组

  • 思路：
    • 二维动态规划：定义 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长重复子数组的长度。
    • 状态转移方程：如果 nums1[i-1] == nums2[j-1]，那么 dp[i][j] = dp[i-1][j-1] + 1，表示当前两个数组的元素相等，长度可以在之前的基础上加 1。
    • 结果维护：每次更新 dp[i][j] 时，比较当前最长的重复子数组长度 result，并存储最大的长度。
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
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // 动态规划 - 使用二维数组
        // n 表示 nums1 的长度，m 表示 nums2 的长度
        int n = nums1.length;
        int m = nums2.length;
        // dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长重复子数组的长度
        // 使用 n+1 和 m+1 来处理边界情况，即考虑当 i 或 j 为 0 时的状态，dp[0][*] 或 dp[*][0] 默认初始化为 0
        int[][] dp = new int[n + 1][m + 1];
        // 初始化最长重复子数组的长度为 0
        int result = 0;
        // 遍历 nums1 和 nums2，填充 dp 数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; 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;
                }
                // 每次更新 result，保存当前最长的子数组长度
                result = Math.max(result, dp[i][j]);
            }
        }
        // 返回最长重复子数组的长度
        return result;
    }
}

题目4：1143. 最长公共子序列

1.题目描述

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

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

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

2.题解

2.1 动态规划-二维数组

  • 思路：
    • 动态规划二维表：dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。
    • 状态转移方程：
      • 如果当前字符相同（text1[i-1] == text2[j-1]），则 dp[i][j] = dp[i-1][j-1] + 1，表示在前一个状态基础上增加一个相同字符。
      • 如果当前字符不同，则 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])，表示取不相等情况下的最大公共子序列长度。
    • 结果维护：在遍历过程中，每次计算出 dp[i][j] 后，将其与 result 比较并更新，确保 result 保持为当前最大值。
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
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 获取 text1 和 text2 的长度
        int n = text1.length();
        int m = text2.length();

        // 初始化 result 变量，用于保存最终最长公共子序列的长度
        int result = 0;

        // 定义 dp 二维数组，dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度
        // dp[0][*] 和 dp[*][0] 初始化为 0，表示空字符串与其他字符串的最长公共子序列长度为 0
        int[][] dp = new int[n + 1][m + 1];

        // 双层循环遍历 text1 和 text2 的所有字符
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 取出当前遍历的字符
                char c1 = text1.charAt(i - 1); // text1 的第 i 个字符
                char c2 = text2.charAt(j - 1); // text2 的第 j 个字符

                // 如果两个字符相同，则最长公共子序列可以在 dp[i-1][j-1] 的基础上加 1
                if (c1 == c2)
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    // 如果两个字符不相同，则最长公共子序列等于 dp[i-1][j] 和 dp[i][j-1] 的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

                // 更新 result，保存最长的公共子序列长度
                result = Math.max(result, dp[i][j]);
            }
        }

        // 返回结果，即最长公共子序列的长度
        return result;
    }
}

题目5：1035. 不相交的线

1.题目描述

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

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

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

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

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

示例 1：

img 
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

示例 3：

1
2
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2

提示：

  • 1 <= nums1.length, nums2.length <= 500
  • 1 <= nums1[i], nums2[j] <= 2000

2.题解

2.1 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 此问题可以转化为经典的最长公共子序列（LCS）问题
        // nums1 和 nums2 分别表示两个数组
        // n 和 m 分别表示 nums1 和 nums2 的长度
        int n = nums1.length;
        int m = nums2.length;
        
        // 创建一个大小为 (n+1) x (m+1) 的二维数组 dp，用于存储中间计算结果
        // dp[i][j] 表示在 nums1 的前 i 个元素和 nums2 的前 j 个元素中，最长的公共子序列长度
        int[][] dp = new int[n+1][m+1];
        
        // 结果变量 result 用于存储最终的最长不相交线的长度
        int result = 0;

        // 使用动态规划填充 dp 表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; 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;
                } else {
                    // 否则，dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大者
                    // 即选择不加入当前元素时的最长子序列长度
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
                
                // 更新结果，保持 result 为当前遇到的最大公共子序列长度
                result = Math.max(result, dp[i][j]);
            }
        }

        // 返回最终的最长不相交线的长度
        return result;
    }
}

题目变体：

1. 限制连接的距离

  • 问题变形：要求两条线段（元素之间的匹配）之间的距离不能超过 k（即 nums1[i] 和 nums2[j] 匹配时，|i - j| <= k）。
  • 解法：在原有的动态规划方案基础上，增加对距离的限制。也就是在计算 dp[i][j] 时，只有满足 |i - j| <= k 的情况下，才能更新 dp[i][j]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n+1][m+1];
        int result = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = Math.max(1, i - k); j <= Math.min(m, i + k); 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]);
                }
                result = Math.max(result, dp[i][j]);
            }
        }
        return result;
    }
}

变动点：在双重循环里，对 j 进行了限制，使得它只能在 i - k 和 i + k 范围内搜索。

2. 最小化交叉线的数量

  • 问题变形：要求不仅要计算不相交的线数，还要求最小化交叉线的数量。
  • 解法：将问题从最大化不相交线的数量转换为最小化交叉线。可以通过增加一个计数器来记录交叉线的数量，并基于 dp 的方式，在更新 dp[i][j] 时记录那些产生交叉的情况。

解法思路：将匹配的路径记录下来，交叉线可以根据路径上的线段是否互相交叉来判断。

3. 给定匹配值的不同权重

  • 问题变形：两个数组中的元素匹配时，有不同的权重，要求最大化匹配线段的权重和，而不仅仅是匹配的数量。
  • 解法：在 dp 数组中存储权重和而不是匹配的数量。当 nums1[i-1] == nums2[j-1] 时，不是简单地加 1，而是加上它们的匹配权重值（可以提前给定的权重函数）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxWeightedUncrossedLines(int[] nums1, int[] nums2, int[][] weights) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n+1][m+1];
        int result = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i-1] == nums2[j-1]) {
                    // 使用给定的权重值代替简单的 +1
                    dp[i][j] = dp[i-1][j-1] + weights[nums1[i-1]][nums2[j-1]];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
                result = Math.max(result, dp[i][j]);
            }
        }
        return result;
    }
}

变动点：这里加入了 weights 矩阵，代表不同元素匹配的权重，动态规划时会选择权重和最大的匹配方案。

4. 不允许某些特定匹配

  • 问题变形：要求有些元素不能匹配，例如给定一组禁用的匹配对 (x, y)，nums1 中的元素 x 不能和 nums2 中的元素 y 匹配。
  • 解法：在进行动态规划时，提前将这些禁止的匹配对存入一个哈希表，在判断 nums1[i-1] 和 nums2[j-1] 是否相等时，同时检查它们是否在禁用对中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2, Set<Pair<Integer, Integer>> bannedPairs) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n+1][m+1];
        int result = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                Pair<Integer, Integer> pair = new Pair<>(nums1[i-1], nums2[j-1]);
                if (nums1[i-1] == nums2[j-1] && !bannedPairs.contains(pair)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
                result = Math.max(result, dp[i][j]);
            }
        }
        return result;
    }
}

变动点：增加一个禁用匹配对的集合，在动态规划时排除不允许的匹配。

5. 求解两数组中部分元素的最大不相交线

  • 问题变形：不是要求整个数组，而是要求找出两个子数组（或从原数组中任意挑选的若干元素）之间的最大不相交线数。
  • 解法：在原有的 dp 方法基础上，可以额外维护一个可以选择的元素集合或对两数组进行部分切割，动态规划求解部分区间的最长公共子序列。

题目6：53. 最大子数组和

1.题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

示例 1：

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

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • $1 <= nums.length <= 10^5$
  • $-10^4 <= nums[i] <= 10^4$

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

2.题解

2.1 暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        //暴力解法
        int result = Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            int sum = 0;
            for(int j=i;j<nums.length;j++){
                sum += nums[j];
                result = Math.max(result,sum);
            }
        }
        return result;
    }
}

2.2 贪心算法

  • 思路：
    • 在遍历数组的过程中，维护一个当前子数组的和 sum。
    • 每次将当前元素加入到 sum 中，如果 sum 变为负数，则抛弃当前的子数组（即重置 sum 为 0），因为负数只会减少后续子数组的和。
    • 同时在每一步更新记录最大子数组和的变量 result，确保记录遍历到的最大子数组和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxSubArray(int[] nums) {
        // 初始化结果为整数的最小值，表示子数组的最大和
        int result = Integer.MIN_VALUE;
        // 初始化当前子数组的和为0
        int sum = 0;

        // 遍历数组
        for(int i = 0; i < nums.length; i++) {
            // 将当前元素加入当前子数组的和
            sum += nums[i];
            // 更新最大子数组的和，比较当前的和与之前记录的最大值
            result = Math.max(result, sum);
            // 如果当前子数组的和为负数，则将和重置为0（贪心策略：负数会降低后面的和）
            sum = Math.max(sum, 0);
        }
        // 返回最大子数组和
        return result;
    }
}

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
class Solution {
    public int maxSubArray(int[] nums) {
        // 定义 dp 数组，dp[i] 表示以第 i 个元素结尾的子数组的最大和
        int[] dp = new int[nums.length];
        // 初始化 dp[0]，即以第一个元素结尾的子数组最大和就是该元素本身
        dp[0] = nums[0];
        // 初始化 result，保存最终结果，初始值为第一个元素
        int result = nums[0];
        // 从第二个元素开始遍历数组
        for (int i = 1; i < nums.length; i++) {
            // 状态转移方程：dp[i] 表示以 nums[i] 结尾的最大子数组和
            // 选择要么将当前元素 nums[i] 加入前面的子数组（即 dp[i-1] + nums[i]），
            // 要么以当前元素 nums[i] 开始一个新的子数组，取两者中的最大值
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            // 更新 result，确保 result 始终存储全局的最大子数组和
            if (dp[i] > result) {
                result = dp[i];
            }
        }
        // 返回最大子数组和
        return result;
    }
}

题目7：392. 判断子序列

1.题目描述

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

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

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

1
2
输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

1
2
输入：s = "axc", t = "ahbgdc"
输出：false

提示：

  • 0 <= s.length <= 100
  • $0 <= t.length <= 10^4$
  • 两个字符串都只由小写字符组成。

2.题解

  • 这个道题目是最长公共子序列的变体

2.1 双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isSubsequence(String s, String t) {
        // 获取 s 和 t 的长度
        int n = s.length();
        int m = t.length();
        
        // 定义双指针：left 指向 s，right 指向 t
        int left = 0, right = 0;
        
        // 当两个指针都没有越界时，继续循环
        while (left < n && right < m) {
            // 如果 s[left] 与 t[right] 匹配，left 前进，查找 s 中下一个字符
            if (s.charAt(left) == t.charAt(right)) {
                left++;
            }
            // right 指针总是前进，用来遍历 t
            right++;
        }
        
        // 如果 left 达到了 s 的末尾，说明 s 是 t 的子序列
        return left == n;
    }
}

2.2 动态规划

  • 动态规划表 dp 的定义：
    • dp[i][j] 表示 t 的前 i 个字符和 s 的前 j 个字符的最长公共子序列的长度。
    • 核心是通过逐步填充 dp 表，来判断 s 是否可以作为 t 的子序列。
  • 状态转移：
    • 如果 t[i-1] == s[j-1]，那么当前字符相等，最长公共子序列的长度增加 1，即 dp[i][j] = dp[i-1][j-1] + 1。
    • 如果 t[i-1] != s[j-1]，那么最长公共子序列的长度保持不变，即 dp[i][j] = dp[i-1][j]。
  • 结果判断：
    • 最后判断 dp[n][m] == m 是否成立。如果 dp[n][m] 等于 m，说明 s 的所有字符都可以在 t 中按顺序找到，即 s 是 t 的子序列，返回 true；否则返回 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
class Solution {
    public boolean isSubsequence(String s, String t) {
        // 获取字符串 t 和 s 的长度
        int n = t.length();
        int m = s.length();

        // dp[i][j] 表示 t 的前 i 个字符和 s 的前 j 个字符的最长公共子序列的长度
        int[][] dp = new int[n + 1][m + 1];

        // 遍历 t 的每个字符
        for (int i = 1; i <= n; i++) {
            // 遍历 s 的每个字符
            for (int j = 1; j <= m; j++) {
                // 获取 t 中的第 i-1 个字符和 s 中的第 j-1 个字符
                char ct = t.charAt(i - 1);
                char cs = s.charAt(j - 1);

                // 如果两个字符相等，说明它们可以加入到最长公共子序列
                if (ct == cs)
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                // 否则最长公共子序列的长度保持不变，丢弃 t 的当前字符
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }

        // 判断最长公共子序列的长度是否等于 s 的长度
        return dp[n][m] == m;
    }
}

题目8：115. 不同的子序列

1.题目描述

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

image-20241020120035127

示例 2：

image-20241020120051444

提示：

  • 1 <= s.length, t.length <= 1000
  • s 和 t 由英文字母组成

2.题解

2.1 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int numDistinct(String s, String t) {
        int n = s.length(); // 获取字符串 s 的长度
        int m = t.length(); // 获取字符串 t 的长度

        // dp[i][j] 表示 s 的前 i 个字符中出现 t 的前 j 个字符的子序列个数
        int[][] dp = new int[n + 1][m + 1];

        // 初始化：当 t 为空串时，无论 s 是什么，结果都是 1，因为空串是任何字符串的子序列
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        // 动态规划填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果 s[i-1] 与 t[j-1] 相等，可以选择匹配它们或者不匹配
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // dp[i-1][j-1] 表示匹配 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-1]，保持 dp[i-1][j]
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        // 最终结果是 dp[n][m]，即 s 的前 n 个字符中出现 t 的前 m 个字符的子序列个数
        return dp[n][m];
    }
}

2.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
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int numDistinct(String s, String t) {
        int n = s.length();
        int m = t.length();
        
        // 初始化一个二维数组来缓存递归结果，-1 表示尚未计算过
        int[][] memo = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                memo[i][j] = -1;
            }
        }
        
        // 调用递归函数
        return dfs(s, t, n, m, memo);
    }
    
    // 递归函数，计算 s 的前 i 个字符中有多少个子序列等于 t 的前 j 个字符
    private int dfs(String s, String t, int i, int j, int[][] memo) {
        // 如果 t 是空串，空串是任何字符串的子序列，返回 1
        if (j == 0) return 1;
        
        // 如果 s 是空串且 t 不是空串，不可能匹配，返回 0
        if (i == 0) return 0;
        
        // 如果已经计算过，直接返回缓存的结果
        if (memo[i][j] != -1) return memo[i][j];
        
        // 递归计算
        if (s.charAt(i - 1) == t.charAt(j - 1)) {
            // 如果当前字符匹配，既可以匹配当前字符，也可以跳过当前字符
            memo[i][j] = dfs(s, t, i - 1, j - 1, memo) + dfs(s, t, i - 1, j, memo);
        } else {
            // 如果当前字符不匹配，只能跳过当前字符
            memo[i][j] = dfs(s, t, i - 1, j, memo);
        }
        
        // 返回计算结果
        return memo[i][j];
    }
}

题目8：583. 两个字符串的删除操作

1.题目描述

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

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

示例 1：

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

示例 2:

1
2
输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

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

2.题解

2.1 动态规划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
class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(); // 获取 word1 的长度
        int m = word2.length(); // 获取 word2 的长度
        // dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作次数
        int[][] dp = new int[n + 1][m + 1];
        //初始化
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int i = 0; i <= m; i++) dp[0][i] = i;
        // 填充 dp 表格
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果当前字符相等，则不需要进行任何操作，dp[i][j] 等于 dp[i-1][j-1]
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 如果当前字符不相等，选择三种操作中最小的
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));
                }
            }
        }

        // 返回将 word1 转换为 word2 所需的最少操作次数
        return dp[n][m];
    }
}

2.2 动态规划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
29
class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(); // 获取 word1 的长度
        int m = word2.length(); // 获取 word2 的长度

        // dp[i][j] 表示 word1 的前 i 个字符和 word2 的前 j 个字符之间的最长公共子序列长度
        int[][] dp = new int[n + 1][m + 1];
        int result = 0; // 用来记录最长公共子序列的长度
        // 遍历 word1 和 word2 的每个字符，填充 dp 表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果当前字符相等，则最长公共子序列长度可以在前一个基础上 +1
                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]);
                }

                // 更新最长公共子序列的长度
                result = Math.max(result, dp[i][j]);
            }
        }

        // 最少操作次数 = 两个字符串的长度之和 - 2 * 最长公共子序列的长度
        // 原因：最少操作次数等于将不属于最长公共子序列的字符删除，并插入到正确位置上
        return n + m - result * 2;
    }
}

题目9：72. 编辑距离

1.题目描述

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

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

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

示例 1：

1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

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')

提示：

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

2.题解

2.1 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(); // 获取 word1 的长度
        int m = word2.length(); // 获取 word2 的长度
        // dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作次数
        int[][] dp = new int[n + 1][m + 1];
        // 初始化：将 word1 的前 i 个字符转换为空字符串，所需的操作次数是 i（全部删除）
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        // 初始化：将空字符串转换为 word2 的前 j 个字符，所需的操作次数是 j（全部插入）
        for (int i = 0; i <= m; i++) dp[0][i] = i;
        // 填充 dp 表格
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果当前字符相等，则不需要进行任何操作，dp[i][j] 等于 dp[i-1][j-1]
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 如果当前字符不相等，选择三种操作中最小的：
                    //dp[i - 1][j] + 1 删除操作
                    //dp[i][j - 1] + 1 增加操作
                    //dp[i-1][j-1] + 1 替换操作
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1,dp[i-1][j-1] + 1));
                }
            }
        }

        // 返回将 word1 转换为 word2 所需的最少操作次数
        return dp[n][m];
    }
}

题目10：647. 回文子串

1.题目描述

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

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

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

示例 1：

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

示例 2：

1
2
3
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

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

2.题解

2.1 动态规划

  • 思路解析：
  1. 回文子串的定义：
    • 回文子串是一个正读和反读都相同的子字符串。
    • 例如：在字符串 “abcba” 中，”a”、”b”、”c”、”bcb”、”abcba” 都是回文子串。
  2. 动态规划的状态定义：
    • 创建一个二维数组 dp[i][j]，其中 i 表示子字符串的起始位置，j 表示子字符串的结束位置。dp[i][j] 为 true 表示子字符串 s[i..j] 是一个回文串，false 表示不是回文串。
  3. 转移方程：
    • 如果s[i] == s[j]，那么：
      • 如果 j - i <= 1（即子串长度为 1 或 2），则 s[i..j] 肯定是回文串，直接标记 dp[i][j] = true。
      • 如果 j - i > 1，则需要判断内部的子串 s[i+1..j-1] 是否是回文串。如果 dp[i+1][j-1] == true，那么 s[i..j] 也是回文串。
  4. 遍历顺序：
    • 从右向左遍历字符串 s 的每个字符 i，对于每个 i，遍历其右侧的每个字符 j（j >= i），判断 s[i..j] 是否为回文串。
    • 这种遍历顺序保证了在判断 s[i..j] 是否为回文串时，子串 s[i+1..j-1] 的状态已经被计算出来。
  5. 结果统计：
    • 每当找到一个回文子串（即 dp[i][j] == true），结果 result 加 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int countSubstrings(String s) {
        int n = s.length(); // 获取字符串 s 的长度 n
        boolean[][] dp = new boolean[n][n]; // dp[i][j] 表示 s[i..j] 是否是回文串
        int result = 0; // 存储回文子串的个数
        for (int i = n - 1; i >= 0; i--) { // 从字符串末尾向前遍历每个字符
            for (int j = i; j < n; j++) { // 遍历以 i 开始、以 j 结束的子字符串
                if (s.charAt(i) == s.charAt(j)) { // 如果 s[i] == s[j]
                    if (j - i <= 1) { // 如果子串长度为 1 或 2
                        dp[i][j] = true;
                        result++; // 是回文串，计数加 1
                    } else if (dp[i+1][j-1]) { // 否则检查 s[i+1..j-1] 是否为回文
                        dp[i][j] = true;
                        result++; // 如果 s[i+1..j-1] 是回文，则 s[i..j] 也是回文
                    }
                }
            }
        }
        return result; // 返回回文子串的总个数
    }
}
  • 代码优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int countSubstrings(String s) {
        int n = s.length(); // 获取字符串 s 的长度 n
        boolean[][] dp = new boolean[n][n]; // dp[i][j] 表示 s[i..j] 是否是回文串
        int result = 0; // 存储回文子串的个数
        for (int i = n - 1; i >= 0; i--) { // 从字符串末尾向前遍历每个字符
            for (int j = i; j < n; j++) { // 遍历以 i 开始、以 j 结束的子字符串
                if (s.charAt(i) == s.charAt(j) && (j - i == 1 || dp[i + 1][j - 1])) { // 如果 s[i] == s[j]
                    dp[i][j] = true;
                    result++; // 是回文串，计数加 1
                }
            }
        }
        return result; // 返回回文子串的总个数
    }
}

2.2 双指针

  • 中心扩展法：
    • 对于一个长度为 n 的字符串，有 2n-1 个可能的中心。对于每个字符，它可以作为单字符中心，此外，两个相邻字符之间也可以作为双字符中心。因此有 n 个单字符中心和 n-1 个双字符中心。
  • 双指针：
    • left 和 right 两个指针从中心开始向外扩展，检查左右两侧的字符是否相等。如果相等，则说明找到一个回文子串。
    • i / 2 用于计算左指针，i % 2 用于处理双字符中心的情况。
  • 计数：
    • 每当找到一个回文子串，result 计数器就加 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int countSubstrings(String s) {
        // 使用双指针法，通过中心扩展来计算回文子串数量

        int n = s.length(); // 获取字符串的长度
        int result = 0; // 用于记录回文子串的数量

        // 遍历 2 * n - 1 个中心点
        // 对于长度为 n 的字符串，可以有 n 个单字符中心和 n-1 个双字符中心
        for (int i = 0; i < 2 * n - 1; i++) {
            // 计算当前中心的左边界和右边界
            int left = i / 2; // 左指针指向当前中心的左侧字符
            int right = left + i % 2; // 右指针指向当前中心的右侧字符，取决于是单字符中心还是双字符中心

            // 扩展中心，检查回文
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                result++; // 找到一个回文子串，计数+1
                left--; // 左指针向左扩展
                right++; // 右指针向右扩展
            }
        }

        return result; // 返回找到的回文子串总数
    }
}

题目11：5. 最长回文子串

1. 题目描述

给你一个字符串 s，找到 s 中最长的 回文子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

2.题解

2.1 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n <= 1) return s;  // 如果字符串为空或只有一个字符，直接返回
        
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLength = 1;  // 初始的最长回文长度为1

        // 遍历的顺序：从后往前填充
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = true;  // 单个字符本身就是回文
            
            for (int j = i + 1; j < n; j++) {
                // 判断当前字符是否相同以及内部子串是否是回文
                if (s.charAt(i) == s.charAt(j) && (j - i == 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    
                    int currentLength = j - i + 1;
                    if (currentLength > maxLength) {
                        maxLength = currentLength;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start + maxLength);
    }
}

题目12：516. 最长回文子序列

1.题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

2.题解

2.1 动态规划-二维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // dp[i][j] 表示从字符串 s 的第 i 个字符到第 j 个字符之间的最长回文子序列的长度
        int[][] dp = new int[n][n];

        // 从后向前遍历字符串的每个字符 i
        for (int i = n - 1; i >= 0; i--) {
            // 内部循环从 i 到字符串的末尾 j
            for (int j = i; j < n; j++) {
                // 如果第 i 和第 j 个字符相同
                if (s.charAt(i) == s.charAt(j)) {
                    // 如果 i 和 j 是同一个字符，最长回文子序列的长度为 1
                    if (j == i)
                        dp[i][j] = 1;
                    // 否则，最长回文子序列等于 2 加上去掉当前字符后的回文长度
                    else
                        dp[i][j] = 2 + dp[i + 1][j - 1];
                } else {
                    // 如果 i 和 j 字符不同，则取舍去掉 i 或去掉 j 的情况中较大的回文子序列长度
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        // 返回从字符串第 0 个字符到最后一个字符之间的最长回文子序列长度
        return dp[0][n - 1];
    }
}

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 4.5k 阅读时长 ≈ 7 分钟
动态规划练习题

题目1：198. 打家劫舍

1.题目描述

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

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
29
class Solution {
    // 定义一个公共方法rob，用来计算打劫非相邻房屋可以获得的最大金额
    public int rob(int[] nums) {
        //判断特殊情况
        if (nums == null || nums.length == 0) return 0;
		if (nums.length == 1) return nums[0];

        // 初始化一个动态规划数组dp，长度等于输入数组nums的长度
        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++) {
            // 对于每个房屋i，有两种选择：
            // 1. 不打劫房屋i，那么前一步的最大金额保持不变，即dp[i-1]
            // 2. 打劫房屋i，那么当前的最大金额为前两步的最大金额加上当前房屋的金额，即dp[i-2] + nums[i]
            // 取两种情况下的最大值作为dp[i]的值
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        
        // 返回最后一个房屋的最大金额
        return dp[nums.length - 1];
    }
}

题目2：213. 打家劫舍 II

1.题目描述

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

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

示例 1：

1
2
3
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

1
2
3
4
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

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

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

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
29
30
31
32
33
34
35
36
37
// 定义一个名为 Solution 的类
class Solution {
    // 主方法，用于计算能够偷窃的最大金额
    public int rob(int[] nums) {
        // 如果输入数组为空或长度为0，则表示没有房子可以偷，返回0
        if (nums == null || nums.length == 0) return 0;
        // 如果只有一个房子，直接返回该房子的金额
        if (nums.length == 1) return nums[0];
        
        // 分别计算两种情况下的最大可偷金额：
        // 第一种情况：不偷最后一个房子，从第一个到最后第二个
        int result1 = robRange(nums, 0, nums.length - 2);
        // 第二种情况：不偷第一个房子，从第二个到最后一个
        int result2 = robRange(nums, 1, nums.length - 1);
        // 返回两种情况下较大的金额
        return Math.max(result1, result2);
    }

    // 辅助方法，用于计算从 start 到 end 范围内房间的最大可偷金额
    public int robRange(int[] nums, int start, int end) {
        // 如果开始和结束位置相同，表示只有一个房子，直接返回该房子的金额
        if (start == end) return nums[start];
        // 初始化动态规划数组，长度与输入数组相同
        int[] dp = new int[nums.length];
        // 填充初始条件
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        // 从第三个房子开始遍历
        for (int i = start + 2; i <= end; i++) {
            // 动态规划状态转移方程：当前房子的收益等于前天（i-2）的最大收益加上当前房子的价值，
            // 或者昨天（i-1）的最大收益（即不偷当前房子）
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        // 返回最后一个房子位置处的最大可偷金额
        return dp[end];
    }
}

题目3：337. 打家劫舍 III

1.题目描述

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

img

1
2
3
输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

img

1
2
3
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

  • 树的节点数在 $[1, 10^4]$ 范围内
  • $0 <= Node.val <= 10^4$

2.题解

2.1 递归-超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int rob(TreeNode root) {
        //递归
        if(root == null) return 0;
        int money = root.val;
        if(root.left != null){
            money += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            money += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(money,rob(root.left)+rob(root.right));
    }
}

2.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
class Solution {
    Map<TreeNode,Integer> map = new HashMap<>();
    public int rob(TreeNode root) {
        //递归优化
        if(root == null) return 0;
        if(root.left == null && root.right == null) return root.val;
        if(map.containsKey(root)) return map.get(root);

        //偷父节点
        int money1 = root.val;
        if(root.left != null){
            money1 += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            money1 += rob(root.right.left) + rob(root.right.right);
        }

        //不偷父节点
        int money2 = rob(root.left)+rob(root.right);

        map.put(root,Math.max(money1,money2));
        return Math.max(money1,money2);
    }
}

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
31
32
33
34
35
class Solution {
    /**
     * 主方法，计算以 root 为根的二叉树能抢劫的最大金额。
     * @param root 树的根节点。
     * @return 返回能抢劫的最大金额。
     */
    public int rob(TreeNode root) {
        // 计算从根节点开始的子树抢劫策略
        int[] result = robTree(root);
        // 返回偷或不偷根节点时的最大金额
        return Math.max(result[0], result[1]);
    }

    /**
     * 辅助递归方法，计算从 cur 节点开始的子树的最佳抢劫策略。
     * @param cur 当前节点。
     * @return 返回一个数组，其中 result[0] 是不偷当前节点的最大金额，result[1] 是偷当前节点的最大金额。
     */
    public int[] robTree(TreeNode cur) {
        // 如果当前节点为空，直接返回不偷也不抢的情况
        if (cur == null) return new int[]{0, 0};

        // 递归计算左右子树的抢劫策略
        int[] left = robTree(cur.left);
        int[] right = robTree(cur.right);

        // 偷当前节点，那么它的左右子节点都不能偷
        int money1 = cur.val + left[0] + right[0];
        // 不偷当前节点，那么其左右子节点可以选择偷或不偷
        int money2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        // 返回当前节点的最优策略
        return new int[]{money2, money1};
    }
}