算法训练营第五十六天|LeetCode300、674、718子序列系列开始

题目链接：300. 最长递增子序列 – 力扣（LeetCode）

个人思路：动规五部曲

1. dp数组含义及下标：dp数组表示以nums[i]结尾的最长递增子序列为dp[i]

2. 递推公式：当nums[i]和nums[j]比较的时候，如果i比j大，那么dp[i] = dp[j]+1。由于数组会被覆盖，因此我们要取最大值，即dp[i] = Math.max(dp[j]+1,dp[i]);

3. 初始化：不管什么情况，我总能输出一个数字，因此填充数组为1就好了

4. 遍历顺序：从前往后

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0 || nums == null) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);//不管怎么样都能输出一个数字
        for(int i=1 ; i<nums.length;i++){
            for(int j = 0 ; j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i] =  Math.max(dp[j]+1,dp[i]);            
                }            
            }
        }
        int res = 0;
        for(int i = 0;i<dp.length;i++){
            res = Math.max(dp[i],res);
        }
        return res;
    }
}

题目链接：674. 最长连续递增序列 – 力扣（LeetCode）

个人思路：这道题简单多了。

1. dp数组含义是：以nums[i]为结尾的最长连续递增子序列的长度。

2. 递推公式：既然是连续，那么就只用让后一个数和前一个数进行比较，同时也不再需要二次循环，因为如果后一个数比前一个数大的话，那么直接加一就可以了，如果碰到了后一个数比前一个数小，那么就跳过，这个时候我保留了最大值。

代码

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length == 0||nums == null) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for(int i = 1 ; i<nums.length;i++){
            if(nums[i]>nums[i-1]){
                dp[i] = Math.max(dp[i-1]+1,dp[i]);
            }
        }
        int res = 0;
        for(int i : dp ){
            res = Math.max(i,res);
        }
        return res;

    }
}

题目链接：718. 最长重复子数组 – 力扣（LeetCode）

个人思路：递归五部曲

1. dp数组含义及下标：表示的是以nums1[i-1]，nums2[j-1]为结尾的最长重复子数组的长度。至于为什么是i-1和j-1呢？则是因为这样子代码会简洁一点。如果使用了i和j的话，那就需要对dp数组的第一行和第一列进行初始化

2. 递推公式：因为使用dp数组来记录它的每一次的状态，当前的状态等于上一次的状态加一，因此，dp[i][j] = dp[i-1][j-1]+1

3. 初始化：按照道理我们需要对dp[i][0]和dp[0][j]，进行初始化，也就是第一行和第一列，但是根据我们dp数组的含义来说，这里dp[i][0]和dp[0][j]是没有意义的，所以初始化为0

4. 遍历顺序：从前往后

代码

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int res = 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;
                     
                }
                res = Math.max(dp[i][j],res);
               
            }
        }
        return res;

    }
}