不同的子序列
回溯法（超时）
class Solution { public: vector<int> path; vector<vector<int>> result; void backtracking(string s, string t , int deep ,int pre , vector<int> &path) { if(deep >= s.size()) return; if(pre >= t.size()) { if(find(result.begin() , result.end(),path)==result.end()) { for(int i=1 ; i<path.size();i++) { if(path[i] <= path[i-1]) return; } result.push_back(path); } return; } for(int i=deep ; i<s.size(); i++) { if(s[i] == t[pre] ) { path.push_back(i); backtracking(s,t,i,pre+1,path); path.pop_back(); } } return; } int numDistinct(string s, string t) { backtracking(s,t,0,0,path); return result.size(); } };
动态规划
- 确定dp数组（dp table）以及下标的含义
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。 - 确定递推公式
这一类问题，基本是要分析两种情况 - s[i - 1] 与 t[j - 1]相等
dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。
一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
s[i - 1] 与 t[j - 1] 不相等
dp[i][j] = dp[i - 1][j];
- dp数组如何初始化
dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。
那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。
再来看dp[0][j]，dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。
那么dp[0][j]一定都是0，s如论如何也变成不了t。
最后就要看一个特殊位置了，即：dp[0][0] 应该是多少。
dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。
class Solution { public: int numDistinct(string s, string t) { vector<vector<uint64_t>> dp(s.size()+1 , vector<uint64_t>(t.size()+1,0) ); for(int i=1 ; i<s.size()+1 ;i++) dp[i][0] = 1; for(int j=1 ;j<t.size()+1 ;j++) dp[0][j] = 0; dp[0][0] = 1; for(int i=0 ; i<s.size() ;i++) { for(int j=0 ;j<t.size();j++) { if(s[i]==t[j]) dp[i+1][j+1] = dp[i][j] + dp[i][j+1]; else dp[i+1][j+1] = dp[i][j+1]; } } return dp[s.size()][t.size()]; } };
二刷
class Solution { public: int numDistinct(string s, string t) { vector<vector<unsigned long long>> dp(s.size()+1 , vector<unsigned long long>(t.size()+1,0)); for(int i=0 ; i<=s.size() ;i++) dp[i][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]; else dp[i][j] = dp[i-1][j]; // cout<<dp[i][j]<<' '; } // cout<<endl; } return dp[s.size()][t.size()]; } };
