題目描述

給你兩個(gè)字符串 s 和 t ，統(tǒng)計(jì)并返回在 s 的 子序列 中 t 出現(xiàn)的個(gè)數(shù)，結(jié)果需要對(duì) 109 + 7 取模。

示例：

輸入：s = "babgbag", t = "bag"

輸出：5

解釋：

如下所示, 有 5 種可以從 s 中得到 "bag" 的方案。

babgbag

babgbag

babgbag

babgbag

babgbag

為了解決這個(gè)問(wèn)題，我們首先需要理解題目中的關(guān)鍵概念：“子序列”和“出現(xiàn)的個(gè)數(shù)”。子序列是指從原字符串中刪除一些（或者不刪除）字符而不改變剩余字符的相對(duì)順序所得到的新字符串。例如，字符串 "abc" 的子序列包括 "a", "b", "c", "ab", "ac", "bc", "abc", ""（空字符串）等。

接下來(lái)，我們要計(jì)算在字符串?s?的所有子序列中，字符串?t?出現(xiàn)的次數(shù)。這可以通過(guò)動(dòng)態(tài)規(guī)劃（Dynamic Programming, DP）來(lái)有效地解決。

解題思路

我們可以使用二維數(shù)組?dp[i][j]?來(lái)表示狀態(tài)，其中?dp[i][j]?表示?s?的前?i?個(gè)字符（即?s[0...i-1]）中包含?t?的前?j?個(gè)字符（即?t[0...j-1]）作為子序列的個(gè)數(shù)。注意這里的?i?和?j?都是從 1 開(kāi)始的，方便處理邊界情況。

1. 初始化：dp[0][j] = 0?對(duì)于所有的?j（因?yàn)榭兆址话魏畏强兆址淖有蛄?#xff09;，dp[i][0] = 1?對(duì)于所有的?i（因?yàn)槿魏巫址及兆址鳛樽有蛄?#xff09;。

2. 狀態(tài)轉(zhuǎn)移方程：

   • 如果?s[i-1] == t[j-1]，則有兩種情況：
     • 包含當(dāng)前字符?s[i-1]?作為?t[j-1]?的一部分：dp[i-1][j-1]
     • 不包含當(dāng)前字符?s[i-1]：dp[i-1][j]
       因此，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。
   • 如果?s[i-1] != t[j-1]，則只有一種情況：
     • 不包含當(dāng)前字符?s[i-1]：dp[i-1][j]
       因此，dp[i][j] = dp[i-1][j]。

3. 結(jié)果：dp[n][m]，其中 n?和 m?分別是字符串?s?和?t?的長(zhǎng)度。

怎樣想到這樣狀態(tài)方程的？

一點(diǎn)個(gè)人經(jīng)驗(yàn)，見(jiàn)過(guò)的很多2個(gè)串的題，大部分都是dp[i][j] 分別表示s串[0...i] 和t串[0...j]怎么怎么樣然后都是觀察s[i]和t[j]分等或者不等的情況 而且方程通常就是 dp[i-1][j-1] 要么+ 要么 || dp[i-1][j]類(lèi)似的。

class Solution {
public:const int MOD = 1e9 + 7;int numDistinct(string s, string t) {int n = s.size();int m = t.size();vector<vector<int>> dp(n+1, vector<int>(m+1, 0));//dp[i][j]: t[0~j]子串在 s[0~i]子序列中出現(xiàn)的個(gè)數(shù)for(int i=0;i<n;i++){           dp[i][0] = 1;//空字符串是任何字符串的子序列}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(j>i)continue;//無(wú)法在較小的字符串中出現(xiàn)更大的字符串if(s[i-1] == t[j-1]){dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%MOD;}else{dp[i][j] = dp[i-1][j];}}} return dp[n][m];   }
};