前言

今日挑戰的題目是115. Distinct Subsequences，雖然是hard，但因為有點想法，感覺可以挑戰一下XD 就一起來破解這題難題吧！

想法

首先想法是，要在不破壞順序的情形下，可以隨意刪除字元，讓剩下的字元可以組成target字串。這樣的話，就又是dp出場的時候了，因為這可以拆成比較簡單的子問題形式。我們可以用dp來存s中每個位置的可能答案總數，為了單純化，我們可以先假設t只有一個字元，那這問題是不是就變得很簡單？從s[0]開始看，如果s[0]==t，那dp[0]就=1，如果走到第二格發現s[1]也==t，那我們就知道有兩個可能，所以就dp[1]=dp[0]+1=2，如果走到s的第三格發現s[2]!=t，那仍然只有兩個可能，dp[2]=dp[1]+0=2。
現在我們進一步考慮t不只一個字元的情形，我們就讓dp變成二維的，dp[i][j]代表在s[:i]的字串中，可以有多少t[:j]的可能組合；更新的方式就會變成dp[i][j]=dp[i-1][j] + s[i]==t[j]?dp[i-1][j-1]:0；為什麼？如果不相等的話很簡單，就=隔壁的情形；那如果相等的話就會有更多可能的結果，那會多多少組合？你可以試著列列看簡單的範例，重點就是要多多少排列組合。
寫成程式如下：

class Solution {
public:
    int numDistinct(string s, string t) {
        
        // use dp to save the possibilities
        int sl = s.length();
        int tl = t.length();
        vector<vector<unsigned long long>> cnt (sl, vector<unsigned long long>(tl,0));
        //vector<vector<long long>> cnt (sl, vector<long long>(tl,0));

        // for the first word in t
        cnt[0][0] = (s[0]==t[0])?1:0;
        for(int i=1;i<sl;++i){
            cnt[i][0] = cnt[i-1][0] + (s[i]==t[0]);
        }
        // for other rounds
        for(int i=1;i<sl;++i){
            for(int j=1;j<tl;++j){
                cnt[i][j] = cnt[i-1][j] + (s[i]==t[j])*cnt[i-1][j-1];
            }
        }
        return cnt[sl-1][tl-1];
        
    }
};

還有中間的坑是test case讓answer變成超大的數，要unsigned long long才存得下...若要查詢每個型別的容納數範圍可以參考這邊。

結語

雖然是hard但其實dp類型問題就是一旦掌握到更新的方式，就可以做出來了。接下來也可以再多多挑戰這類的題目~
而這題也跟其他dp一樣，也有辦法優化空間複雜度從O(m*n)變成O(n)，只要考慮到前一行的情形就好。