学步园

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，如果大家还记得去年谷歌校招笔试最后的那道编辑距离的算法题的话，这道题相比也不在话下的~ : )

我们定义 f(i,j ) 表示的是 S 的前i个字符和 T 的前 j 个字符能有多少种匹配，注意当i=0的时候 f(0 ,j) =0, 反过来j=0的时候，f(i,0)=1，这是因为T为空的时候，任意长的S都可以匹配的！下面我们来推导转移方程。

假设当前我们正在求 f( i, j )，那么跟前面的结果有什么关系呢？很明显：

1.i<j的时候，S中的长度都不够，肯定不能匹配的，f( i,j )=0;

2. s[i-1]==t[j-1] （要转换为下标）的时候，意味着我们当前有两种选择，一个是留下S[i-1]这个字符来匹配T[j-1]，然后结果取决于 f(i-1,j-1)，另一个不要这个S[i-1]，用S之前的字符去匹配T，结果为  f( i-1,j)，所以总结为  f (i, j) = f( i-1,j-1) + f(i-1,j);

3.s[i-1]!=t[j-1]时候，我们只能尝试用之前的S去匹配T，f(i,j) = f(i-1,j);

这下很好写了，代码如下：

class Solution {
public:
    int numDistinct(string s,string t)
{
    int ns=s.length(),nt=t.length();
	if ( ns<nt)
		return 0;
	vector<vector<int> > dp(ns+1,vector<int>(nt+1,0));
	dp[0][0]=1;
	int i,j;
    for(i=0;i<=ns;i++)
    		dp[i][0]=1;
	for(i=1;i<=ns;i++)
		for(j=1;j<=nt;j++)
		{
			if(i<j)
				dp[i][j]=0;
			else
			{
				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];
			}
		}
	return dp[ns][nt];
}

};