动态规划
设f(i, j)是s[0...i)中t[0...j]匹配到的个数
Base:
当t为空时，s总能成功匹配t
转移方程：
当s[i] == t[j]时
s[i]让自己和t[j]匹配：那么f(i + 1, j + 1)的值就包括了f(i, j)s[i]不让自己和t[j]匹配：那么对于s[0...i+1)来说，因为没有匹配，所以f(i + 1, j + 1)的值就包括f(i, j + 1)，就是让前面s[0...i)去和t[0...j + 1)匹配
当s[i] != t[j]时
只能由前面的字符串去和t[0...i + 1)尝试匹配了。
所以最终的递推方程也由此得到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int numDistinct(string s, string t) {
int m = s.size(), n = t.size();
if(m < n)
return 0;
vector<vector<unsigned int>> dp(m + 1, vector<unsigned int>(n + 1));
dp[0][0] = 1;
for(int i = 0; i < m; ++i)
{
dp[i + 1][0] = 1;
for(int j = 0; j < n; ++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.back().back();
}
};
|