建设网站用户名是什么,做初中物理题目的网站,济南冷空气来袭,东莞网站建设 牛魔网思路#xff1a;LCS#xff0c;dp
其实就是把dp的状态信息变了一下#xff0c;但是本质上的状态转移其实是没有很大的变动#xff0c;既然是让我们删除其他不一样的字符#xff0c;那么保留下来的肯定就是两个字符串的最长公共子序列了。这样的我们就可以设状态方程为最长…思路LCSdp
其实就是把dp的状态信息变了一下但是本质上的状态转移其实是没有很大的变动既然是让我们删除其他不一样的字符那么保留下来的肯定就是两个字符串的最长公共子序列了。这样的我们就可以设状态方程为最长公共子序列那种状态转移方程了。
这里的含义就变成了最小ASCII删除和。
当我们的s1[i]s2[j]的时候是不用发生任何变化的直接把上一个状态转移过来就行
当s1[i]!s2[j]的时候我们需要考虑两种情况了第一种就是删除第一个s1字符串的当前字符和第二种就是删除s2字符串的我当前字符我们需要比较一下这两个字符串的删除操作结束之后最小的删除和是哪一个我们就选哪一个不要忘记我们需要把这个当前字符串的ASCII值加到上一个状态上然后再进行比较。
注意我们在刚开始的时候需要进行初始化我们需要根据dp的状态转移信息确定怎么初始化。
例如当s1的长度为0的时候我们遍历s2字符串的时候其实就是把s2字符串全部删除状态存储就用前缀和的思想进行转移就行了。s2为0的时候s1是同样的操作。
dp[0][0]是一定为0的因为这个时候没有任何字符串可以删除。
class Solution {
public:int minimumDeleteSum(string s1, string s2) {vectorvectorintdp(s1.size()1,vectorint(s2.size()1,0));int ms1.size();int ns2.size();for(int i1;in;i){dp[0][i]dp[0][i-1]s2[i-1];}for(int i1;im;i){dp[i][0]dp[i-1][0]s1[i-1];}for(int i1;im;i){for(int j1;jn;j){if(s1[i-1]s2[j-1]){dp[i][j]dp[i-1][j-1];}else{dp[i][j]min(dp[i-1][j]s1[i-1],dp[i][j-1]s2[j-1]);}}}return dp[m][n];}
};
