思路：LCS類dp

這道題的思考思路其實(shí)就是把以兩個(gè)字符串結(jié)尾作為狀態(tài)方程。

dp[i][j]的意義就是在s字符串在以s[i]結(jié)尾的字符串的情況下，所能匹配出t字符串以t[j]結(jié)尾的字符串個(gè)數(shù)。

本質(zhì)上其實(shí)是一個(gè)LCS類的狀態(tài)方程，只不過(guò)是意義不一樣了，轉(zhuǎn)移方程不一樣了。

那么，我們知道了狀態(tài)意義之后，我們就需要知道轉(zhuǎn)移方程怎么寫。

首先我們需要比較每一個(gè)字符串，以s作為匹配的主體，去匹配t。當(dāng)s[i]==t[j]的時(shí)候，說(shuō)明這個(gè)時(shí)候結(jié)尾處我們是可以用這意味匹配的，那么我們這一位考慮和t[j]匹配了之后，就只需要考慮后面的字符串就行了，也就是dp[i-1][j-1]。但是我們還有一種情況，比如bagg，和bag這個(gè)距離，我們除了判斷除了dp[i-1][j-1]這個(gè)狀態(tài)之外，需要知道dp[i-1][j]的狀態(tài)，因?yàn)檫@里我們?nèi)绻豢紤]s[i]的匹配了（選與不選的問(wèn)題），那么上一位我們就需要考慮是不是和當(dāng)前t的這一位匹不匹配。

之后，就是s[i]!=t[j]的情況，這里就簡(jiǎn)單了，因?yàn)闊o(wú)論如何s[i]都不能滿足t[j]的匹配，我們只需要考慮上一位的匹配情況就可以了。

注意：初始化的時(shí)候我們需要額外注意，在t為空的時(shí)候，我們無(wú)論怎么匹配就只有一種情況，也就是dp[i][0]=1，因?yàn)橹挥幸粋€(gè)空集能夠匹配；當(dāng)s為空的時(shí)候，其實(shí)就沒(méi)有什么匹配情況了，本身需要匹配的字符串都沒(méi)有，也就沒(méi)有什么個(gè)數(shù)方案了，也就是dp[0][i]=0。

當(dāng)然，當(dāng)s,t都是空的時(shí)候，也就是一種方案，都是匹配空集。

還有，在遞推的過(guò)程中，其實(shí)dp可能會(huì)暴int，所以需要及時(shí)在中途進(jìn)行類型變化并取余。

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