回家躺的太舒服了的说 -><-

300.最长递增子序列

文章：41. 最长上升子序列

题目：300. 最长递增子序列

【思路】

子序列：由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序

1.确定dp及其下标的定义

dp[i]：表示i之前包括 i 的以nums[i]结尾的最长递增子序列的长度

2.状态转移方程

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列+1的最大值

=》 if(nums[i] > nums[i-1]) dp[i] = max(dp[i],dp[j+1]) (j=0; j< i ;j++)

不是要dp[i]与dp[j] + 1进行比较，而是要去dp[j] +1 的最大值

3.dp[i] 的初始化

每一个i，对应的dp[i] 的起始大小都至少为1

4.确认遍历顺序

每个dp[i] 都是从0到i-1各个位置的最长递增子序列推导而来的，那么遍历i一定是从前向后遍历

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[]dp = new int[nums.length];
        Arrays.fill(dp,1);
        int res = 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; 
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func lengthOfLIS(nums []int) int {
    dp:= make([]int,len(nums))
    for i:=0;i<len(dp);i++{
        dp[i] = 1
    }
    res:=1
    for i:=1;i<len(dp);i++{
        for j:=0;j<i;j++{
            if nums[i] > nums[j] {
                dp[i] = max(dp[i],dp[j]+1)
            }
            res = max(res,dp[i])
        }
    }
    return res
}

674.最长连续递增序列

文章：42. 最长连续递增序列

题目：674. 最长连续递增序列

【思路】

本题和上题的最大区别在于：要求的是最长连续递增序列

1.确认数组及其下标的含义

dp[i] : 以下标i 为结尾的连续递增的子序列长度为dp[i]

一定是要以下标i为结尾，并不是说一定以下标0为起始位置

2.确认递推公式

如果nums[i] > nums[i-1]，那么以 i 为结尾的连续递增的子序列长度一定等于 以 i-1 为结尾的连续递增的子序列长度 + 1

即： dp[i] = dp[i-1] + 1

3.数组初始化

以下标 i 为结尾的连续递增的子序列长度最少也应该是1，即dp[i]的初始值为1

4.确认遍历顺序

本题只需dp[i] 和dp[i-1]进行比较，只需要一层遍历，因此是从前往后遍历

5.举例推

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        for(int i=0;i<dp.length;i++){
            dp[i] = 1;
        }
        int res = 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;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findLengthOfLCIS(nums []int) int {
    dp:= make([]int,len(nums))
    for i:=0;i<len(dp);i++{
        dp[i] = 1
    }
    res :=1
    for i:=1;i<len(dp);i++{
        if nums[i] > nums[i-1]{
            dp[i] = dp[i-1] +1
        }
        res = max(res,dp[i])
    }
    return res
}

718.最长重复子数组

文章：43. 最长重复子数组

题目：718. 最长重复子数组

【思路】

题目求的是连续子序列

要求两个数组中最长重复子数组，我们只要想到用二维数组记录两个字符串的所有比较情况，这样就比较好推 递推公式了

1.确认dp数组及其下标含义

dp[i] [j] ：以下标i-1 结尾的A，和以下标为j-1结尾的B，最长重复子数组长度为dp[i] [j]

我们在遍历dp[i] [j] 的时候i和j都从1开始

2.确认递推公式

根据dp[i] [j]的定义，dp[i] [j]的状态都是只能由[i-1] [j-1]推导出来，

即当A[i-1]和B[j-1]相等的时候，dp[i] [j] = dp[i-1] [j-1]+1

3.数组初始化

递推公式dp[i] [j] = dp[i-1] [j-1]+1需要有dp[i] [0]和dp[0] [j]的初始化情况，因此dp[i] [0]和dp[0] [j]都需要初始化为1

4.确认遍历顺序

外层遍历A，内层遍历B和相反顺序都可以

5.举例推导

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 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+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;
                }
                res = Math.max(dp[i][j],res);
            }
        }
        return res;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func findLength(nums1 []int, nums2 []int) int {
    dp := make([][]int,len(nums1)+1)
    for i:=0;i<len(nums1)+1;i++{
        dp[i] =make([]int,len(nums2)+1)
    }
    res:=0
    for i:=1;i<len(nums1)+1;i++{
        for j:=1;j<len(nums2)+1;j++{
            if nums1[i-1] == nums2[j-1]{
                dp[i][j] = dp[i-1][j-1] +1
            }
            res = max(res,dp[i][j])
        }
    }
    return res
}

【算法总结】

  • 最长递增子序列：比较nums[i]和nums[i-1]的大小，大于的话就dp[i] = max(dp[i] , dp[j]+1)，默认初始化为1
  • 最长连续递增序列：比较nums[i]和nums[i-1]的大小，大于的话就dp[i] = dp[i-1]+1 ，默认初始化为1
  • 最长重复数组：循环比较两个数组的值，如果相等的话dp[i] [j] = dp[i-1] [j-1] +1