代码随想录算法训练营Day52|LC300 最长递增子序列&LC 674 最长连续递增序列&LC 718 最长重复子数组

一句话总结：动规做多了就豁然开朗了。

原题链接：300 最长递增子序列

 按照动规五部曲：

1. 首先确定dp数组及下标的含义：dp[i]表示以nums[i]结尾的最长子序列的长度；
2. 确定状态转移方程：如果nums[i] > nums[j]（其中j < i）,那么dp[i] = Math.max(dp[i], dp[j] + 1)，即位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值；
3. dp数组的初始化：每个子序列最开始都是1，所以初始化为1；
4. 数组的遍历顺序：可见dp[i]取决于每一个小于i的j的值，因此从前往后遍历；
5. 举例推导dp数组：过程略。

最终代码如下：

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

原题链接： 674 最长连续递增序列

找的是连续递增子序列，因此直接一次遍历即可解决，如果当前数大于前一个数，那么cnt+1，否则将cnt重置为1。最后取所有cnt值中最大的一位即可。

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        int ans = 1, cnt = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) ++cnt;
            else cnt = 1;
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}

这里用的是贪心思想，动规做法即上一题的改动，一趟遍历即可，过程差不多。

原题链接：718 最长重复子数组

最基础的做法是二维dp数组。按照动规五部曲，过程如下：

1. 确定dp数组及下标的含义：dp[i][j]表示nums1数组的第i位与nums2数组的第j位的最长重复子数组的长度；
2. 确定状态转移方程：dp[i][j]只能由dp[i - 1][j - 1]推导而来，即if (nums1[i - 1] == nums2[j - 1]) {dp[[i][j] = dp[i - 1][j - 1] + 1}。而如果两者不等，那么即为0；
3. dp数组的初始化：为了递归方便，所有dp[i][0] 和所有dp[0][i]都初始化为0；
4. 确定dp数组的遍历顺序：从前往后，两层循环分别对nums1数组和nums2数组遍历即可；
5. 举例推导dp数组：过程略。

最终代码如下：

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

另有滚动数组解法，利用一维dp数组即可。需要注意内层循环为了避免重复覆盖，因此采用从后往前遍历顺序。

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