class Solution {
public:
int numDistinct(string s, string t) {
int rows = s.size();
int cols = t.size();
int dp[rows + 1][cols + 1] = {0};
//当T为空，T的子串在S中出现的次数是1，因为空串也是子串
for(int i = 0 ; i < rows + 1 ; i++){
dp[i][0] = 1;
}
//当S为空，T的子串在S中出现的次数为0
for(int k = 1 ; k < cols + 1 ; k++){
dp[0][k] = 0;
}
for(int i = 1 ; i < cols + 1 ; i++){
for(int j = 1 ; j < rows + 1 ; j++){
if(s[j-1] == t[i-1]){
dp[j][i] = dp[j-1][i-1] + dp[j-1][i];
}
else{
dp[j][i] = dp[j-1][i];
}
}
}
return dp[rows][cols];
}
};
//首先这道题的题意一开始没看懂，但是大概就是从开始到当前字符的公共子串的个数
//中间出现错误就是对应的i,j的关系并不是随意的，从定下来谁是行谁是列就开始确定了dp的下标位置也确定了
//按照矩阵的角度去考虑
链接点击打开链接
点击打开链接
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
int numDistinct(string s, string t) {
//int rows = t.size();
//int cols = s.size();
int dp[100][100] = { 0 };
//当T为空，T的子串在S中出现的次数是1，因为空串也是S的子串
for (int i = 0; i < s.size() + 1; i++){
dp[0][i] = 1;
}
//当S为空，T的子串在S中出现的次数为0、
for (int k = 1; k < t.size() + 1; k++){
dp[k][0] = 0;
}
for (int i = 1; i < t.size() + 1; i++){
cout << "------------" << endl;
for (int j = 1; j < s.size() + 1; j++){
//cout << "------------" << endl;
//只是状态的延续，不是字符的位置变动
dp[i][j] = dp[i][j - 1];
if (t[i - 1] == s[j - 1]) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return dp[t.size()][s.size()];
}
};
int main(){
int res;
Solution obj;
string s = "rrrrr";
string t = "r";
//X = { { 1 }, { 2, 3 } };
res = obj.numDistinct(s, t);
cout << res << endl;
while (1);
return 1;
}
