第九章 动态规划part11
1143.最长公共子序列
体会一下本题和 718. 最长重复子数组 的区别
文章讲解
题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
思路
继续动规五部曲分析如下：
确定dp数组（dp table）以及下标的含义
dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
这样定义是为了后面代码实现方便，其实就是简化了dp数组第一行和第一列的初始化逻辑。确定递推公式
- 两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
- 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
-
如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。
即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
dp数组如何初始化
先看看dp[i][0]应该是多少呢？
test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;
同理dp[0][j]也是0。
其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0。-
确定遍历顺序
从递推公式，可以看出，有三个方向可以推出dp[i][j]，如图：
image.png
那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下来遍历这个矩阵。
举例推导dp数组
以输入：text1 = "abcde", text2 = "ace" 为例，dp状态如图：
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; 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[len1][len2];
}
}
什么时候使用 i <= text1.length() 和 i < text1.length()
- 使用 i <= text1.length() 的情况：
当你在 DP 表中额外添加了一行和一列（通常初始化为 0），用来处理边界情况（即空字符串的情况），此时循环的范围需要包括这行这列，即 i 从 1 开始，直到 text1.length()（包含）。 - 使用 i < text1.length() 的情况：
当你没有额外添加这一行和一列，而是直接在 DP 表中使用索引 0 代表第一个字符，索引 text1.length() - 1 代表最后一个字符时，此时循环的范围是 i 从 0 开始，直到 text1.length() - 1（不包含 text1.length()）。
1035.不相交的线
其实本题和 1143.最长公共子序列 是一模一样的，大家尝试自己做一做。
文章讲解
思路
绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！
直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; 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[len1][len2];
}
}
53. 最大子序和
这道题我们用贪心做过，这次 再用dp来做一遍
文章讲解
动规五部曲如下：
确定dp数组（dp table）以及下标的含义
dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。确定递推公式
dp[i]只有两个方向可以推出来：
dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
nums[i]，即：从头开始计算当前连续子序列和
一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);dp数组如何初始化
从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。
dp[0]应该是多少呢?
根据dp[i]的定义，很明显dp[0]应为nums[0]即dp[0] = nums[0]。确定遍历顺序
递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。-
举例推导dp数组
以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：
image.png
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0) return 0;
int[] dp = new int[nums.length];
dp[0] = nums[0];
int res = nums[0];
for(int i = 1; i < nums.length; i++){
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
res = res > dp[i] ? res: dp[i];
}
return res;
}
}
392.判断子序列
这道题目算是 编辑距离问题 的入门题目（毕竟这里只是涉及到减法），慢慢的，后面就要来解决真正的 编辑距离问题了
文章讲解
思路
动态规划五部曲分析如下：
确定dp数组（dp table）以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。确定递推公式
在确定递推公式的时候，首先要考虑如下两种操作，整理如下：
- if (s[i - 1] == t[j - 1])
t中找到了一个字符在s中也出现了 - if (s[i - 1] != t[j - 1])
相当于t要删除元素，继续匹配 - if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1（如果不理解，在回看一下dp[i][j]的定义）
- if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];
- 其实这里 大家可以发现和 1143.最长公共子序列 的递推公式基本那就是一样的，区别就是 本题 如果删元素一定是字符串t，而 1143.最长公共子序列 是两个字符串都可以删元素。
-
dp数组如何初始化
因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：
从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。
这里大家已经可以发现，在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
image.png 确定遍历顺序
同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右-
举例推导dp数组
以示例一为例，输入：s = "abc", t = "ahbgdc"，dp状态转移图如下：
image.png
class Solution {
public boolean isSubsequence(String s, String t) {
int len1 = s.length();
int len2 = t.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; 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[len1][len2] == len1) return true;
else return false;
}
}
用双指针似乎更简单，练习一下
class Solution {
public boolean isSubsequence(String s, String t) {
int sp = 0;
int tp = 0;
while(sp < s.length() && tp < t.length()){
if(s.charAt(sp) == t.charAt(tp)) sp++;
tp++;
}
if(sp == s.length()) return true;
else return false;
}
}
