leetcode第一刷_Distinct Subsequences

應該可以想到是個dp，但是轉移方程很難理解。

首先要理解題目要的是什麼，求s中包含了多少個形式為t的字串。那麼中間結果保存的應該是什麼呢？有三種選擇，第一，p[i]表示s的前i個字符包含了多少個t，那看看規模擴大時，小規模怎麼更新到大規模，當s的長度增加1的時候有什麼變化呢，p[i]應該是在p[i-1]的基礎上加個數的，但t的規模是固定的，做不到更新。比如aaab中包含了一個ab，那麼aaabb中包含多少個呢，完全推不出來出來啊親，pass。第二，p[j]表示s中包含多少個t的前j個字符，看看這個行不行，不行啊親，怎麼想這小規模和大規模之間也沒聯系啊，s中包含多少個ab跟s中包含多少個a，是沒有直接的關系的。只剩下最後一種選擇了，p[i][j]表示s的前i個字符中包含多少個t的前j個字符。總算有點子問題的樣子了。

好，下面看看p[i][j]跟什麼有關系，顯然，p[i][j]一定是包含p[i-1][j]的，因為s多考慮了一個字符，個數一定至少是之前的那個量。那麼怎麼更新呢？看s[i]和t[j]之間的關系，如果他們相等，那麼p[i][j]還應該包含p[i-1][j-1]，因為同時增加一個字符，仍然保持了t是s的一部分的性質，如果不相等，那麼說明我們應該跳過s的這個字符，它沒有用處。

關於邊界的計算，當t的長度是0時，即它為空，無論s多長，都肯定包含了一個它。

方程我就不列了，上面的分析應該比較說明問題了。dp的代碼永遠那麼簡單，哎：

class Solution {
public:
    int numDistinct(string S, string T) {
        int len1 = S.length(),  len2 = T.length();
        if(len2>len1)   return 0;
        int p[len1+1][len2+1];
        memset(p, 0, sizeof(p));
        for(int i=0;i<=len1;i++)    p[i][0] = 1;
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                p[i][j] = p[i-1][j]+(S[i-1] == T[j-1]?p[i-1][j-1]:0);
            }
        }
        return p[len1][len2];
    }
};