Day 52 | 674. 最长连续递增序列 & 718. 最长重复子数组 & 1143.最长公共子序列

 674. 最长连续递增序列

动态规划解题思路：    

①确定dp数组以及下标含义

        dp[i]：下标[0,i]，以nums[i]结尾的最长递增序列长度

②确定递推公式

        每次遍历比较nums[i]与nums[i-1]的值。

        若大于，dp[i]=dp[i-1]+1

        否则，因为要求连续，dp[i]不变，即为初始值1.遍历下一个元素时则从1开始递增。

③dp数组如何初始化

        dp长度为数组长度。

        给dp数组所有元素都初始化为1，代表初始递增序列为1.

④确定遍历顺序

          从前向后遍历。

⑤举例推导dp数组

 最后返回dp数组中元素的最大值即可。

    public int findLengthOfLCIS(int[] nums) {
        int[] dp=new int[nums.length];
        Arrays.fill(dp,1);
        for(int i=1;i
            if(nums[i]>nums[i-1]){
                dp[i]=dp[i-1]+1;
            }
        }
        int res=1;
        for(int i:dp){
            if(i>res){
                res=i;
            }
        }
        return res;
    }

718. 最长重复子数组

dp解题思路：

①确定dp数组以及下标含义

        dp[i][j]：下标为[i-1]的nums1，下标为[j-1]的nums2，两个数组的最长重复子数组为dp[i][j]

②确定递推公式

        定义dp数组为dp[len1+1][len2+1]

        为了方便计算和初始化，每次比较的都是下标i-1与j-1的元素，将其赋值给dp[i][j]（注意错位一位）.

        i,j从1开始遍历（元素i-1下标为0开始遍历），

        若nums[i-1]==nums[j-1]，则dp[i][j]=dp[i-1][j-1]+1;

        若不相等，因为要求连续，则为初始值0.

③dp数组如何初始化

        给dpdp[0][j],dp[i][0]初始化为0，代表初始重复子数组为0.

④确定遍历顺序

          从前向后，从上至下遍历。（i从1到len1，j从1到len2）

⑤举例推导dp数组

    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;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]>res){
                    res=dp[i][j];
                }
            }
        }
        return res;
    }

1143.最长公共子序列

dp解题思路：

①确定dp数组以及下标含义

        dp[i][j]：下标为[i-1]的nums1，下标为[j-1]的nums2，两个字符串的最长公共子序列为dp[i][j]

②确定递推公式

        定义dp数组为dp[len1+1][len2+1]

        为了方便计算和初始化，每次比较的都是下标i-1与j-1的元素，将其赋值给dp[i][j]（注意错位一位）.

        i,j从1开始遍历（元素i-1下标为0开始遍历），

        (1)若nums1[i-1]==nums1[j-1]，则

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

        (2)若不相等，因为不要求连续，则dp[i][j]由dp[i-1][j]和dp[i][j-1]决定，取两者的最大值。

                                             dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);

③dp数组如何初始化

        给dpdp[0][j],dp[i][0]初始化为0，代表初始公共子序列为0.

④确定遍历顺序

          dp[i][j]由dp[i-1][j-1],dp[i][j-1],dp[1-1][j]三者共同决定。因此从前向后，从上至下遍历。（i从1到len1，j从1到len2）。

⑤举例推导dp数组

 最后返回dp[len][len]即为最长公共子序列

    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp=new int[text1.length()+1][text2.length()+1];
        for(int i=1;i<=text1.length();i++){
            for(int j=1;j<=text2.length();j++){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }