[LeetCode]Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, 

"ACE"

 is a subsequence of 

"ABCDE"

 while 

"AEC"

 is not).

Here is an example:

S = 

"rabbbit"

, T = 

"rabbit"

Return 

3

.

此題跟LCS比較類似，狀态由S和T一起決定，是以設狀态d(i, j)表示S的前i個字元串中以T的前j個字元為子串的不同子串數量。（如果沒了解題意再仔細讀讀，我讀了好幾遍才明白題意）

那麼d(i, j)的狀态轉移選擇有兩個：

(1) 放棄字元s[i]，原來的模闆字元串T不變，轉移到d(i - 1, j)

(2) 如果s[i]=t[j]，那麼還可以選擇将s[i]和s[j]比對，轉移到d(i - 1, j - 1)

是以，狀态轉移方程為

d(i , j) = sum{ d(i - 1, j),  d(i - 1, j - 1)(if s[i]=t[j]) }

邊界條件是當模闆字元串T為空時，任何字元串S都有一種方式和T比對（将S中所有字元全部删掉）

是以d(i, 0) = 1

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

上面的寫法比較浪費空間，實際上i-1以前的狀态在後面的計算中都用不到，是以可以使用一位數組來優化空間複雜度到O(m)。

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

注意m的周遊順序，是由大到小，保證每次通路數組中dp[j -1]時都是尚未被修改過的，即dp[i-1][j-1]，如果是以j遞增的順序周遊，那麼每次通路到的dp[j-1]則為dp[i][j-1]，這樣就不符合狀态轉移方程了。