题目

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

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

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

示例

输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabb b it
rab b bit
ra b bbit

解析

首先根据题意，s中可能有若干个t；且要求的是子序列，并没有要求连续；
先用动归五部曲来分析下：
1.确定dp数组及其含义
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
这个定义没有变，这几道题都是用的这个定义套路
2.确定递推公式
这个递推公式就会相对麻烦一点，首先对于这一类分析，在分析递推公式的时候，一般都是分析两种情况：

• s[i - 1] 与 t[j - 1]相等
• s[i - 1] 与 t[j - 1] 不相等
  对于本题来讲，相等的时候，dp[i][j]的公式→可以分为如下两个部分：
  第一部分，s[i - 1] 与 t[j - 1]这两个值相等了，将相当于假设没有这两个值的话的dp值，就是dp[i-1][j-1]（也就是用s[i-1]）;
  第二部分，就是不用s[i-1]，不用的话就是dp[i-1][j]（即s[i-2]结尾，t[i-1]结尾）
  最后二者相加，就是最后的递推公式

3.初始化
首先已知求递推公式，dp[i][j]可以由dp[i-1][j-1] 和 dp[i-1][j]方向推到过来，也就是上方和左上方，那么第一行就需要初始化；
dp[i][0]表示第一行的初始化的时候，根据dp数组的含义，就相当于以i-1结尾的字符串s，中出现-1结尾（空字符串）的个数，那就是1；
dp[0][j]表示以-1结尾（空字符串s）中出现字符串t的个数，那肯定没有合适的，就是0；且dp[0][0]为0

func numDistinct(s string, t string) int {m := len(s)n := len(t)dp := make([][]int, m+1)for i := range dp {dp[i] = make([]int, n+1)}// 初始化dp数组for i := range dp {dp[i][0] = 1}for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if s[i-1] == t[j-1] {dp[i][j] = dp[i-1][j-1] + dp[i-1][j]} else {dp[i][j] = dp[i-1][j]}}}return dp[m][n]
}