代码随想录|300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组（非常不理解了）

300.最长递增子序列

1.dp[i]的定义

本题中，正确定义dp数组的含义十分重要。

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

2.状态转移方程

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

所以if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1)

3.dp[i]的初始化

每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.

4.遍历顺序从前往后

5.dp推导

代码实现

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp=new int[nums.length]; //dp[i]含义是i之前包括i的以nums[i]结尾的最长递增子序列的长度
        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;
    }
}
 

674. 最长连续递增序列

思路比较简单

1.dp含义

dp[i]表示截至到i(包括i)的最长连续的子序列长度

2.初始化

dp都初始化为1

3.递推公式

因为要连续，如果满足后者大于前者，dp[i]=dp[i-1]+1。

4.遍历顺序

从前往后遍历

5.推导dp

6.代码实现

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int[] dp=new int[nums.length];//dp[i]表示截至到i包括i的最长连续个数
        int result=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;
                }
                if(dp[i]>result){result=dp[i];}
 
        }
        return result;
    }
}

718. 最长重复子数组（非常不理解了）

1.确定dp数组（dp table）以及下标的含义

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

2.递推公式(怎么推不太理解啊)

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

3.dp初始化

根据dp[i][j]定义，dp[i][0]和dp[0][j]其实都是没有意义的，但dp[i][0]和dp[0][j]要初始值，因为为了方便递归公式dp[i][j]=dp[i-1][j-1]+1,所以dp[i][0]和dp[0][j]初始化为0

A[0]如果和B[0]相同的话，dp[1][1]=dp[0][0]+1,只有dp[0][0]初始为0，正好符合递推公式逐步累加起来

4.确定遍历顺序

外侧for循环遍历A,内层for循环遍历B或者 外侧for循环遍历B,内层for循环遍历A都是一样的。

5.推导dp

6.代码实现

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int result=0;
        int[][] dp=new int[nums1.length+1][nums2.length+1];//dp[i][j]表示从nums1的下标i-1到nums2的下标j-1的相同长度
        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;
 
                }
                if(dp[i][j]>result){result=dp[i][j];}
 
            }
        }
        return result;
    }
}