不同的子序列java

序列java"/>

不同的子序列java

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
示例 2：

输入：s = “babgbag”, t = “bag”
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 “bag” 的方案。
(上箭头符号 ^ 表示选取的字母)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^

提示：

0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路，第一眼看出就是dp了，但是想偷懒于是写dfs，发现不过，还是乖乖dp。
dp最主要的就是递归方程，递归方程该如何得出？乖乖画表找规律（捂脸），看下表

这里多了个“”，肯定有人不懂了，解释下，空字符串是所有字符串的字串。但是想不到他怎么办？？那就不要他，代码中先算出第一行，第一列的就可以了。
动态规划的状态转移方程都有个判断条件，这里的就是t.charAt==s.charAt，这个应该都想的出来吧，这个想不出来我也没办法了。
然后我们圈出所以满足条件的（如果没有""，那么第一行第一列的就不要圈了），看下图

我相信这时候看图已经有小部分人找出规律了，但是还是要继续讲解。绝大大大大部分情况，dp[i][j]与他的左，上，左上有关。我们找出一个满足所有画圈的方程就算是解出此题了。如果是左+上，第6行F列不满足情况。上加左上很多都不满足。左加左上，所有都满足。所以方程就的出来了。

class Solution {public int numDistinct(String s, String t) {//t要是s的字串，所以s.len要大于t.lenif(s.length()<t.length())return 0;int[][] dp = new int[t.length()+1][s.length()+1];//第一行全部为1for(int j=0;j<s.length()+1;j++){dp[0][j] = 1;}for(int i=1;i<dp.length;i++)for(int j=1;j<dp[0].length;j++){if(t.charAt(i-1)==s.charAt(j-1))dp[i][j] = dp[i-1][j-1] +dp[i][j-1];elsedp[i][j] = dp[i][j-1];}return dp[dp.length-1][dp[0].length-1];}
}