题解 | #不同的子序列#

// 状态F[i,j]：S的前i个字符的子序列 与 T的前j个字符相等 的不同子序列数
// 转移方程：F[i,j]=?这里要进行一个判断：
//          如果S[i-1]==T[j-1],则S的第i个字符可以使用，但我们可以选择是否使用
//          1.使用：F(i,j)=F(i-1,j-1)
//          2.不使用：F(i,j)=F(i-1,j)
//          即F(i,j)=F(i-1,j)+F(i-1,j-1)
//          如果S[i]！=T[j],则S的第i个字符不可以使用
//          F(i,j)=F(i-1,j)
// 初始值：F(i,0)=1; F(0,j)=0(j>=1)
// 返回结果：F(s.size(),t.size())
class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return int整型
     */
    int numDistinct(string S, string T) {
        if(S.size()<T.size())
            return 0;
        if(T.empty())
            return 1;
        int row=S.size();
        int col=T.size();
        vector<vector<int> > ret(row+1,vector<int>(col+1,0));
        for(int i=0;i<=row;i++)
        {
            ret[i][0]=1;
        }
        for(int i=1;i<=row;i++)
        {
            for(int j=1;j<=col;j++)
            {
                if(S[i-1]==T[j-1])
                    ret[i][j]=ret[i-1][j-1]+ret[i-1][j];
                else
                    ret[i][j]=ret[i-1][j];
            }
        }
        return ret[row][col];
    }
};