力扣爆刷第79天--动态规划一网打尽子序列一维二维连续不连续问题

力扣爆刷第79天–动态规划一网打尽子序列一维二维连续不连续问题

文章目录

• • • 力扣爆刷第79天--动态规划一网打尽子序列一维二维连续不连续问题
    • 零、总结
    • 一、300.最长递增子序列
    • 二、674. 最长连续递增序列
    • 三、718. 最长重复子数组
    • 四、1143.���长公共子序列

      零、总结

      今天的专题是子序列问题，有一维的，也有二维的，有求连续的，也有求不连续的，组合是四种类型，且看一网打尽。

      （）

      一、300.最长递增子序列

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

      思路：求最长递增子序列，定义dp[i]表示在区间[0,i]种，以nums[i]为结尾的最长递增子序列的长度，确定了dp[i]的定义以后，dp[i]就好推导了，既然dp[i]是以nums[i]为结尾的，那么自然要从[0,i-1]找小于nums[i]的值，遍历一遍，然后更新dp[i]。

      （）

      class Solution {    public int lengthOfLIS(int[] nums) {        int[] dp = new int[nums.length];        Arrays.fill(dp, 1);        int max = 1;        for(int i = 1; i  nums[j]) {                    dp[i] = Math.max(dp[i], dp[j]+1);                }            }            max = Math.max(max, dp[i]);        }        return max;    }}

      二、674. 最长连续递增序列

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

      思路：连续的话就更好做了，都不需要在小区间里再遍历，上一题是非连续，需要在[0, i-1]区间里遍历，本题连续，连续就加1，不连续就为1，非常简单。

      class Solution {    public int findLengthOfLCIS(int[] nums) {        int[] dp = new int[nums.length];        dp[0] = 1;        int max = 1;        for(int i = 1; i  nums[i-1]) {                dp[i] = dp[i-1]+1;            }else{                dp[i] = 1;            }            max = Math.max(dp[i], max);        }        return max;    }}

      三、718. 最长重复子数组

      题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

      思路：本题求的是最长连续重复子数组，因为是重复子数组，数组是连续的，如果是最长重复子序列，那么就是不连续的，要求两个数组有最长的，连续重复部分，那么定义dp[i][j]表示以nums1[0, i]和nums2[0, j]中以nums1[i]和nums2[j]为结尾的最长连续重复子数组的长度，那么只要nums1[i]==nums2[j]可以得到dp[i][j]=dp[i-1][j-1]+1,

      如果nums1[i] != nums2[j]，那么dp[i][j]=0。

      class Solution {     public int findLength(int[] nums1, int[] nums2) {        int[][] dp = new int[nums1.length+1][nums2.length+1];        int max = 0;        for(int i = 0; i  
      四、1143.最长公共子序列
       
      题目链接：https://leetcode.cn/problems/longest-common-subsequence/
      思路：本题正好和上一题是一对，上一题求的是两个数组的最长重复子数组，求的是连续的重复，本题求的是最长公共子序列，那自然求的是不要求连线的，定义和之前一样，dp[i][j]表示以nums1[0, i]和nums2[0, j]中以nums1[i]和nums2[j]为结尾的最长公共子序列的长度，
      如果nums1[i] == nums2[j]，那么dp[i][j]=dp[i-1][j-1]+1;
      如果nums1[i] != nums2[j]，那么dp[i][j]的长度就要延续之前最长的长度，如 1 2 3与1 2 4, 3与4不相等，那么便可以延续集和{1， 2， 3}和集合{1， 2}或者{1， 2}和{1， 2， 4}，那么自然是包括dp[1][1]的，所以为dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
       
      class Solution {     public int longestCommonSubsequence(String text1, String text2) {        int[][] dp = new int[text1.length()+1][text2.length()+1];        for(int i = 1; i             for(int j = 1; 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()];    }}