9.10 子序列问题

子序列不连续

300. 最长递增子序列

https://leetcode.cn/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/

dp数组含义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度

class Solution {
    public int lengthOfLIS(int[] nums) {
        // dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);//初始化数组
        for(int i = 0; i < nums.length;i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res = 0;
        for(int i = 0; i < dp.length;i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

1143. 最长公共子序列

https://www.programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html
https://mp.weixin.qq.com/s/ZhPEchewfc03xWv9VP3msg
林小鹿清晰！！

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1]; // 先对dp数组做初始化操作
        for (int i = 1 ; i <= text1.length() ; i++) {
            char char1 = text1.charAt(i - 1);
            for (int j = 1; j <= text2.length(); j++) {
                char char2 = text2.charAt(j - 1);
                if (char1 == char2) { // 开始列出状态转移方程
                    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()];
    }
}

1035. 不相交的线

拿示例一A = [1,4,2], B = [1,2,4]为例，相交情况如图：

其实也就是说A和B的最长公共子序列是[1,4]，长度为2。 这个公共子序列指的是相对顺序不变（即数字4在字符串A中数字1的后面，那么数字4也应该在字符串B数字1的后面）
这么分析完之后，大家可以发现：本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

class Solution {
  public int maxUncrossedLines(int[] A, int[] B) {
      int [][] dp = new int[A.length+1][B.length+1];
      for(int i=1;i<=A.length;i++) {
          for(int j=1;j<=B.length;j++) {
              if (A[i-1]==B[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[A.length][B.length];
  }
}

子序列连续

674. 最长连续递增序列

https://leetcode.cn/problems/longest-continuous-increasing-subsequence/solution/zui-chang-lian-xu-di-zeng-xu-lie-by-kino-on97/

class Solution {
    //注意与非连续的区分
    public int findLengthOfLCIS(int[] nums) {
    //dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
    int[] dp = new int[nums.length];
    Arrays.fill(dp,1);//初始化
    for(int i = 0; i < nums.length-1;i++){
        if(nums[i+1] > nums[i]){
            //因为本题要求连续递增子序列
            //要比较nums[i + 1]与nums[i]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。
            dp[i+1] = dp[i] + 1;//注意这里和不连续的区别，连续的
        }
    }
    int res = 0;
    for(int i = 0; i < dp.length;i++){
        res = Math.max(res,dp[i]);
    }
    return res;
    }
}

718. 最长重复子数组

https://www.programmercarl.com/0718.%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84.html#_718-%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/solution/yi-zhang-biao-ba-ju-hua-kan-dong-dong-tai-gui-hua-/

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        //dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        dp[0][0] = 0;
        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;
    }
}

// 版本二: 滚动数组
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length + 1];
        int result = 0;
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = nums2.length; j > 0; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else {
                    dp[j] = 0;
                }
                result = Math.max(result, dp[j]);
            }
        }
        return result;
    }
}

53. 最大子数组和

https://www.programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html#%E6%80%9D%E8%B7%AF
以 nums[i] 为结尾的「最大子数组和」为 dp[i]。
dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。

class Solution {
    public int maxSubArray(int[] nums) {
        //1、dp[i] : 前i个包括i最大和的连续子数组
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];
        for(int i = 1; i < nums.length;i++){
            //2、确定递推公式
            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
            if(dp[i] > res) res = dp[i];
        }
        return res;
    }
}

编辑距离

392. 判断子序列

https://www.programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html#其他语言版本

class Solution {
    public boolean isSubsequence(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for(int i = 1; i <= s.length(); i++){
            for(int j = 1; j <= t.length();j++){
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if(dp[s.length()][t.length()] == s.length()){
            return true;
        } else{
            return false;
        }
    }
}

115. 不同的子序列

583. 两个字符串的删除操作

72. 编辑距离

回文

647. 回文子串

https://leetcode.cn/problems/palindromic-substrings/solution/liang-dao-hui-wen-zi-chuan-de-jie-fa-xiang-jie-zho/

class Solution {
    public int countSubstrings(String s) {
        int res = 0;
        for(int i = 0; i < s.length();i++){
            res += extent(s,i,i,s.length());
            res += extent(s,i,i+1,s.length());
        }
        return res;
    }
    int extent(String s,int i,int j,int n){
        int res = 0;
        while(i >= 0 && j < n && s.charAt(i) == s.charAt(j)){
            res++;
            i--;
            j++;
        }
        return res;
    }
}

5. 最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/solution/dai-ma-sui-xiang-lu-5-zui-chang-hui-wen-zi0c6/

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            // 以 s[i] 为中心的最长回文子串
            String s1 = palindrome(s, i, i);
            // 以 s[i] 和 s[i+1] 为中心的最长回文子串
            String s2 = palindrome(s, i, i + 1);
            // res = longest(res, s1, s2)
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    String palindrome(String s, int l, int r) {
        // 防止索引越界
        while (l >= 0 && r < s.length()
                && s.charAt(l) == s.charAt(r)) {
            // 向两边展开
            l--;
            r++;
        }
        // 返回以 s[l] 和 s[r] 为中心的最长回文串
        return s.substring(l + 1, r);
    }
}
// 详细解析参见：
// https://labuladong.github.io/article/?qno=5

516. 最长回文子序列

回文子串是要连续的，回文子序列可不是连续的！
https://leetcode.cn/problems/longest-palindromic-subsequence/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dpzi-dv83q/

public class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len + 1][len + 1];
        for (int i = len - 1; i >= 0; i--) { // 从后往前遍历 保证情况不漏
            dp[i][i] = 1; // 初始化
            for (int j = i + 1; j < len; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], Math.max(dp[i][j], dp[i][j - 1]));
                }
            }
        }
        return dp[0][len - 1];
    }
}