力扣爆刷第132天之动态规划五连刷（子序列问题）

总结：

本节的题目均是上一节四种类型的变体。

一、1035. 不相交的线

题目链接：https://leetcode.cn/problems/uncrossed-lines/description/
思路：本题是子序列问题的变体，求不相交的线的最大个数，其实就是求最长重复子序列，求子序列，不等问题也需要处理。
定义dp[i][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] = max(dp[i][j-1], dp[i-1][j])。

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        for(int i = 0; i < nums1.length; i++) {
            for(int j = 0; j < nums2.length; j++) {
                if(nums1[i] == nums2[j]) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                }else{
                    dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }
}

二、53. 最大子数组和

题目链接：https://leetcode.cn/problems/maximum-subarray/description/
思路：求最大子数组的和，其实就是最长连续子数组的和，是这个类型的变体，定义dp[i]表示以nums[i]为结尾的子序列和的最大值，如果前面子序列的和加上当前元素，结果还比当前元素小，就没必要加了。
另外的结题思路就是贪心，贪心的思路就是一直计算累加和，并且记录最大值，只要累加和小于0了，就从新计算累加和。

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

三、392. 判断子序列

题目链接：https://leetcode.cn/problems/is-subsequence/description/
思路：求一个字符串是否是另一个字符串的子序列，其实求的就是最长相等子序列。本题可以用贪心，也可以用动规。
贪心的话就是，遍历长字符串，只要短字符串中有想等的，短字符串就往前走一步。
动规的话，定义dp[i][j]表示以下标i为结尾的字符串s，是否是以下标j为结尾的字符串t的字符子串。所以元素相等时依赖于上一个位置，元素不等时，s不可后退，t可后退。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int k = 0, j = 0;
        for(int i = 0; i < t.length() && j < s.length(); i++) {
            if(s.charAt(j) == t.charAt(i)) {
                k++;
                j++;
            }
        }
        return k == s.length();
    }
}

动态规划

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

四、115. 不同的子序列

题目链接：https://leetcode.cn/problems/distinct-subsequences/description/
思路：本题和上一题类似，上一题是s不能后退，t可以，因为求的是完整的s。本题是t不能后退，s可以，因为求的是完整的t。
求不同子序列，定义dp[i][j]表示，以下标i为结尾的字符串包含dp[i][j]个以j为结尾的t。
当s[i] = t[j]时，求组合数，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。 如abb 和 ab。i= 2和j=1时可以体会一下。
当s[i]!=t[j]时，求组合数，dp[i][j] = dp[i-1][j]。

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

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

题目链接：https://leetcode.cn/problems/delete-operation-for-two-strings/description/
思路：本题是求最少删除多少次，可以让两个字符串相等。定义也是一样的，定义dp[i][j]表示以i为为结尾的字符串word1和以j为结尾的字符串word2，需要dp[i][j]此删除操作才相等。
那么当word1[i] == word2[j]时，就无需删除，依赖于上一个位置要删除的个数，dp[i][j] = dp[i-1][j-1]。
当word1[i] != word2[j] 时，就需要考虑删除，可以考虑是删掉Word1一个还是删掉word2一个，反正就是最少个数。dp[i][j] = min(dp[i-1][j]), dp[i][j-1] + 1;

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        for(int i = 0; i < dp.length; i++) {
            dp[i][0] = i;
        }
        for(int i = 0; i < dp[0].length; i++) {
            dp[0][i] = i;
        }
        for(int i = 0; i < word1.length(); i++) {
            for(int j = 0; j < word2.length(); j++) {
                if(word1.charAt(i) == word2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j];
                }else{
                    dp[i+1][j+1] = Math.min(dp[i+1][j], dp[i][j+1]) + 1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}