算法训练营day44 | {300.最长递增子序列, 674.最长连续递增序列, 718.最长重复子数组}

第九章动态规划part10，今天正式开始子序列系列。

300. 最长递增子序列

1.1 解题分析

题目要求最长递增子序列，即求数组中的一段区间，如何明确定义这段区间是关键(dp数组含义)。

DP五部曲：

  1. dp数组定义：
    • dp[i]表示 以nums[i]为结尾的最长递增子序列的长度。
  2. 递推公式：
    • 位置i的最长递增子序列等于j从0到 i - 1 各个位置的最长递增子序列 + 1 的最大值
    • 即取 dp[j] + 1 的最大值
    • if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
  3. dp数组初始化：
    • 每一个i，对应的dp[i] 初始都至少为1
  4. 遍历顺序：因为dp[i]是由0 - i-1各个位置的最长递增子序列推导来的，依赖前面的结果，故从前往后
  5. 打印dp数组。

1.2 解题小结

  • 第一遍写题，没注意if判断条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);
            }
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

674. 最长连续递增序列

2.1 解题分析

dp[i]表示以nums[i]为结尾的连续最长递增子序列的长度。和上一题的区别在于要求递增子序列连续，所以就只要比较nums[i]与nums[i - 1]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。

2.2 解题小结

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

718. 最长重复子数组

3.1 解题分析

本题其实是动规解决的经典题目，只要想到用二维数组可以记录两个字符串的所有比较情况，这样就比较好推递推公式了。

DP五部曲：

  1. dp数组定义：
    • dp[i][j] 表示最长重复子数组的长度，i和j分别是？
    • dp[i][j] 以 i - 1结尾的nums1 和以 j - 1 结尾的nums2的最长重复子数组长度
  2. 递推公式：
    • 依据dp[i][j]定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推出来；
    • if(nums[i - 1] == nums[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
  3. dp数组初始化：
    • 因为定义的是 x - 1，二维数组的第一行dp[0][j] 第一列dp[i][0] 都是没有意义的，因为是最长子数组是累加上去的，故初始化为0
  4. 遍历顺序：从前往后。
  5. 打印dp数组。

3.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int result = 0;
        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;
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
}

4. 今日收获

  • 子序列题目，目前接触到的dp数组定义都是以nums[i]为结尾的最长子序列长度。
  • 学习时长：3小时