前言：
此刻我们对“子序列的和”大概比较关注，大家都需要了解一些“子序列的和”的相关文章。那么小编在网络上网罗了一些对于“子序列的和””的相关知识，希望我们能喜欢，兄弟们快快来学习一下吧！题目描述
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例
输入：
s = "rabbbit", t = "rabbit"
输出：
3写在前面
本文答案参考自 LeetCode 精选（powcai的）题解。[敲打]
解法：动态规划
窍门：当问的是解法个数而不是怎么解的时候，可以优先考虑动态规划。
dp[ i ][ j ] 代表 在 s 的前 j 个字符 中 t 的前 i 个字符出现的个数
那么，状态转移方程为
当 s[ j ] == t [ i ] 时, dp[ i ][ j ] = dp[ i -1][ j -1] + dp[ i ][ j -1];
当 s[ j ] != t [ i ] 时, dp[ i ][ j ] = dp[ i ][ j -1]
这么简洁的吗~但是我是不可能懂的[看][流泪]
代码
class Solution { public int numDistinct(String s, String t) { int[][] dp = new int[t.length() + 1][s.length() + 1]; for (int j = 0; j < s.length() + 1; j++) dp[0][j] = 1; for (int i = 1; i < t.length() + 1; i++) { for (int j = 1; j < s.length() + 1; j++) { if (t.charAt(i - 1) == s.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]; else dp[i][j] = dp[i][j - 1]; } } return dp[t.length()][s.length()]; }}作者：powcai链接：来源：力扣（LeetCode） 版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #子序列的和
