代码随想录 Day44 动规12 LeetCode T300 最长递增子序列 T674 最长连续递增序列 T718 最长重复子数组

前言

本期我们来解决动规的经典题型------  子数组问题

我们还是会使用动规五部曲来解决问题,下面我们仍然列出动规五部曲

1.明确dp数组含义

2.明确dp数组如何推导-递推公式

3.初始化dp数组

4.确定遍历顺序

5.打印dp数组排错

LeetCode T300 最长递增子序列

题目链接:300. 最长递增子序列 - 力扣（LeetCode）

题目思路:

1.明确dp数组含义

这里的dp[i]表示的是以dp[i]为结尾的最长递增子序列的长度

2.明确dp数组如何推导-递推公式

我们知道这里的递增不要求连续,只需要位置在i前面即可,所以我们定义一个j来遍历i前面的元素,这里dp[i]就等于dp[j]+1或者本身或者是dp[j]+1之间的最大值,因为在这个期间我们可以不断的更新dp[i]

3.初始化dp数组

初始化全为1即可

由于单个字母也构成递增子序列,所以长度为1

4.确定遍历顺序

顺序遍历,因为后面的dp值是由前面的推出来的

5.打印dp数组排错

题目代码:

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }
}

LeetCode T674 最长连续递增序列

题目链接:674. 最长连续递增序列 - 力扣（LeetCode）

题目思路:

1.明确dp数组含义

dp[i]表示i为结尾元素的最长连续子数组

2.明确dp数组如何推导-递推公式

dp[i]这里只能由前面一个元素推出来,所以dp[i] = dp[i-1]+1

3.初始化dp数组

仍然初始化为1

4.确定遍历顺序

顺序遍历即可

5.打印dp数组排错

题目代码:

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < dp.length; i++) {
            if (nums[i] > nums[i-1]) {
                dp[i] = dp[i-1] + 1;
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

LeetCode T718 最长重复子数组

题目链接:718. 最长重复子数组 - 力扣（LeetCode）

题目思路:

1.明确dp数组含义

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）

至于为什么是i-1和j-1我会在最后给出解答

2.明确dp数组如何推导-递推公式

dp[i][j] = dp[i-1][j-1] + 1;

为啥是i-1和j-1呢?为啥不是别的呢,我在这里举个例子大家就能理解

假设nums1 = [1,2,3,2,1]

      nums2 = [3,2,1,4,7]

我们这里匹配到i = 4,j=2 他们的前一个状态是两者同时向前一个单位,是同时回退

3.初始化dp数组

dp[i][0]和dp[0][j]都是无意义的,全部初始化为0即可,其他的随便初始化为啥都可以,因为在遍历的过程中会被覆盖的

4.确定遍历顺序

先遍历哪个都行,顺序遍历,因为右下角的元素依赖于左上角元素产生

5.打印dp数组排错

注:这里的dp[i][j]并不是答案,答案在数组中出现,因为这里dp数组的含义是以i-1和j-1结尾的数组a和数组b的最大公共子数组,这里i-1和j-1不一定是最后的结尾位置.

这里dp数组的定义为啥不用i和j呢?

我们思考这样一个问题,如果dp[i][j]定义为以i结尾和以j结尾,那么这里的dp[i][0]就需要遍历一遍数组a,[0][j]需要遍历一遍数组b,这样代码显得冗余了.

题目代码:

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        int res = 0;
        for(int i = 1;i<=nums1.length;i++){
            for(int j = 1;j<=nums2.length;j++){
                if(nums1[i-1] == nums2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
                res = Math.max(res,dp[i][j]);
            }
        }
        return res;
    }
}