开奖网站怎么做google优化排名

思路：LCS类dp

这道题的思考思路其实就是把以两个字符串结尾作为状态方程。

dp[i][j]的意义就是在s字符串在以s[i]结尾的字符串的情况下，所能匹配出t字符串以t[j]结尾的字符串个数。

本质上其实是一个LCS类的状态方程，只不过是意义不一样了，转移方程不一样了。

那么，我们知道了状态意义之后，我们就需要知道转移方程怎么写。

首先我们需要比较每一个字符串，以s作为匹配的主体，去匹配t。当s[i]==t[j]的时候，说明这个时候结尾处我们是可以用这意味匹配的，那么我们这一位考虑和t[j]匹配了之后，就只需要考虑后面的字符串就行了，也就是dp[i-1][j-1]。但是我们还有一种情况，比如bagg，和bag这个距离，我们除了判断除了dp[i-1][j-1]这个状态之外，需要知道dp[i-1][j]的状态，因为这里我们如果不考虑s[i]的匹配了（选与不选的问题），那么上一位我们就需要考虑是不是和当前t的这一位匹不匹配。

之后，就是s[i]!=t[j]的情况，这里就简单了，因为无论如何s[i]都不能满足t[j]的匹配，我们只需要考虑上一位的匹配情况就可以了。

注意：初始化的时候我们需要额外注意，在t为空的时候，我们无论怎么匹配就只有一种情况，也就是dp[i][0]=1，因为只有一个空集能够匹配；当s为空的时候，其实就没有什么匹配情况了，本身需要匹配的字符串都没有，也就没有什么个数方案了，也就是dp[0][i]=0。

当然，当s,t都是空的时候，也就是一种方案，都是匹配空集。

还有，在递推的过程中，其实dp可能会暴int，所以需要及时在中途进行类型变化并取余。

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()];}
};