力扣爆刷第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()];
}
}