leetcode115. 不同的子序列

dp

f[i][j]表示s[0-i]和t[0-j]匹配时有多少种方案，s[i]==t[j]时，f[i][j]=f[i-1][j-1]+f[i-1][j]
[注]使用int会爆Int，所以将数组用usigned long long 存储。

class Solution {
public:
    int numDistinct(string s, string t) {
       int n=s.size(),m=t.size();
       if(n<m)return 0;
       vector<vector<unsigned long long>>f(n,vector<unsigned long long>(m,0));
       f[0][0]=s[0]==t[0];
       for(int i=1;i<n;i++)f[i][0]=f[i-1][0]+(s[i]==t[0]);//初始化，找到t[0]有多少种相同的字母
       for(int i=1;i<n;i++){
           for(int j=1;j<m;j++){
               if(s[i]==t[j])f[i][j]=f[i-1][j]+f[i-1][j-1];//相等
               else f[i][j]=f[i-1][j];//不等
           }
       }
       return f[n-1][m-1];
    }
};