算法训练营day45 | {1143.最长公共子序列, 1035.不相交的线, 53. 最大子序和, 392.判断子序列}

第九章动态规划part11，继续子序列。

1143. 最长公共子序列

1.1 解题分析

dp[i][j]可以由哪几个状态推出来，看这个例子，假设现在i对应”abc”的c，j对应”ace”的e。

abcde
ace

DP五部曲：

  1. dp数组定义：
    • dp[i][j]表示以i - 1结尾的text1和以j - 1结尾的text2的最长公共子序列长度。
  2. 递推公式：
    • if(text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1
    • else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
  3. dp数组初始化：
    • 第一行和第一列在我们这个定义下是没有意义的。依据递推公式初始化为0.
  4. 遍历顺序：从左到右，从上到下。
  5. 打印dp数组。

1.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int x = text1.length() + 1;
        int y = text2.length() + 1;
        int[][] dp = new int[x][y];
        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[x - 1][y - 1];
    }
}

1035. 不相交的线

2.1 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int x = nums1.length + 1;
        int y = nums2.length + 1;
        int[][] dp = new int[x][y];
        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[x-1][y-1];
    }
}

53. 最大子序和

3.1 解题分析

DP五部曲：

  1. dp数组定义：
    • dp[i]表示以i为结尾（nums[i]）的最大子数组和。
  2. 递推公式：
    • dp[i]可以从两个方向推出来
    • 继续累加前面的子数组和 dp[i - 1] + nums[i]
    • 重新开始 nums[i]
  3. dp数组初始化：
    • dp[0] = nums[0]
  4. 遍历顺序：从前往后，并且复用for循环记录最大的结果。
  5. 打印dp数组。

3.2 解题小结

  • 贪心算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution {
        public int maxSubArray(int[] nums) {
            int sum = 0, ans = Integer.MIN_VALUE;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                ans = Math.max(ans, sum);
                if (sum < 0) sum = 0;
            }
            return ans;
        }
    }
  • 动态规划
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
        public int maxSubArray(int[] nums) {
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            int result = dp[0];
            for (int i = 1; i < nums.length; i++) {
                dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
                if (result < dp[i]) result = dp[i];
            }
            return result;
        }
    }

392. 判断子序列

4.1 解题分析

abc
ahbgdc

DP五部曲：

  1. dp数组定义：
    • dp[i][j]表示以i-1为结尾的字符串s 和 以j-1为结尾的字符串t的最长公共子序列长度
  2. 递推公式：
    …(省略)

4.2 解题小结

  • 第一遍解题时，if判断条件写错了，为什么下标是i - 1和j - 1，因为dp[i][j]代表的就是以i-1为结尾的字符串s 和 以j-1为结尾的字符串t。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isSubsequence(String s, String t) {
        int x = s.length() + 1;
        int y = t.length() + 1;
        int[][] dp = new int[x][y];
        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = dp[i][j - 1];
            }
        }
        return dp[x - 1][y - 1] == s.length();
    }
}

4. 今日收获

  • 关于子序列问题dp数组的定义，以及可以由哪些状态推导出来，有一些手感了。
  • 学习时长：2小时
Leetcode > 动态规划
#Java #代码随想录
算法训练营day45 | {1143.最长公共子序列, 1035.不相交的线, 53. 最大子序和, 392.判断子序列}
http://paopaotangzu.xyz/cn/day45_leetcode/
作者
PROTON TANG
发布于
2026年2月5日
许可协议