文章目录【115.不同的子序列】【583.两个字符串的删除操作】方法一方法二求出最大公共子序列长度再将两个序列所需要的删除步骤相加即可【72.编辑距离】【115.不同的子序列】思路确定dp数组dp table以及下标的含义dp[i] [j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i] [j]。为什么i-1j-1 这么定义在 718. 最长重复子数组 中做了详细的讲解。确定递推公式这一类问题基本是要分析两种情况s[i - 1] 与 t[j - 1]相等s[i - 1] 与 t[j - 1] 不相等当s[i - 1] 与 t[j - 1]相等时dp[i] [j]可以有两部分组成。一部分是用s[i - 1]来匹配那么个数为dp[i - 1] [j - 1]。即不需要考虑当前s子串和t子串的最后一位字母那前面都只剩下 i-1 个字符所以只需要 dp[i-1] [j-1]。一部分是不用s[i - 1]来匹配个数为dp[i - 1] [j]。这里有疑惑为什么还要考虑 不用s[i - 1]来匹配都相同了指定要匹配啊。例如 sbagg 和 tbag s[3] 和 t[2]是相同的但是字符串s也可以不用s[3]来匹配即用s[0]s[1]s[2]组成的bag。当然也可以用s[3]来匹配即s[0]s[1]s[3]组成的bag。所以当s[i - 1] 与 t[j - 1]相等时dp[i] [j] dp[i - 1] [j - 1] dp[i - 1] [j];当s[i - 1] 与 t[j - 1]不相等时dp[i] [j]只有一部分组成不用s[i - 1]来匹配就是模拟在s中删除这个元素即dp[i - 1] [j]所以递推公式为dp[i] [j] dp[i - 1] [j];子序列题目字符相等只是多出来一条可选路径旧的路径之前已经凑好 t 的方案依然存在不能丢掉。这里还有疑惑为什么只考虑 “不用s[i - 1]来匹配” 这种情况 不考虑 “不用t[j - 1]来匹配” 的情况呢。因为这里要明确我们求的是 s 中有多少个 t而不是 求t中有多少个st不能删除所以只考虑 s中删除元素的情况即 不用s[i - 1]来匹配 的情况。dp数组如何初始化从递推公式dp[i] [j] dp[i - 1] [j - 1] dp[i - 1] [j]; 和 dp[i] [j] dp[i - 1] [j]; 中可以看出dp[i] [j] 是从上方和左上方推导而来如图那么 dp[i] [0] 和dp[0] [j]是一定要初始化的。每次当初始化的时候都要回顾一下dp[i] [j]的定义不要凭感觉初始化。dp[i] [0]表示什么呢dp[i] [0] 表示以i-1为结尾的s可以随便删除元素出现空字符串的个数。那么dp[i] [0]一定都是1因为也就是把以i-1为结尾的s删除所有元素出现空字符串的个数就是1。再来看dp[0] [j]dp[0] [j]空字符串s可以随便删除元素出现以j-1为结尾的字符串t的个数。那么dp[0] [j]一定都是0s如论如何也变成不了t。最后就要看一个特殊位置了即dp[0] [0] 应该是多少。dp[0] [0]应该是1空字符串s可以删除0个元素变成空字符串t。初始化分析完毕代码如下vectorvectorlonglongdp(s.size()1,vectorlonglong(t.size()1));for(inti0;is.size();i)dp[i][0]1;for(intj1;jt.size();j)dp[0][j]0;// 其实这行代码可以和dp数组初始化的时候放在一起但为了凸显初始化的逻辑所以还是加上了。确定遍历顺序从递推公式dp[i] [j] dp[i - 1] [j - 1] dp[i - 1] [j]; 和 dp[i] [j] dp[i - 1] [j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。举例推导dp数组classSolution{public:intnumDistinct(string s,string t){vectorvectoruint64_tdp(s.size()1,vectoruint64_t(t.size()1));// dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。for(inti0;is.size();i){dp[i][0]1;}for(intj1;jt.size();j){dp[0][j]0;}for(inti1;is.size();i){for(intj1;jt.size();j){if(s[i-1]t[j-1])dp[i][j]dp[i-1][j-1]dp[i-1][j];elsedp[i][j]dp[i-1][j];}}returndp[s.size()][t.size()];}};【583.两个字符串的删除操作】思路方法一本题和动态规划115.不同的子序列相比其实就是两个字符串都可以删除了情况虽说复杂一些但整体思路是不变的。这次是两个字符串可以相互删了这种题目也知道用动态规划的思路来解动规五部曲分析如下确定dp数组dp table以及下标的含义dp[i] [j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。这里dp数组的定义有点点绕大家要理清思路。确定递推公式当word1[i - 1] 与 word2[j - 1]相同的时候当word1[i - 1] 与 word2[j - 1]不相同的时候当word1[i - 1] 与 word2[j - 1]相同的时候dp[i] [j] dp[i - 1] [j - 1];当word1[i - 1] 与 word2[j - 1]不相同的时候有三种情况情况一删word1[i - 1]最少操作次数为dp[i - 1] [j] 1情况二删word2[j - 1]最少操作次数为dp[i] [j - 1] 1情况三同时删word1[i - 1]和word2[j - 1]操作的最少次数为dp[i - 1] [j - 1] 2那最后当然是取最小值所以当word1[i - 1] 与 word2[j - 1]不相同的时候递推公式dp[i] [j] min({dp[i - 1] [j - 1] 2, dp[i - 1] [j] 1, dp[i] [j - 1] 1});因为 dp[i] [j - 1] 1 dp[i - 1] [j - 1] 2所以递推公式可简化为dp[i] [j] min(dp[i - 1] [j] 1, dp[i] [j - 1] 1);这里可能容易迷糊从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1]dp[i] [j-1] 本来就不考虑 word2[j - 1]了那么我在删 word1[i - 1]是不是就达到两个元素都删除的效果即 dp[i] [j-1] 1。dp数组如何初始化从递推公式中可以看出来dp[i] [0] 和 dp[0] [j]是一定要初始化的。dp[i] [0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。dp[0] [j]的话同理所以代码如下vectorvectorintdp(word1.size()1,vectorint(word2.size()1));for(inti0;iword1.size();i)dp[i][0]i;for(intj0;jword2.size();j)dp[0][j]j;确定遍历顺序从递推公式 dp[i] [j] min(dp[i - 1] [j - 1] 2, min(dp[i - 1] [j], dp[i] [j - 1]) 1); 和dp[i] [j] dp[i - 1] [j - 1]可以看出dp[i] [j]都是根据左上方、正上方、正左方推出来的。所以遍历的时候一定是从上到下从左到右这样保证dp[i][j]可以根据之前计算出来的数值进行计算。举例推导dp数组classSolution{public:intminDistance(string word1,string word2){vectorvectorintdp(word1.size()1,vectorint(word2.size()1));// dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。for(inti0;iword1.size();i){dp[i][0]i;}for(intj0;jword2.size();j){dp[0][j]j;}for(inti1;iword1.size();i){for(intj1;jword2.size();j){if(word1[i-1]word2[j-1])dp[i][j]dp[i-1][j-1];else{dp[i][j]min(dp[i-1][j]1,dp[i][j-1]1);}}}returndp[word1.size()][word2.size()];}};方法二求出最大公共子序列长度再将两个序列所需要的删除步骤相加即可classSolution{public:intminDistance(string word1,string word2){vectorvectorintdp(word1.size()1,vectorint(word2.size()1,0));// dp[i][j]表示0~i-1和0~j-1的最大公共子序列长度for(inti1;iword1.size();i){for(intj1;jword2.size();j){if(word1[i-1]word2[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}}intresult0;resultword1.size()-dp[word1.size()][word2.size()];resultword2.size()-dp[word1.size()][word2.size()];returnresult;}};【72.编辑距离】思路确定dp数组dp table以及下标的含义dp[i] [j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i] [j]。在确定递推公式的时候首先要考虑清楚编辑的几种操作整理如下if (word1[i - 1] word2[j - 1]) 不操作 if (word1[i - 1] ! word2[j - 1]) 增 删 换也就是如上4种情况。if (word1[i - 1] word2[j - 1])那么说明不用任何编辑dp[i][j]就应该是dp[i - 1][j - 1]即dp[i][j] dp[i - 1][j - 1];在下面的讲解中如果哪里看不懂就回想一下dp[i][j]的定义就明白了。在整个动规的过程中最为关键就是正确理解dp[i][j]的定义if (word1[i - 1] ! word2[j - 1])此时就需要编辑了如何编辑呢操作一word1删除一个元素那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。即dp[i][j] dp[i - 1][j] 1;操作二word2删除一个元素那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。即dp[i][j] dp[i][j - 1] 1;这里有同学发现了怎么都是删除元素添加元素去哪了。word2添加一个元素相当于word1删除一个元素例如word1 ad word2 aword1删除元素d和word2添加一个元素d变成word1a, word2ad 最终的操作数是一样 dp数组如下图所示意的a a d ---------- --------------- | 0 | 1 | | 0 | 1 | 2 | ---------- --------------- a | 1 | 0 | a | 1 | 0 | 1 | ---------- --------------- d | 2 | 1 | ----------操作三替换元素word1替换word1[i - 1]使其与word2[j - 1]相同此时不用增删加元素。可以回顾一下if (word1[i - 1] word2[j - 1])的时候我们的操作 是dp[i][j] dp[i - 1][j - 1]对吧。那么只需要一次替换的操作就可以让 word1[i - 1] 和 word2[j - 1] 相同。所以dp[i][j] dp[i - 1][j - 1] 1;综上当if (word1[i - 1] ! word2[j - 1])时取最小的即dp[i][j] min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) 1;递归公式代码如下if(word1[i-1]word2[j-1]){dp[i][j]dp[i-1][j-1];}else{dp[i][j]min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]})1;}dp数组如何初始化再回顾一下dp[i][j]的定义dp[i] [j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i] [j]。那么dp[i] [0] 和 dp[0] [j] 表示什么呢dp[i] [0] 以下标i-1为结尾的字符串word1和空字符串word2最近编辑距离为dp[i] [0]。那么dp[i] [0]就应该是i对word1里的元素全部做删除操作即dp[i] [0] i;同理dp[0] [j] j;所以C代码如下for(inti0;iword1.size();i)dp[i][0]i;for(intj0;jword2.size();j)dp[0][j]j;确定遍历顺序从如下四个递推公式dp[i][j] dp[i - 1][j - 1]dp[i][j] dp[i - 1][j - 1] 1dp[i][j] dp[i][j - 1] 1dp[i][j] dp[i - 1][j] 1可以看出dp[i] [j]是依赖左方上方和左上方元素的所以在dp矩阵中一定是从左到右从上到下去遍历。代码如下for(inti1;iword1.size();i){for(intj1;jword2.size();j){if(word1[i-1]word2[j-1]){dp[i][j]dp[i-1][j-1];}else{dp[i][j]min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]})1;}}}举例推导dp数组classSolution{public:intminDistance(string word1,string word2){vectorvectorintdp(word1.size()1,vectorint(word2.size()1));// dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。for(inti0;iword1.size();i){dp[i][0]i;}for(intj0;jword2.size();j){dp[0][j]j;}for(inti1;iword1.size();i){for(intj1;jword2.size();j){if(word1[i-1]word2[j-1])dp[i][j]dp[i-1][j-1];else{dp[i][j]min(dp[i-1][j]1,min(dp[i][j-1]1,dp[i-1][j-1]1));// 增和删本质一样而修改就是dp[i-1][j-1] 1}}}returndp[word1.size()][word2.size()];}};