題目

給你兩個字符串 s 和 t ，統計并返回在 s 的 子序列 中 t 出現的個數。

測試用例保證結果在 32 位有符號整數范圍內。

思路

首先我們來考慮特殊情況，當s串的長度小于t串時s串肯定就沒有t串了。其他情況我們就需要想一想怎么做了，如果按照暴力做法我們就遍歷s串先找到t串的第一個字符然后再找第二個第三個，也就是一個一個字符的匹配，問題是題目設置的是s串的子序列而不是子串，子序列是不需要連續的所以這就導致找到了第一個字符后可能會有很多個第二個字符也就導致我們的時間復雜度會很高。那么我們是否可以換一種思想，既然是要一個一個的匹配也就是我們可以把兩個字符串拆分成一個一個的字符，我們定義一個二維數組dp，設s串的下標為i，t串的下標為j。我們設dp[i][j]是s[i,…]也就是i位置到末尾的s子串種t[j,…]即j到末尾的t子串的數量，簡單來說我們就是把這個問題分成了一個一個的子問題，我們利用這個二維數組來移動i和j從而得到不同的s子串中不同的t子串出現的個數。然后再找尋其中的規律推導出狀態轉移方程出來，所以我們是利用了動態規劃的思想，把大問題分成小問題。
那么這個二維數組dp我們要如何定義呢？我們需要定義成一個(n+1)*(m+1)的，n為s串的長度m為t串的長度。為什么要+1呢因為我們需要我們從這兩個子串是空串的情況開始，當s為空串t不為空串時dp[i][j] = 0因為一個空串里怎么可能有非空串，當s為非空串t為空串時dp[i][j] =1因為一個空串是任意一個非空串的子序列。所以dp[i][0] = 1( 0 <= i <= n)。在對特殊情況進行討論后我們現在就要移動i和j來得到每一個子問題的答案了，這里需要分成兩種情況。

1. s[i-1] == t[j-1]
   當此位置的字符相同時，我們需要考慮一個問題那就是這個字符是需要匹配的嗎，這是什么意思呢。我們還需要回顧一下題目說的是s串的子序列中t出現的個數，是子序列所以不是連續的所以在這兩個相等的字符前面可能還有和t[j]相同的s[i]，所以我們需要討論這兩種情況例如s:tbabag,t:bag。s的第一個a不是一定要和t的a進行匹配的也可以讓后面那個a來和t的a進行匹配，這就是為什么要考慮是否需要匹配。如果兩個字符匹配了那么此時的dp[i][j] = dp[i-1][j-1],也就是我們需要考慮t[j-1,…]作為s[i-1,…]的子序列的情況了，如果不匹配此時的dp[i][j] = dp[i-1][j]，因為不匹配也就是這個i被跳過了我們就需要考慮t[j]作為s[i-1]的子序列的情況了。
2. s[i]-1 != t[j-1]
   如果兩個字符不同就說明無法匹配,dp[i][j] = dp[i+1][j]。

代碼

class Solution {
public:int numDistinct(string s, string t) {int n = s.length();int m = t.length();if (n < m) {return 0;}//dp[i][j]代表t中從0到j的子串作為s中從0到i的子串的子序列的個數vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(m + 1));for (int i = 0; i <= n; i++) {dp[i][0] = 1;}for (int i = 1; i <= n; i++) {char si = s[i-1];for (int j = 1; j <= m; j++) {char tj = t[j-1];if (si == tj) {dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];} else {dp[i][j] = dp[i - 1][j];}}}return dp[n][m];}
};