不同的子序列

---

image.png

dp存储该点含之前的所有子序列匹配的解个数。首先对第一列初始化，先确定第一个是否匹配然后再从第二位根据dp[0][i-1]+s[j]==t[i]?1:0初始化。之后根据dp[i-1][j-1]+dp[i][j-1]计算对应位的值。

• 坑点：（1）状态转移方程（2）long long 防溢出（3）返回dp[-1][-1]

class Solution {
public:
    long long numDistinct(string s, string t) {
        if(t.length()==0||s.length()==0||t.length()>s.length()){
            return 0;
        }        
        long long dp[1005][1005]={0};
        int i,j;
        int pre=0;
        if(s[0]==t[0]){
            dp[0][0]=1;
        }
        for(i=1;i<s.length();i++){
            dp[0][i]=dp[0][i-1]+(s[i]==t[0]?1:0);
        }
        for(i=1;i<t.length();i++){
            for(j=i;j<s.length();j++){
                if(t[i]==s[j]){
                    dp[i][j]=dp[i-1][j-1]+dp[i][j-1];
                }
                else{
                    dp[i][j]=dp[i][j-1];
                }
            }
        }
        return dp[t.length()-1][s.length()-1];
    }
};