115.不同的子序列

题目描述

给你两个字符串s和t，统计并返回在s的子序列中t出现的个数，结果需要对10^9+7取模。

示例1：

输入：s = "rabbbit"，t = “rabbit"
输出：3
解释：
如下所示，有3种可以从s种得到"rabbit"的方案
rabbbit
rabbbit
rabbbit

示例2：

输入：s = "babgbag"，t = “bag"
输出：5
解释：
如下所示，有5种可以从s种得到"bag"的方案
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

• 1<=s.length,t.length<=1000
• s和t由英文字母组成

解题思路

1. 确定dp数组 dp[i][j]：以i-1为结尾的子序列s出现以j-1为结尾的子序列t的个数为dp[i][j]
2. 递推公式

• s[i-1] == t[j-1] dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
• s[i-1] != t[j-1] 相当于模拟删除元素(只删除s里面的元素) dp[i][j] = dp[i-1][j]

3. dp数组初始化

• dp[i][0]=1
• dp[0][j]=0
• dp[0][0]=1

4. 遍历顺序 从左到右，从上到下
5. 打印dp数组

代码实现

核心模式

class Solution{
    public:
    int numDistinct(string s, string t){
       vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1)); 
       // initialize the DP array
       for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
       for (int j = 1; j < t.size(); j++) dp[0][j] = 0;

       // traversal; 
       for (int i = 1; i <= s.size(); i++){
            for (int j = 1; j <= t.size(); j++){
                if (s[i - 1] == t[j - 1]) 
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else 
                    dp[i][j] = dp[i - 1][j];
            }
       }
        return dp[s.size()][t.size()];
    }
};

ACM模式

"dynamicPro.h"

#include <iostream>
#include "dynamicPro.h"

class Solution{
    public:
    int numDistinct(string s, string t){
       vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1)); 
       // initialize the DP array
       for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
       for (int j = 1; j < t.size(); j++) dp[0][j] = 0;

       // traversal; 
       for (int i = 1; i <= s.size(); i++){
            for (int j = 1; j <= t.size(); j++){
                if (s[i - 1] == t[j - 1]) 
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else 
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[s.size()][t.size()];
    }
};


int main(){
    Solution solution;
    cout << "Result1 = " << solution.numDistinct("rabbbit", "rabbit"); 
    cout << "Result2 = " << solution.numDistinct("babgbag", "bag"); 

    return 0;
}

• 输出

Result1 = 3
Result2 = 5