代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

文章链接：最长递增子序列、最长连续递增序列、最长重复子数组

视频链接：最长递增子序列、最长连续递增序列、最长重复子数组

1. LeetCode 300. 最长递增子序列

1.1 思路

1. 本题是属于子序列系列，同样是动态规划解决的经典的一系列问题。
2. dp 数组及其下标的含义：dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度为 dp[i]
3. 递推公式：设 j 在 [0,i)之间，当 nums[i]>nums[j] 时，nums[i] 可以接在 nums[j] 之后（严格递增时），就相当于 nums[i] 是直接加在 dp[j] 原来的递增子序列后的，此时 dp[i]=dp[j]+1；当 nums[i]<=nums[j] 时，nums[i] 不可以接在 nums[j] 之后，就 dp[i]=dp[i]。因此 dp[i]=Math.max（dp[i]，dp[j]+1）
4. dp 数组的初始化：dp[i] 至少都是 1，意思是至少包含 nums[i]
5. 遍历顺序：这里都依赖前面的元素，因此 i 一定是从左到右遍历，for（int i=1；i<nums.length；i++）为什么从 1 开始？因为 dp[0]=1 没必要求了，肯定为 1。for（int j=0；j<i；j++）遍历所有 nums[j] 的情况和 nums[i] 做比较，j 从前往后还是从后往前呢？其实都可以，只要把 [0,i) 之间都遍历了就可以了。if（nums[i]>nums[j]）dp[i]=Math.max（dp[i]，dp[j]+1）
6. 最终结果存在哪呢？是在 dp 数组的最大值，就遍历 dp 数组，result=Math.max（dp[i]，result），最终返回 result 即可
7. 打印 dp 数组：用于 debug

1.2 代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 0;
        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;
    }
}

2. LeetCode 674. 最长连续递增序列

2.1 思路

1. 本题和300. 最长递增子序列的区别就在于要求连续。
2. dp 数组及其下标的含义：dp 表示以 i 为结尾的最长连续递增子序列为 dp[i]
3. 递推公式：因为本题要求连续，就不需要比较前面所有的元素了，直接比较 nums[i] 和 nums[i-1]，如果 nums[i]>nums[i-1] 就 dp[i]=dp[i-1]+1，就相当于 nums[i] 直接接在了 dp[i-1] 后面了，因此就 dp[i-1]+1
4. dp 数组的初始化：dp 数组全部都初始化为 1，因为每个元素本身就是连续的，就是 1
5. 遍历顺序：因为 i 依赖 i-1，因此是从前往后遍历，for（int i=1；i<nums.length；i++）这里为什么从 1 开始？因为 dp[0] 一定是 1。
6. 最终结果在哪里？是在 dp 数组的最大值中，因此遍历 dp 数组，result=Math.max（dp[i]，result），最终返回 result
7. 打印 dp 数组：用于 debug

2.2 代码

/**
     * 1.dp[i] 代表当前下标最大连续值
     * 2.递推公式 if（nums[i+1]>nums[i]） dp[i+1] = dp[i]+1
     * 3.初始化 都为1
     * 4.遍历方向，从其那往后
     * 5.结果推导 。。。。
     * @param nums
     * @return
     */
    public static int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        int res = 1;
  //可以注意到，這邊的 i 是從 0 開始，所以會出現和卡哥的C++ code有差異的地方，在一些地方會看到有 i + 1 的偏移。
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i + 1] > nums[i]) {
                dp[i + 1] = dp[i] + 1;
            }
            res = res > dp[i + 1] ? res : dp[i + 1];
        }
        return res;
    }

3. LeetCode 718. 最长重复子数组

3.1 思路

1. 求两个数组的最长重复子数组的长度，其实就是求最长连续子序列。
2. dp 数组及其下标的含义：我们用一个二维 dp 数组保存我们两个数组比较的状态。dp[i][j] 表示的是最长重复子数组，第一个数组到 i，第二个数组到 j，最长重复子数组为 dp[i][j]。即 dp[i][j] 表示以 i-1 为结尾的数组 1 和以 j-1 为结尾的数组 2，最长重复子数组长度为 dp[i][j]。为什么不以 i 和 j 为结尾呢？那么定义是为了简洁
3. 递推公式：if（nums1[i-1]==nums2[j-1]）就相当于找到两个数组中相等的元素了 dp[i][j]=dp[i-1][j-1]+1，为什么是从 i-1,j-1 这里+1 呢？因为我们是比较两个数组中的元素是否相同，如果相同就要两个数组一起往后退一格，一起看后面元素的状态，从这个
4. dp 数组的初始化：dp[i][0] 和 dp[0][j] 就是第一列和第一行都是没有意义的状态，因为我们要用到 i-1 和 j-1，因此应该初始化为 0，因为 dp 数组是在前一个状态+1，这里没有意义就不要初始化为 1 了。其余位置会被递推公式覆盖，就可以不用初始化，默认为 0 即可
5. 遍历顺序：肯定是两层 for 循环，先遍历数组 1 还是数组 2 呢？其实都可以。这里 for（int i=1；i<=nums1.length；i++）for（int j=1；j<=nums2.length；j++）因为 0 这一行和列没有意义，直接都从 1 开始。为什么取等于号呢？我们的 dp 数组的长度是 nums1 和 nums2 的长度加 1 的，而我们比较的时候是比较 nums[i-1] 和 nums[j-1]，因此不会越界。
6. 最终结果存在哪？不是在最后面的位置的，因此要遍历二维数组，找到最大值，因此在两层 for 循环遍历的时候就记录最大值了，再第二层 for 循环中最后 if（dp[i][j]>result）result=dp[i][j]
7. 打印 dp 数组：用于 debug
8. 解释：为什么不定义 i 和 j 为结尾的子序列呢？如果这样的话，第一列和第一行就要遍历统计，如果对应位置相等了，就要初始化为 1 了，就比较麻烦了

3.2 代码

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