題目網址：https://leetcode.cn/problems/distinct-subsequences/

題意：給兩 string s 和 t, 返回在 s 的 subsequence 中 t 出現的個數。

題目保證答案符合 32-bit 有號整數的範圍。

Solution 1：

想法：利用 DP

1. 定義狀態：

  • dp[i][j]：s[1:i]中 subseq 為 t[1:j] 的個數

2. 得到轉移方程：

  • 當 s[i] == t[j] 時, 有兩種情況：

    • 用 s[i] 去匹配 t[j]：
      ➔ 則問題變成 s[1:(i-1)] 中 subseq 為 t[1:(j-1)] 的數量
      ➔ dp[i][j] = dp[i - 1][j - 1]
    • 不用 s[i] 去匹配 t[j]：
      ➔ 則問題變成 s[1:(i-1)] 中 subseq 為 t[1:j] 的數量
      ➔ dp[i][j] = dp[i - 1][j]

  • 否則, 問題變成 s[1:(i-1)] 中 subseq 為 t[1:j] 的數量
    ➔ dp[i][j] = dp[i - 1][j]

3. 初始化：

  • dp[i][0]：當 t = "" 時, s 中能匹配的 subseq 就只有 "" 一種（取法只有一種, 就是什麼都不取）
    ➔ dp[i][0] = 1
  • dp[0][j]：當 s = "" 時, 除了 dp[0][0] = 1 以外, 其餘的 dp[0][j] = 0, 其中 1 ≤ j ≤ n
class Solution {
public:
    int numDistinct(string s, string t) {
        const int m = s.size(), n = t.size();
        vector<vector<unsigned long>> dp(m + 1, vector<unsigned long>(n + 1, 0));

        s = '#' + s;
        t = '#' + t;

        for (int i = 0; i <= m; ++i) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= m; ++i) {
            for ( int j = 1; j <= n; ++j) {
                if (s[i] == t[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[m][n];
    }
};
  • time：$O(m \cdot n)$ ➔ for loop
  • space：$O(m \cdot n)$ ➔ dp

Solution 2：

想法：改善 Solution 1, 由於 dp[i][j] 只會用到上一列狀態的 dp[i - 1][j - 1] 和 dp[i - 1][j], 故只需要儲存上一列的狀態即可, 根本不需開到 $O(m \cdot n)$ space

class Solution {
public:
    int numDistinct(string s, string t) {
        const int m = s.size(), n = t.size();
        vector<unsigned long> dp(n + 1, 0);
        dp[0] = 1;

        s = '#' + s;
        t = '#' + t;

        for (int i = 1; i <= m; ++i) {
            vector<unsigned long> nextRow = dp;

            for (int j = 1; j <= n; ++j) {
                if (s[i] == t[j]) {
                    nextRow[j] = dp[j - 1] + dp[j];
                } else {
                    nextRow[j] = dp[j];
                }
            }

            dp = move(nextRow);
        }

        return dp.back();
    }
};
  • time：$O(m \cdot n)$ ➔ for loop
  • space：$O(n)$ ➔ dp