distinct-subsequences

• 状态定义：dp[i][j]代表s[0_i-1]中T[0j-1]不同子串的个数。

• 递推关系式：S[i-1]!= T[j-1]： DP[i][j] = DP[i-1][j] （不选择S中的s[i-1]字符）

•          S[i-1]==T[j-1]： DP[i][j] = DP[i-1][j-1]（选择S中的s[i-1]字符） + DP[i-1][j]（不选择S中的s[i-1]字符）
  

• 初始状态：第0列：DP[i][0] = 1，第0行：DP[0][j] = 0

class Solution {
public:
    int numDistinct(string S, string T) {
        int len=T.length();
        vector<int>dp(len+1,0);
        dp[0]=1;
        for(int i=1;i<=S.length();i++)
        {
            for(int j=min(len,i);j>0;j--)
            {
                if(S[i-1]==T[j-1])dp[j]+=dp[j-1];
            }
        }
        return dp[T.length()];
    }
};