【代码随想录训练营】Day52-动态规划

代码随想录训练营 Day52

今日任务

300.最长递增子序列
674.最长连续递增序列
718.最长重复子数组
语言：Java

300. 最长递增子序列

链接：https://leetcode.cn/problems/longest-increasing-subsequence/
油管上很清晰的模拟过程视频
同类型题目：increasing, decreasing, non-decreasing…

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

时间复杂度：O(N^2)
空间复杂度：O(N)

674. 最长连续递增序列

链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/

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

718. 最长重复子数组

链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
油管上很清晰的模拟过程视频

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        //dp[i][j]表示截至i-1位和j-1位最长相同子串长度为dp[i][j]
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int len1 = nums1.length;
        int len2 = nums2.length;
        int result = 0;
        for(int i = 0; i < len1; i++){
            for(int j = 0; j < len2; j++){
                if(nums1[i] == nums2[j]){
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }
                result = Math.max(result, dp[i + 1][j + 1]);
            }   
        }
        return result;
    }
}

//也可以根据下边这个过程采用滚动数组的方法
//滚动数组就要求从后向前遍历
//且在元素不相等时要有赋0的动作
/*

            1   2   3   2   1
        j    
    i   0   0   0   0   0   0

    3   0   0   0   1   0   0

    2   0   0   1   0   2   0

    1   0   1   0   0   0   3

    4   0   0   0   0   0   0

    7   0   0   0   0   0   0

*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

滚动数组

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] dp = new int[len1 + 1];
        int result = 0;
        for(int i = 1; i <= len2; i++){
            for(int j = len1; j > 0; j--){
                if(nums1[j - 1] == nums2[i - 1]){
                    dp[j] = dp[j - 1] + 1;
                }
                else{
                    dp[j] = 0;
                }
                result = result > dp[j] ? result : dp[j];
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20