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

本文主要是介绍力扣爆刷第132天之动态规划五连刷（子序列问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

这篇关于力扣爆刷第132天之动态规划五连刷（子序列问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---