描述
给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？
字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，”ACE”is a subsequence of”ABCDE”但是”AEC”不是）
例如：
S=”nowcccoder”, T = “nowccoder”
返回3
示例1
输入：
"nowcccoder","nowccoder"
返回值：
3
// 关键在于弄清楚对退公式与状态矩阵 // dp[i][j] 表示 S中的前i个字符构成的字符串包含 T 中前j个字符构成的字符串的 子串的个数 // 当S【i-1】 == t【j-1】时， 则新的dp值可以是 不使用第i个字符，却能构成T中j子串的个数dp[i][j] 加上 // 不使用第i个字符能构成T中j-1子串的个数dp[i-1][j-1] // 否则，只能是等于dp[i-1][j] class Solution { public: int numDistinct(string S, string T) { int slen = S.length(); int tlen = T.length(); vector<vector<int>> dp; vector<int> temp(tlen+1,0); temp[0] = 1; for( int i = 0; i <= slen; i++) dp.push_back( temp ); for( int i = 1; i <= slen ; i++) for(int j = 1 ; j <= tlen ; j++) { if( S[i-1] == T[j-1] ) dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; else dp[i][j] = dp[i-1][j]; } return dp[slen][tlen]; } };2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/151275.html
