[Day 14] Leetcode 115. Distinct Subsequences (C++)

前言

今日挑战的题目是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)，只要考虑到前一行的情形就好。