代码随想录算法训练营第四十四天 | 1143-最长公共子序列、1035-不相交的线、53-最大子序和、392-判断子序列
LeetCode1143 最长公共子序列
题目链接：https://leetcode.cn/problems/longest-common-subsequence/description/
文章讲解：https://programmercarl.com/1143.最长公共子序列.html
视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ/?vd_source=b989f2b109eb3b17e8178154a7de7a51
动规五部曲：
- 确定dp数组以及下标的含义
dp[i][j]表示[0，i-1]的nums1和[0，j-1]的nums2，二者的最长公共子序列的长度
- 确定递推公式
如果nums1[i-1] == nums2[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1
如果nums1[i-1] != nums2[j-1]，那么dp[i][j] = Math.max(dp[i-1][j]，dp[i][j-1]）
- dp数组如何初始化
与空字符串比较无公共子序列，故第零行和第零列都初始化为0
- 确定遍历顺序
由递推公式dp[i][j]由dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]得出，故两层for循环都是从1开始顺序遍历到nums1.length/nums2.length
- 举例推导dp数组
class Solution {public int longestCommonSubsequence(String text1, String text2) {int[][] dp = new int[text1.length()+1][text2.length()+1];for(int i = 1; i <= text1.length(); i++){for(int j = 1; j <= text2.length(); 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()];}
}
LeetCode1035 不相交的线
题目链接：https://leetcode.cn/problems/uncrossed-lines/description/
文章讲解：https://programmercarl.com/1035.不相交的线.html
视频讲解：https://www.bilibili.com/video/BV1h84y1x7MP/?vd_source=b989f2b109eb3b17e8178154a7de7a51
本题与 LeetCode1143 最长公共子序列 本质上是一致的，动规五部曲：
- 确定dp数组以及下标的含义
dp[i][j]表示[0，i-1]的nums1和[0，j-1]的nums2，二者的最长公共子序列的长度
- 确定递推公式
如果nums1[i-1] == nums2[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1
如果nums1[i-1] != nums2[j-1]，那么dp[i][j] = Math.max(dp[i-1][j]，dp[i][j-1]）
- dp数组如何初始化
与空字符串比较无公共子序列，故第零行和第零列都初始化为0
- 确定遍历顺序
由递推公式dp[i][j]由dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]得出，故两层for循环都是从1开始顺序遍历到nums1.length/nums2.length
- 举例推导dp数组
class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];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;}else{dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}}}return dp[nums1.length][nums2.length];}
}
LeetCode53 最大子序和
题目链接：https://leetcode.cn/problems/maximum-subarray/description/
文章讲解：https://programmercarl.com/0053.最大子序和（动态规划）.html
视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5/?vd_source=b989f2b109eb3b17e8178154a7de7a51
动规五部曲：
- 确定dp数组以及下标的含义
dp[i]表示以元素nums[i]为结尾的最大连续子序列的和
- 确定递推公式
两种情况：
- 延续前面的结果，dp[i] = dp[i-1] + nums[i]
- 不延续前面的结果，自己单独重新开始累加，dp[i] = nums[i]
故有：dp[i] = Math.max(nums[i]，dp[i-1] + nums[i])
- dp数组如何初始化
以nums[0]为结尾的最大连续子序列的和为nums[0]，所以dp[0] = nums[0]
- 确定遍历顺序
dp[i]由dp[i-1]推，所以从1开始往后遍历
- 举例推导dp数组
class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int result = dp[0];for(int i = 1; i < nums.length; i++){dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);result = Math.max(result, dp[i]);}return result;}
}
LeetCode392 判断子序列
题目链接：https://leetcode.cn/problems/is-subsequence/description/
文章讲解：https://programmercarl.com/0392.判断子序列.html
视频讲解：https://www.bilibili.com/video/BV1tv4y1B7ym/?vd_source=b989f2b109eb3b17e8178154a7de7a51
本题只涉及删除原始字符串，所以动态规划过程类似于LeetCode1143 最长公共子序列，最后只需比较二者的最长公共子序列是否是题目所给子序列，即可判断该子序列是否为原始字符串的子序列，动规五部曲：
- 确定dp数组以及下标的含义
dp[i][j]表示[0，i-1]的nums1和[0，j-1]的nums2，二者的最长公共子序列的长度，num1为题目所给子串，nums2为题目所给原始字符串
- 确定递推公式
如果nums1[i-1] == nums2[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1
如果nums1[i-1] != nums2[j-1]，那么dp[i][j] = dp[i-1][j]
- dp数组如何初始化
与空字符串比较无公共子序列，故第零行和第零列都初始化为0
- 确定遍历顺序
由递推公式dp[i][j]由dp[i-1][j-1]、dp[i-1][j]得出，故两层for循环都是从1开始顺序遍历到nums1.length/nums2.length
- 举例推导dp数组
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] = Math.max(dp[i-1][j], dp[i][j-1]);}}}if(dp[s.length()][t.length()] == s.length()){return true;}return false;}
}
另外的，此题更适合用双指针的方法进行求解：
class Solution {public boolean isSubsequence(String s, String t) {if(s.length() == 0){return true;}else if(t.length() == 0){return false;}int j = 0;for(int i = 0; i < t.length(); i++){if(t.charAt(i) == s.charAt(j)){j++;if(j == s.length()){return true;}}}return false;}
}