dp 力扣 115. 不同的子序列

题目：
链接：https://leetcode.cn/problems/distinct-subsequences/

思路：
使用动态规划思想
根据题目可得 题目要求为 字符串s 中得到 字符串t的方案总数。
dp[i][j]定义为从s[i]可以得到t[j]的方案的总数的集合
dp状态为count

dp[i][j]状态转移为： dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

代码：

class Solution {
public:
    long long dp[1010][1010];
    int numDistinct(string s, string t) {
        int n= s.size();
        int m= t.size();
        if(m>n)return 0;//t字符串大于s字符串不存在
        s='#'+s;
        t='#'+t;
        for(int i =0;i<=n;i++)
            dp[i][0]=1;//预处理
        for(int i =1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                if(s[i]==t[j]){//当s[i]==t[j]时需要加上之前s[i]与j匹配的情况
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                    if(dp[i][j]>1e9)dp[i][j]=0;
                }
                else {dp[i][j]=dp[i-1][j];//不等于时等于上一层的方案数
                    if(dp[i][j]>1e9)dp[i][j]=0;
                }
            }
        }
        return dp[n][m];
    }
};