Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 115. Distinct Subsequences

---

題目：


解答：

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size();
        int m = t.size();
        vector<vector<int>> memo(n + 1, vector<int>(m + 1, -1));

        auto dfs = [&](this auto&& dfs, int start, int pos) -> int {
            if (memo[start][pos] != -1) {
                return memo[start][pos];
            }

            if (n - start < m - pos) {
                return 0;
            }

            if (pos >= m) {
                return 1;
            }

            int ans = 0;

            for (int i = start; i < n; ++i) {
                if (t[pos] == s[i]) {
                    ans += dfs(i + 1, pos + 1);
                }
            }

            memo[start][pos] = ans;
            return ans; 
        };

        return dfs(0, 0);
    }
};