115. Distinct Subsequences

Problem:

思路：

用DP算法。状态方程为：

s[i-1] == t[j-1]  dp[i][j] = dp[i-1][j-1] + dp[i-1][j]    //如果相等时，就考虑2种可能情况，包括s[i-1]和不包括s[i-1]的情况。
s[i-1] != t[j-1]  dp[i][j] = dp[i-1][j]                   //不相等时只需考虑不包括s[i-1]的情况。

Solution (C++):

int numDistinct(string s, string t) {
    int m = s.size(), n = t.size();     //size()和length()方法均可
    vector<vector<long>> dp(m+1, vector<long>(n+1, 0));
    for (int i = 0; i < m; ++i)  dp[i][0] = 1;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            dp[i][j] = dp[i-1][j] + (s[i-1] == t[j-1] ? dp[i-1][j-1] : 0);
    
    return dp[m][n];
}

性能：

Runtime: 12 ms  Memory Usage: 15.6 MB

思路：

Solution (C++):

int m = s.size(), n = t.size();     //size()和length()方法均可
vector<long long> dp(n+1, 0);
dp[0]= 1;
for (int i = 1; i <= m; ++i) {
    int pre = 1;
    for (int j = 1; j <= n; ++j) {
        int tmp = dp[j];
        dp[j] += (s[i-1] == t[j-1] ? pre : 0);
        pre = tmp;
    }
}
return dp[n];

性能：

Runtime: 8 ms  Memory Usage: 8.9 MB