Given two strings s and t, return the number of distinct subsequences of s which equals t.
A string's subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters' relative positions. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).
It is guaranteed the answer fits on a 32-bit signed integer.
Example 1:
Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways you can generate "rabbit" from S. rabbbitrabbbitrabbbit Example 2:
Input: s = "babgbag", t = "bag" Output: 5 Explanation: As shown below, there are 5 ways you can generate "bag" from S. babgbagbabgbagbabgbagbabgbagbabgbag Constraints:
0 <= s.length, t.length <= 1000sandtconsist of English letters.
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）题目数据保证答案符合 32 位带符号整数范围。
在字符串
s中最多包含多少个字符串t。这里面包含很多重叠子问题，所以尝试用动态规划解决这个问题。定义dp[i][j]代表s[i:]的子序列中t[j:]出现的个数。初始化先判断边界条件。当i = len(s)且0≤ j < len(t)的时候，s[i:]为空字符串，t[j:]不为空，所以dp[len(s)][j] = 0。当j = len(t)且0 ≤ i < len(s)的时候，t[j:]不为空字符串，空字符串是任何字符串的子序列。所以dp[i][n] = 1。当
i < len(s)且j < len(t)的时候，如果s[i] == t[j]，有 2 种匹配方式，第一种将s[i]与t[j]匹配，那么t[j+1:]匹配s[i+1:]的子序列，子序列数为dp[i+1][j+1]；第二种将s[i]不与t[j]匹配，t[j:]作为s[i+1:]的子序列，子序列数为dp[i+1][j]。综合 2 种情况，当s[i] == t[j]时，dp[i][j] = dp[i+1][j+1] + dp[i+1][j]。如果
s[i] != t[j]，此时t[j:]只能作为s[i+1:]的子序列，子序列数为dp[i+1][j]。所以当s[i] != t[j]时，dp[i][j] = dp[i+1][j]。综上分析得：$$dp[i][j] = \left{\begin{matrix}dp[i+1][j+1]+dp[i+1][j]&,s[i]=t[j]\ dp[i+1][j]&,s[i]!=t[j]\end{matrix}\right.$$
最后是优化版本。写出上述代码以后，可以发现填表的过程是从右下角一直填到左上角。填表顺序是 从下往上一行一行的填。行内从右往左填。于是可以将这个二维数据压缩到一维。因为填充当前行只需要用到它的下一行信息即可，更进一步，用到的是下一行中右边元素的信息。于是可以每次更新该行时，先将旧的值存起来，计算更新该行的时候从右往左更新。这样做即可减少一维空间，将原来的二维数组压缩到一维数组。
package leetcode // 解法一 压缩版 DPfuncnumDistinct(sstring, tstring) int { dp:=make([]int, len(s)+1) fori, curT:=ranget { pre:=0forj, curS:=ranges { ifi==0 { pre=1 } newDP:=dp[j+1] ifcurT==curS { dp[j+1] =dp[j] +pre } else { dp[j+1] =dp[j] } pre=newDP } } returndp[len(s)] } // 解法二 普通 DPfuncnumDistinct1(s, tstring) int { m, n:=len(s), len(t) ifm<n { return0 } dp:=make([][]int, m+1) fori:=rangedp { dp[i] =make([]int, n+1) dp[i][n] =1 } fori:=m-1; i>=0; i-- { forj:=n-1; j>=0; j-- { ifs[i] ==t[j] { dp[i][j] =dp[i+1][j+1] +dp[i+1][j] } else { dp[i][j] =dp[i+1][j] } } } returndp[0][0] }