代码随想录算法训练营第五十七天 | 392.判断子序列 115.不同的子序列

1. 判断子序列

392. 判断子序列 - 力扣（LeetCode）

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度。

class Solution {public boolean isSubsequence(String s, String t) {//dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。int ls = s.length();int lt = t.length();int[][] dp = new int[ls + 1][lt + 1];for(int i = 1; i <= ls; i++){for(int j = 1; j <= lt; j++){if(s.charAt(i-1) == t.charAt(j-1))dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = dp[i][j-1];}}return dp[ls][lt] == ls? true: false;}
}

2. 不同的子序列

115. 不同的子序列 - 力扣（LeetCode）

dp[i][j]：s中[0: i-1] 出现 t中 [0: j-1] 个数。(i j 为0 可以理解为空字符串)

可以理解为 字符串 s[i-1] 删除元素 能否变成 t[j-1] 

如果当前位置上的两个元素相等了 bagg bag 

那么这个位置的个数等于 bagg bag +  bagg bag

if(s.charAt(i-1) == t.charAt(j-1))

                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; （包含当前组成情况 + 不包含当前组成情况）

既然s[i-1]可以组成 t[j-1]，那么还要看s不包含(i-1)的情况（前面可能已经组成了，得加上）

如果当前位置上的两个元素不相等 bagg bag 

不相等了，就看s[i]的字串s[i - 1] 的组成个数

class Solution {public int numDistinct(String s, String t) {// dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。int ls = s.length();int lt = t.length();int[][] dp = new int[ls+1][lt+1];for (int i = 0; i < ls + 1; i++) {dp[i][0] = 1; // s[0-1:i-1] 可以构成 t[0-1](空字符串)}for(int i = 1; i <= ls; i++){for(int j = 1; j <= lt; j++){if(s.charAt(i-1) == t.charAt(j-1))dp[i][j] = dp[i-1][j-1] + dp[i-1][j];// 包括s当前元素 + 不包括s当前元素elsedp[i][j] = dp[i-1][j];}}return dp[ls][lt];}
}