建设网站参数,深圳有实力的优化公司,卡盟代网刷24小时自助下单,设计制作ppt时这道题是困难题#xff0c;本章是针对于动态规划解决#xff0c;对于思路进行一个全面透彻的讲解#xff0c;但是并不是对于基础讲解思路#xff0c;而是渗透到递推式和dp填数的详解#xff0c;如果有读者不清楚基本的解题思路#xff0c;请看我的这篇文章算法训练营DAY5…这道题是困难题本章是针对于动态规划解决对于思路进行一个全面透彻的讲解但是并不是对于基础讲解思路而是渗透到递推式和dp填数的详解如果有读者不清楚基本的解题思路请看我的这篇文章算法训练营DAY53|392.判断子序列、115.不同的子序列-CSDN博客
但在看的过程中你可能会有为什么把dp数组设为以i-1和j-1的下标这样的奇怪含义的困惑这是为了方便初始化不用对每一个位置进行一开始的判定初始化也就是说可能要对于一开始下标匹配做一些多余的处理详细的解释可以翻看我往期作品其中会有更为详细的介绍本期文章我主要是针对对于思路有一些了解但是对于题解本身仍存有一些疑惑的读者准备的。
当然也是对于 我之前写的那期题解未能写的清楚的一些部分的补充。 这里还要纠正一下第一次写那个题解的一部分话是存在一些问题的两个字符匹配的第一项并不是未匹配成功的结果如果读者不能明白我在说什么直接看下面的代码即可不必要去看那期文章以避免误导读者。
class Solution {
public:int numDistinct(string s, string t) {int ms.size(),nt.size();vectorvectoruint64_tdp(m1,vectoruint64_t(n1,0));for(int i0;im;i)dp[i][0]1;for(int i1;im;i){for(int j1;jn;j){if(s[i-1]t[j-1])dp[i][j]dp[i-1][j-1]dp[i-1][j];else dp[i][j]dp[i-1][j];}}return dp[m][n];}
};
如上是题目正确的代码可以ac。
首先我们来分析的是递推式然后是初始化和打表最后是整体的总结。
先粘上一张代码随想录的图片当大家需要看图对比时候可以回过头开看 请注意子序列问题中dp解决时通常在需要在两个数组或字符串中找答案时候大多数情况下都需要开辟二维dp数组来解决问题。 明确递推式dp【i】【j】代表以i-1和j-1结尾的字符串s和t当前情况下s字符串中t出现的个数有多少个。 递推公式当i-1和j-1位置上的s和t字符串对应下标字符相等则当前位置可由dp【i-1】【j-1】推出来这个递推式的意思是由于这两个字符相等所以不用管该两个字符 然后去看相当于i-2和j-2对应的位置下s中包含了多少个t。 你也可以理解为当前的dp【i】【j】要填数就要看上一个状态时也就是dp【i-1】【j-1】的状态因为此时对应下标的元素相等所以直接去看上一个状态而此时不需要删除元素 那上一个状态dp【i-1】【j-1】有没有可能需要删除元素呢当然有可能但这并不是我们本次填数需要解决的问题上一个状态肯定在上一个状态被解决了。 为什么不是dp【i-1】【j-1】1当前字符相等应该意味着我们又多匹配成功了一个字符所以理应1啊 看这两个【bag】和【bag】当该填数dp【2】【2】时候我们根据dp数组定义实际上看的是s的i-1下标和t的j-1下标位置 那么也就是此时正在比较【ba】和【ba】呢它的上一个状态是【b】【b】虽然匹配是相等但是这并不意味着我们只要匹配相等字符就得1 因为这道题求的不是重复字符最多有多少个 那怎么完成匹配成功t字符串时候加入答案呢因为有第二项递推式 是dp【i-1】【j】这个递推式就相当于不回退当前的t字符串的匹配下标而是回退s字符串下标看看此时状态是否有s中有t字符串的这种情况 举例【bagg】和【bag】这两个那么除了s字符中的s[0]s[1]s[3]可以得到t字符串s[0]s[1]s[2]这个组合也可以得到t字符串。 所以这正是我们可以回退s的原因换个角度去看这也是我们匹配t这个字符串的整个字符串的方法。把这两个递推式相加就可以得到dp【i】【j】了 我们不考虑t字符串回退的原因在这里是因为我们是在s字符串里找有多少个t而不是在t里找所以应该回退s里的字符。如果你选择回退t此时对应的下标那么将不可能得到正确答案因为无论最后s能不能 从中找到t字符串的完整序列只要t中的部分子数组在s中出现过那么它一直沿用前面的状态那是不是肯定会得到1次匹配 你想想t一直沿用前面的状态而最开始的状态是s有字符而t无字符所以一定会有一解。这得出的答案一定是错误的。 所以t不可回退字符t只能向前匹配这样保证了求到最后的是s里是否包含完整的t字符串而不是只要包含一部分子数组就可以完成匹配。 还有一件事是s字符下标每次增大1然后重新对t字符串进行匹配也就解决了以各个的s下标位置为截止能匹配到最大匹配个数是多少。将它们加起来就是答案。 而如果此时两字符对应不等怎么办 dp【i】【j】dp【i-1】【j】这里的递推式你可以理解为删除s字符串当前遍历的字符模拟删除而转为用该下标的前一个位置看看有没有 s中含有t的时候延续那时候的状态就可以了。 初始化也很重要它是得到答案的关键初始化dp数组s和t数组都为空时候对应dp应该为1解释两字符串都为空则s字符串里包含1个t 当s字符串有内容t为空那么s各个状态都为1解释s字符串删除全部字符得到空字符串也就是t 当s没内容t有内容则这些状态都为0解释s无论如何也无法推出t 当两字符串内容不相等时候也就是s中不包含t那么无论如何也推不出一个因为s里要想能找到t那么必须t中的第一个元素与s中的某位置元素发生了起始匹配。 这时初始化产生作用虽然这种中间某处得到的匹配匹配不上原始的dp【0】【0】但是它能匹配上dp【i】【0】使得累计1次匹配。 然后接下来的匹配就是对t字符串各个字符都必须连续匹配才可以使这个1继承下来因为递推式的缘故往后匹配dp【0】【0】肯定匹配不上 而如果中间某字符没匹配上断档了那么再匹配上的时候dp【i-1】【j】也不可能借用到dp【i】【0】就使得最终答案是0。 打表特殊测试用例 s【bag】t【bag】 dp[0][0]1dp[0][1]0dp[0][2]0dp[0][3]0 dp[1][0]1dp[1][1]1dp[1][2]0dp[1][3]0 dp[2][0]1dp[2][1]1dp[2][2]1dp[2][3]0 dp[3][0]1dp[3][1]1dp[3][2]1dp[3][3]1 可见即使中间遍历时候也有完全匹配时候【ba】【ba】但是这并不会使dp【2】【2】变成2 由头上的图片可以知道其实dp【i-1】【j-1】和dp【i-1】【j】都有可能是答案的组成部分 打表bac和bad dp[0][0]1dp[0][1]0dp[0][2]0dp[0][3]0 dp[1][0]1dp[1][1]1dp[1][2]0dp[1][3]0 dp[2][0]1dp[2][1]1dp[2][2]1dp[2][3]0 dp[3][0]1dp[3][1]1dp[3][2]1dp[3][3]0
再写该题时候写到循环部分的时候想的是t字符串既然不能使之回退那么是不是应该写成t循环在外面s循环在里面这样只循环了一次t就保证了不回退的效果而不是写成s循环在外面t循环在内部 但后来发现不是这么一回事这样写循环是有原因的它遍历s的各个字符给t去进行匹配以获得所有的组合答案。如果t循环写外面了t确实没有回退但是这样写的思路不就成了拿t的各个元素去找 t里面是否存在s字符串了吗这不就写反了吗 还有就是外层for是s内层for是t并不是没有实现t的禁止回退所谓t字符串不能回退不是指t的字符串不能重复遍历不能回退体现在递推公式上不要弄混淆。 再细说一下具体的匹配机理是如何实现s拿一个个字符串然后去匹配t的。 首先s字符串每次增大一个匹配范围表面上看然后t字符串在s每次增大匹配范围时重新遍历t字符串去和s的现在范围去匹配看看现在的s范围能否找到更多的匹配次数并填到dp数组内。 从代码的实际运行角度s的每次增大一个字符的范围t重新匹配并不是匹配0——i而是拿t的整个字符串去和i这个元素单单去匹配而非s子串和t字符串匹配。 这实际上无形之中提升了效率那么怎么实现匹配的正确呢 递推式已经给出了如果当前元素匹配不上那么当前位置填数继承上一次匹配也就是当前两个字符不匹配那么相当于放弃当前两个字符的匹配机会而是选用上一次的对应截止字符处去继承那一次的 匹配成果。这次的继承是就是回退s而不回退t 如果匹配成功有两个方向推出一个是不考虑当前两个字符因为两个字符当前匹配成功所以暂时不考虑但是还没完还要考虑s往前回退一个字符的情况与t进行匹配的成果将二者相加得到答案 为什么不回退第二个字符串t我们上面已经说得很清楚了而回退s为上一个字符是为什么呢就是因为bag和bagg的测试用例这类情况也即是说可能存在上一个s的字符也存在匹配的关系那有人要问 如果是bag和baggg呢你怎么匹配这是一样的第二次的g会继承第一次g匹配成果而第三次又会继承第二次.看递推式就能知道两字符匹配成功答案是左上角数加上头上的数 而这个头上的数自然把上一层的g加过来了。 还有一个问题是为什么总是能得到正确答案我们上面已经说了一些了但是个人觉得还不够透彻。再说一次 首先它为什么不是每匹配成功一次都1我们上面说的很清了当两个字符相等时候的填数再说一下 我们由于初始化的缘故使得若此时匹配的两个字符匹配不相等也就是说假如bagg和bags字符串bagg匹配到最后一个字符时候但是t字符串从头开始匹配这个时候我们由于第二递推式匹配不等时候会拿 dp【i】【j-1】的数做继承直到匹配成功填数的时候真正的递推作用才开始显现 匹配相等时会把头上的位置也就是dp【i-1】【j】和dp【i-1】【j-1】累加起来换句话说只有两个字符最后发生匹配时候才能够获得答案如果不发生匹配不会获得答案。 这是为什么呢不是说不匹配会继承前位置吗但是你要注意只有同列才能继承也就是说如果你的上一行列没有做事那么你不能享受成果这就相当于祖上得有财富积累你才能躺平拿到成果否则你只能 依赖于本身的才能也就是进入第一递推式虽然祖上可能没有成果但你可以收获你左上角人的成果。 所以并不会发生一处匹配成功全部人都受益的结果。 你左上的成果相当于叔辈的成果你没有能力时候它不会贡献成果给你享用只有你的亲祖先才能共享成果所以如果前面出现多次匹配也就是说祖先和叔辈都得到了匹配或他们继承它们的祖先和叔辈匹配 而且同时你也有能力匹配才会同时得到两方面的匹配成果。 这个左上角匹配也并非与你完全无关它有数字代表了发生连续匹配。 badgbacg打表 dp[0][0]1dp[0][1]0dp[0][2]0dp[0][3]0dp[0][4]0 dp[1][0]1dp[1][1]1dp[1][2]0dp[1][3]0dp[1][4]0 dp[2][0]1dp[2][1]1dp[2][2]1dp[2][3]0dp[2][4]0 dp[3][0]1dp[3][1]1dp[3][2]1dp[3][3]0dp[3][4]0 dp[4][0]1dp[4][1]1dp[4][2]1dp[4][3]0dp[4][4]0 这下应该明白了吧虽然祖上有成果的某些中间量会继承祖上的成果但这并不一定影响最后的答案该样例中即使最后一次发生了g和g的匹配但是它的左上角没有成果也就是出现了断档而且它的祖上也没有 成果所以它依然无法收获结果。 这也就是说只要中间断档发生了一次那么就不再可能延续的上想尝试的读者可写一个badgh和bacgh试一下打表 简而言之 对于当前两字符匹配成功则需要收获结果结果的第一部分代表了之前字符的连续匹配第二部分代表了s中存在多个t的继承匹配个数 对于匹配不成功继承连续匹配结果这一举动主要是为了下一次的s扩大后的匹配受益因为s当前字符不可能与t所有字符匹配那么只要有一次完成了匹配则这一列的所有位置理应继承那次匹配成功的成果。 以应对下一次循环匹配的时候对于连续字符匹配的连贯性。 相信如果读者事先具备了代码思路知道题解如何解答再看这篇文章一定会受益匪浅。
这是对于细节上问题的一些补充。本章就到这里。
都看到这里了如果对您有用的话别忘了一键三连哦如果是互粉回访我也会做的
大家有什么想看的题解或者想看的算法专栏、数据结构专栏可以去看看往期的文章有想看的新题目或者专栏也可以评论区写出来讨论一番本账号将持续更新。 期待您的关注
