392.判斷子序列

題目鏈接
**解題思路：**動態(tài)規(guī)劃五部曲分析如下：

1.確定dp數(shù)組（dp table）以及下標的含義

dp[i][j] 表示以下標i-1為結(jié)尾的字符串s，和以下標j-1為結(jié)尾的字符串t，相同子序列的長度為dp[i][j]。

注意這里是判斷s是否為t的子序列。即t的長度是大于等于s的。

有同學(xué)問了，為啥要表示下標i-1為結(jié)尾的字符串呢，為啥不表示下標i為結(jié)尾的字符串呢？

2.確定遞推公式

在確定遞推公式的時候，首先要考慮如下兩種操作，整理如下：

• if (s[i - 1] == t[j - 1])
  • t中找到了一個字符在s中也出現(xiàn)了
• if (s[i - 1] != t[j - 1])
  • 相當(dāng)于t要刪除元素，繼續(xù)匹配

if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因為找到了一個相同的字符，相同子序列長度自然要在dp[i-1][j-1]的基礎(chǔ)上加1（如果不理解，在回看一下dp[i][j]的定義）

if (s[i - 1] != t[j - 1])，此時相當(dāng)于t要刪除元素，t如果把當(dāng)前元素t[j - 1]刪除，那么dp[i][j] 的數(shù)值就是 看s[i - 1]與 t[j - 2]的比較結(jié)果了，即：dp[i][j] = dp[i][j - 1];

3.dp數(shù)組如何初始化

從遞推公式可以看出dp[i][j]都是依賴于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。

這里大家已經(jīng)可以發(fā)現(xiàn)，在定義dp[i][j]含義的時候為什么要表示以下標i-1為結(jié)尾的字符串s，和以下標j-1為結(jié)尾的字符串t，相同子序列的長度為dp[i][j]。

因為這樣的定義在dp二維矩陣中可以留出初始化的區(qū)間，如圖：

如果要是定義的dp[i][j]是以下標i為結(jié)尾的字符串s和以下標j為結(jié)尾的字符串t，初始化就比較麻煩了。

dp[i][0] 表示以下標i-1為結(jié)尾的字符串，與空字符串的相同子序列長度，所以為0. dp[0][j]同理。

vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));

4.確定遍歷順序

同理從遞推公式可以看出dp[i][j]都是依賴于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍歷順序也應(yīng)該是從上到下，從左到右
如圖所示：

5.舉例推導(dǎo)dp數(shù)組

以示例一為例，輸入：s = “abc”, t = “ahbgdc”，dp狀態(tài)轉(zhuǎn)移圖如下：

dp[i][j]表示以下標i-1為結(jié)尾的字符串s和以下標j-1為結(jié)尾的字符串t 相同子序列的長度，所以如果dp[s.size()][t.size()] 與 字符串s的長度相同說明：s與t的最長相同子序列就是s，那么s 就是 t 的子序列。

圖中dp[s.size()][t.size()] = 3， 而s.size() 也為3。所以s是t 的子序列，返回true。

動規(guī)五部曲分析完畢，C++代碼如下：

class Solution {
public:bool isSubsequence(string s, string t) {vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = dp[i][j - 1];}}if (dp[s.size()][t.size()] == s.size()) return true;return false;}
};

---

115.不同的子序列

題目鏈接
解題思路：

動規(guī)五部曲分析如下：

1.確定dp數(shù)組（dp table）以及下標的含義

dp[i][j]：以i-1為結(jié)尾的s子序列中出現(xiàn)以j-1為結(jié)尾的t的個數(shù)為dp[i][j]。

2.確定遞推公式

這一類問題，基本是要分析兩種情況

• s[i - 1] 與 t[j - 1]相等
• s[i - 1] 與 t[j - 1] 不相等

當(dāng)s[i - 1] 與 t[j - 1]相等時，dp[i][j]可以有兩部分組成。

一部分是用s[i - 1]來匹配，那么個數(shù)為dp[i - 1][j - 1]。即不需要考慮當(dāng)前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。

一部分是不用s[i - 1]來匹配，個數(shù)為dp[i - 1][j]。

例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]來匹配，即用s[0]s[1]s[2]組成的bag。

當(dāng)然也可以用s[3]來匹配，即：s[0]s[1]s[3]組成的bag。

所以當(dāng)s[i - 1] 與 t[j - 1]相等時，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

當(dāng)s[i - 1] 與 t[j - 1]不相等時，dp[i][j]只有一部分組成，不用s[i - 1]來匹配（就是模擬在s中刪除這個元素），即：dp[i - 1][j]

所以遞推公式為：dp[i][j] = dp[i - 1][j];

3.dp數(shù)組如何初始化

從遞推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是從上方和左上方推導(dǎo)而來，如圖：，那么 dp[i][0] 和dp[0][j]是一定要初始化的。

每次當(dāng)初始化的時候，都要回顧一下dp[i][j]的定義，不要憑感覺初始化。

dp[i][0]表示什么呢？

dp[i][0] 表示：以i-1為結(jié)尾的s可以隨便刪除元素，出現(xiàn)空字符串的個數(shù)。

那么dp[i][0]一定都是1，因為也就是把以i-1為結(jié)尾的s，刪除所有元素，出現(xiàn)空字符串的個數(shù)就是1。

再來看dp[0][j]，dp[0][j]：空字符串s可以隨便刪除元素，出現(xiàn)以j-1為結(jié)尾的字符串t的個數(shù)。

那么dp[0][j]一定都是0，s如論如何也變成不了t。

最后就要看一個特殊位置了，即：dp[0][0] 應(yīng)該是多少。

dp[0][0]應(yīng)該是1，空字符串s，可以刪除0個元素，變成空字符串t。

初始化分析完畢，代碼如下：

vector<vector<long long>> dp(s.size() + 1, vector<long long>(t.size() + 1));
for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;
for (int j = 1; j <= t.size(); j++) dp[0][j] = 0; // 其實這行代碼可以和dp數(shù)組初始化的時候放在一起，但我為了凸顯初始化的邏輯，所以還是加上了。

4.確定遍歷順序

從遞推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j]都是根據(jù)左上方和正上方推出來的。

所以遍歷的時候一定是從上到下，從左到右，這樣保證dp[i][j]可以根據(jù)之前計算出來的數(shù)值進行計算。

代碼如下：

for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); 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];}}
}

5.舉例推導(dǎo)dp數(shù)組

以s：“baegg”，t："bag"為例，推導(dǎo)dp數(shù)組狀態(tài)如下：

動規(guī)五部曲分析完畢，代碼如下：

class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));for (int i = 0; i < s.size(); i++) dp[i][0] = 1;for (int j = 1; j < t.size(); j++) dp[0][j] = 0;for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); 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[s.size()][t.size()];}
};