组合总和IV | LeetCode-377 | 动态规划

发表于 更新于 分类于 ， ， 阅读次数： 阅读次数： 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];
    }
}
-------------本文结束感谢您的阅读-------------