數據結構和算法 - 633，動態規劃解不同的子序列－鑽石舞台

問題描述

來源：LeetCode第115題

難度：困難

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

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

題目數據保證答案符合32位帶符號整數範圍。

示例 1：

輸入：s = "rabbbit", t = "rabbit"

輸出：3

解釋：

如下圖所示, 有3種可以從s中得到"rabbit"的方案。

rabbbit

示例 2：

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

輸出：5

解釋：

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

babgbag

提示：

0<=s.length, t.length<=1000

s和t由英文字母組成

動態規劃解決

這題說的是s的子序列中出現t的個數，翻譯一下就是字符串s的所有子序列中，和字符串t完全一樣的有多少個。

我們定義dp[i][j]表示t的前i個字符可以由s的前j個字符組成的個數（也可以說是字符串s的前j個字符組成的子序列中，和字符串t的前i個字符組成的字符串一樣的有多少個）。

那麼最終我們只需要求出dp[tLength][sLength]即可（其中tLength和sLength分別表示字符串t和s的長度）。

如果字符串t的第i個字符和字符串s的第j個字符一樣，如下所示

如上圖所示我們可以有兩種選擇。

如果字符串t的第i個字符和字符串s的第j個字符不一樣，也就是說字符串s的第j個字符不能匹配字符串t的第i個字符。那麼我們只能計算字符串s的前j-1個字符構成的子序列中包含字符串t的前i個字符組成的字符串的個數。

所以遞推公式如下

for(intj=1;j<=sLength;j++){if(t.charAt(i-1)==s.charAt(j-1)){//如果字符串t的第i個字符和s的第j個字符一樣，//那麼有兩種選擇dp[i][j]=dp[i-1][j-1]+dp[i][j-1];}else{//如果字符串t的第i個字符和s的第j個字符不一樣，//我們只能用字符串s的前j-1個字符來計算他包含的數量dp[i][j]=dp[i][j-1];}

動態規劃的三個步驟就是定義狀態，列出遞推公式，找出邊界條件。前面兩步我們都完成了，我們來看最後一個。因為空字符串""是所有字符串的子集，所以當字符串t為空的時候，dp[0][j]=1;

我們來看下最終代碼

publicintnumDistinct(Strings,Stringt){//sLength和tLength分別是兩個字符串的長度intsLength=s.length();inttLength=t.length();int[][]dp=newint[tLength+1][sLength+1];//basecase邊界條件for(intj=0;j<=sLength;j++){dp[0][j]=1;}for(inti=1;i<=tLength;i++){for(intj=1;j<=sLength;j++){//下面是遞推公式if(t.charAt(i-1)==s.charAt(j-1)){//如果字符串t的第i個字符和s的第j個字符一樣，//那麼有兩種選擇dp[i][j]=dp[i-1][j-1]+dp[i][j-1];}else{//如果字符串t的第i個字符和s的第j個字符不一樣，//我們只能用字符串s的前j-1個字符來計算他包含的數量dp[i][j]=dp[i][j-1];}}}returndp[tLength][sLength];}