leetcode115 不同的子序列

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

例一
例二

分析

画图。

QQ图片20191230230828 (1).jpg

代码

class Solution {
public:
    int numDistinct(string s, string t) {
        if (s.empty() || t.empty()){
            return 0;
        }

        vector<vector<long long>> dp(t.size(), vector<long long>(s.size(), 0));

        for (int i = 0; i < t.size(); i++){
            for (int j = 0; j < s.size(); j++){
                if (i == 0 && j == 0){
                    dp[i][j] = s[j] == t[i] ? 1 : 0;
                }else if (i == 0){
                    dp[i][j] = s[j] == t[i] ? dp[i][j - 1] + 1 : dp[i][j - 1];
                }else if (j - 1 >= 0 && dp[i - 1][j] != 0){
                    dp[i][j] = s[j] == t[i] ? dp[i - 1][j - 1] + dp[i][j - 1] : dp[i][j - 1];
                }
            }
        }

        // for (auto v : dp){
        //     for (auto x : v){
        //         cout << x << " ";
        //     }
        //     cout << endl;
        // }

        return dp[t.size() - 1][s.size() - 1];
    }
};