給定一個字符串?S?和一個字符串?T，計算在 S 的子序列中 T 出現的個數。

一個字符串的一個子序列是指，通過刪除一些（也可以不刪除）字符且不干擾剩余字符相對位置所組成的新字符串。（例如，"ACE"?是?"ABCDE"?的一個子序列，而?"AEC"?不是）

示例?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
? ? ^^^

思路：

動態規劃

dp[i][j] 代表 T 前 i 字符串可以由 S j 字符串組成最多個數.

所以動態方程:

當 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()];}
}

?