115.不同的子序列

力扣题目链接

class Solution {public int numDistinct(String s, String t) {//dp[i][j]表示以 i-1 j-1 位置结尾，有多少个重复的//选择s，t在i - 1的位置 + 不选，则s往后走，t没动//if(s.charAt(i - 1) == t.charAt(j - 1))dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];//else dp[i][j] = dp[i - 1][j]//初始化[i][0] = 1,s中都不选就可以获得1个空字符串，[0][j] = 0,怎么选都不能从空里面选出个tint lens = s.length();int lent = t.length();int[][] dp = new int[lens + 1][lent + 1];for(int i = 0;i < lens;i++){dp[i][0] = 1;}//这里初始化从1开始，别给覆盖了for(int i = 1;i < lent;i++){dp[0][i] = 0;}for(int i = 1;i <= lens;i++){for(int j = 1;j <= lent;j++){if(s.charAt(i - 1) == t.charAt(j - 1))dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];else{dp[i][j] = dp[i - 1][j];}}}return dp[lens][lent];}
}

#392.判断子序列

力扣题目链接

class Solution {public boolean isSubsequence(String s, String t) {//dp[i][j]表示以i - 1 and j - 1为结尾的子序列的最大长度//右下角为最大值//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];int len1 = s.length();int len2 = t.length();int[][] dp = new int[len1 + 1][len2 + 1];//初始化第一列和第二列为0for(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];}}return dp[len1][len2] == len1;}
}