Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE"
is a subsequence of "ABCDE"
while "AEC"
is not).
Here is an example:
S = "rabbbit"
, T = "rabbit"
Return 3
.
通过删除字符,有多少种办法将S变成T?
典型的DP,因为根据图来推的方程,所以我的方程有点奇怪。
dp[j][i]表示s的前i个字符有多少种方法可以变成T的前j个字符,
显然可以通过直接删除新增加的字符这种方式,所以
dp[j][i]=dp[j][i-1] ,
如果j和i匹配的话,也可以从j-1,i-1转移过来,所以
if(s[i-1]==t[j-1]) dp[j][i]+=dp[j-1][i-1];
class Solution {
public:
int numDistinct(string s, string t) {
vector<int> temp(s.size()+1,0);
vector<vector<int>> dp(t.size()+1,temp);
for(int i=0;i<=s.size();i++) dp[0][i]=1;//<span style="font-family: Arial, Helvetica, sans-serif;">0表示空串,</span><span style="font-family: Arial, Helvetica, sans-serif;">首先需要初始化边界情况,所有S变成空串都只有一种方法。</span>
for(int i=1;i<=s.size();i++)
{
for(int j=1;j<=i && j<=t.size();j++)
{
dp[j][i]=dp[j][i-1];
if(s[i-1]==t[j-1]) dp[j][i]+=dp[j-1][i-1];
}
}
return dp[t.size()][s.size()];
}
};