leetcode-115-Distinct Subsequences

#include <iostream>
#include <string.h>
using namespace std;
/*
 蠻典型的dp，因為跟MIT的課程裡的LCS算法很像，也是建構一個備忘表，
 尋找備忘表元素之間的關系，關系無法一眼看出，後來看了分析，這樣了解，
 比如找的是(i,j)的次數，如果s[i]==t[j],那麼有兩種選法，一種是選了
 s[i],那麼(i,j)的次數就是(i-1,j-1)的次數；不選s[i]的話，就是
 (i-1,j)的次數；如果s[i]!=t[j]，就隻有第二種選法了，也就是
 (i-1,j)的次數。如果是像MIT公開課裡面說的那樣，用一個二維的備忘表，
 那麼就是從左上角到右下角的順序計算就好了，比較直覺，但是這樣需要O(n^2)
 的空間複雜度，改進的是用一個長度為T的長度加1的一位數組代替，這樣複雜度
 就隻是O(n),不過注意的是這樣的話雖然可以從上到下計算，但是計算每一行的
 時候要從右到左，因為目前位置的值要用到上一行的前一個位置的值，這樣算到
 數組最後一個元素就是結果了。
 */
class Solution {
public:
    int numDistinct(string s, string t) {
        int len = t.length();
        int *memo = new int[len + 1];
        for (int i = 0; i < len + 1; i++) {
            memo[i] = 0;
        }
        memo[0] = 1;
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = len - 1; j >= 0; j--) {
                memo[j + 1] += s[i - 1] == t[j] ? memo[j] : 0;
            }
        }
        return memo[len];
    }
};
int main(int argc, const char * argv[]) {
    Solution s;
    cout << s.numDistinct("rabbbit", "rabbit") << endl;
    return 0;
}