LeetCode| Distinct Subseqences

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.

思路：

这是一个典型的DP问题，我们需要维护一个遍历，这里维护的变量为dp[i][j],表示src的前i个字符和dst的前j个字符所符合要求的序列数目，假设二维数组之前的都已经被初始化，那么如果src[i] == dst[j]，也就是当前这两个字符相等，那么dp[i-1][j-1]肯定是符合要求的，同时dp[i-1][j]也是符合要求的，那么dp[i][j]= dp[i-1][j-1]+dp[i-1][j]。如果src[i]!=dst[j].也就是当前这两个字符不相等，那么dp[i][j]= dp[i-1][j-1]

int Distinct_sub(string src,string dst)
{
	vector<vector<int> > dp(src.size());
	int i,j;
	for(i=0;i<src.size();i++)
		dp[i].assign(dst.size(),0);

	if(src[0] == dst[0])
		dp[0][0] =1;
	for(j=1;j<dp.size();j++)
		dp[j][0] = src[j]==dst[0]? dp[j-1][0]+1:dp[j-1][0];

	for(i=1;i<dp.size();i++)
	{
		for(j=1;j<dp[0].size();j++)
		{
			if(src[i] == dst[j])
			//	dp[i][j] = dp[i-1][j-1]>dp[i-1][j]+1?dp[i-1][j-1]:dp[i-1][j]+1; 注意这里 刚开始不知道咋思考的 
				dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
			else
				dp[i][j] = dp[i-1][j];
		}
	}
	return dp[src.size()-1][dst.size()-1];
}

int main()
{
	string src("rabbbit");
	string dst("rabbit");
	cout<<Distinct_sub(src,dst)<<endl;	
	 
	return 0;
}

LeetCode| Distinct Subseqences

原文：http://blog.csdn.net/yusiguyuan/article/details/44646319