LeetCode Distinct Subsequences

タイトル
iven 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の中でいくつかの文字を削除して、SをTに変換させて、異なる変換方法を求めます.
明らかにdpが必要であり,再帰解は必然的にタイムアウトする.
s[i]から始まるシーケンスとt[j]から始まるシーケンスのマッチング数num[i][j]の繰返し式は、
s[i]がt[j]に等しくない場合、s[i+1]から始まる文字列のみがt[j]から始まる文字列と一致し、num[i][j]=num[i+1][j];
s[i]がt[j]に等しい場合は、t[j]をs[i]でマッチングしてもよいし、s[i+1]から始まる文字列をt[j]から始まる文字列とマッチングしてもよいし、num[i][j]=num[i+1][j]+num[i+1][j+1]である.
後ろから前へ押して、dp.
 
コード:

class Solution {
public:
    int numDistinct(string S, string T) {
        vector<vector<int>> num(S.size()+1,vector<int>(T.size()+1,0));	//num[i][j]   s[i],t[j]         
		for(int i=0;i<=S.size();i++)	//   
			num[i][T.size()]=1;
		for(int j=T.size()-1;j>=0;j--)	//dp
			for(int i=S.size()-1;i>=0;i--)
			{
				num[i][j]=num[i+1][j];
				if(S[i]==T[j])
					num[i][j]+=num[i+1][j+1];
			}
		return num[0][0];
    }
};