题目来源：力扣115
解法思路：使用动态规划
定义 dp[i][j]为考虑 s 中 [0,i-1]个字符，t 中 [0,j-1] 个字符的匹配个数。
那么显然对于某个dp[i][j] 而言，从「最后一步」的匹配进行分析，包含两类决策：
1、不让 s[i] 参与匹配，也就是需要让 s 中 [0,i−1]个字符去匹配 t 中的 [0,j-1]字符。此时匹配值为 dp[i][j]
2、让 s[i] 参与匹配，这时候只需要让 s 中 [0,i−2]个字符去匹配 t 中的 [0,j−1]字符即可，同时满足 s[i-1]=t[j-1]。此时匹配值为 dp[i-1][j]
最终 dp[i][j] 就是两者之和。
初始化：
根据dp[i][j]的定义需要初始化 dp[i][0]和dp[0][j]
再看看dp[i][j]的定义可以知道 dp[i][0] 全为1；dp[0][j]全为0；dp[0][0]为1
完整代码
点击查看代码
class Solution {
public:
int numDistinct(string s, string t) {
//因为要求的是 s字符串中有多少个t,所以s字符串长度应该大于等于t字符串长度
if(s.size() < t.size()) return 0;
//vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
//dp[i][j] 表示 s串中以第i-1为结尾的字符串中包含 t串中到第j-1 为结尾的字符串个数
//初始化
for(int i=1;i<s.size();i++)
dp[i][0] = 1;
for(int j=1;j<t.size();j++)
dp[0][j] = 0;
dp[0][0] = 1;
//遍历
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];
//dp[i-1][j-1]表示使用s[i-1]
//dP[i-1][j]表示不使用s[i-1]
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[s.size()][t.size()];
}
};