现在网站如何做优化,iis怎么搭建设计网站,有经验的大良网站建设,东莞seo 公司思路#xff1a;LCS类dp
这道题的思考思路其实就是把以两个字符串结尾作为状态方程。
dp[i][j]的意义就是在s字符串在以s[i]结尾的字符串的情况下#xff0c;所能匹配出t字符串以t[j]结尾的字符串个数。
本质上其实是一个LCS类的状态方程#xff0c;只不过是意义不一样了…思路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) {vectorvectorintdp(s.size()1,vectorint(t.size()1,0));for(int i1;is.size();i){dp[i][0]1;}for(int i1;it.size();i){dp[0][i]0;}dp[0][0]1;for(int i1;is.size();i){for(int j1;jt.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()];}
};
