动态规划,用相似思路解决复杂问题 | LeetCode:392.判断子序列_哔哩哔哩_bilibili
动态规划之子序列,为了编辑距离做铺垫 | LeetCode:115.不同的子序列_哔哩哔哩_bilibili
392. 判断子序列
思目,两个字符串中可以任意删除字符塑造公共的子序列。本题的递推方程在元素相等时dp[i][j] = dp[i-1][j-1]+1;两者不等路:序列题时是dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);初做本题时,对不等时候的递推公式可以理解是:i位置与j位置不等,那么直接继承i-1位置或j-1位置的上一次状态;因为可能i-1位置与j位置相等;i位置与j-1位置可能相等;或者所有情况皆不成立的话,也是对从前向后递推所形成的状态的继承。而站在 编辑距离 的角度来看,这个dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])的操作就是删除i位置元素或删除j位置元素,从而求取两个字符串的共同序列。
// 时间复杂度O(n^2)
// 空间复杂度O(n^2)
class Solution {
public boolean isSubsequence(String s, String t) {
int n = s.length();
int m = t.length();
// dp数组的含义是s下标i与t的下标j之间的公共子序列的长度是多少,这里的子序列是不连续的若干字符
int[][] dp = new int[n+1][m+1];
// 遍历顺序从前向后,初始化是dp[0][0] = 0
for(int i=1; i<=n; i++){
for(int j=1; j<=m; 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]); // 这一步表示既可以删除s当前i位置的字符,也可以删除t的j位置的字符,从而直接关联上一个位置的状态
}
}
if(dp[n][m] == s.length())
return true;
return false;
}
}
115. 不同的子序列
思路:当s的i位置的元素与t的j位置的元素相等时,s可以与t一起往前推一个位置(这个操作是当前i位置与j位置分别在各自字符串中是唯一的,或者说题目中所要判断的仅仅是两个字符串是否存在共同子序列,所以纵使s中有重复的元素,但是不会影响判断结果;共同字串的话就不行);也可以s不选当前的位置,即此时dp[i][j]表示的是s的i位置前与t的j位置前,不同的子序列个数有几个;因此s不选当前的位置,即类似于两者不是合适的匹配元素,要找其他的元素,所以此时是要延续上一状态dp[i-1][j],这里是在s中找有几个t,所以只会由s来判断当前t位置的元素我是否选择,所以仅仅是dp[i-1][j],而不考虑dp[i][j-1];因此s的i位置与t的j位置相等时,有两个状态转移来源,所以需要对两个状态进行相加。
不等时,按照相等时不选择的状态延续操作,赋值dp[i-1][j]即可。
如果站在编辑距离的角度来看,dp[i-1][j]也是单向的删除操作,即只会删除s而不会删除t内的元素,删除的元素,就是重复出现的元素。
// 时间复杂度O(n^2)
// 空间复杂度O(n^2)
class Solution {
public int numDistinct(String s, String t) {
if(s.length() < t.length())
return 0;
int n = s.length();
int m = t.length();
int[][] dp = new int[n+1][m+1];
for(int i=0; i<=n; i++)
dp[i][0] = 1;
// 从前往后推没有初始化,从后往前时需要考虑t为空串,dp[i][m] = 1
for(int i=1; i<=n ;i++){
for(int j=1; j<=m; j++){
if(s.charAt(i-1) == t.charAt(j-1))
dp[i][j] = dp[i-1][j-1]+dp[i-1][j]; // 补上si不与tj比较,而是选择与j位置前的元素比较,因此关联上j-1之前元素所形成的状态dp[i-1][j]
else
dp[i][j] = dp[i-1][j];
}
}
return dp[n][m];
// 滚动数组的优化做法不太理解
// int[] dp = new int[m+1];
// dp[0] = 1;
// // 从前往后推没有初始化,从后往前时需要考虑t为空串,dp[i][m] = 1
// for(int i=1; i<=n ;i++){
// for(int j=m; j>0; j--){
// if(s.charAt(i-1) == t.charAt(j-1))
// dp[j] += dp[j-1]; // 补上si不与tj比较,而是选择与j位置前的元素比较,因此关联上j-1之前元素所形成的状态dp[i-1][j]
// }
// }
// return dp[m];
}
}