首页 / 资讯中心 / 文章详情

最长重复子数组动态规划与滑动窗口解法:从连续匹配到空间优化

最长重复子数组动态规划与滑动窗口解法:从连续匹配到空间优化 ★ FEATURED ARTICLE
1. 题目拆解子数组和子序列一字之差天壤之别1.1 题目的原始定义到底在问什么力扣 718最长重复子数组Java 实现。题目描述很简短给定两个整数数组 nums1 和 nums2返回两个数组中公共的、长度最长的子数组的长度。很多人一看到这个标题就本能地把它和“最长公共子序列”联系起来觉得无非是把两个字符串的匹配换成了整数数组模板抄过来改个类型就行。这个想法如果不及时纠偏后面写代码十有八九要翻车。关键就在“子数组”三个字。在数组语境里子数组就是子串要求元素在原数组中是连续的一段。比如数组 [1,2,3]它的子数组包括 [1]、[2]、[3]、[1,2]、[2,3]、[1,2,3]但 [1,3] 不是子数组它只是子序列。最长公共子序列允许你跳过一些元素去拼凑最长重复子数组不允许两个数字必须挨在一起才算数。这个“连续”约束直接决定了状态怎么定义、转移方程怎么写、空间优化怎么做。可以这样理解子序列就像搭积木你可以从两堆积木里挑出形状相同的几块哪怕它们原来不相邻拼在一起就算数子数组则像电影胶片的相邻帧必须是从某一帧开始到某一帧结束、中间不能断的一整段。我们平时在代码里做字符串匹配、基因序列比对、日志模式识别时需要判断的往往是“这一段是否连续出现”这种场景对应的就是子数组模型。所以这道题不是冷门偏题它是动态规划与滑动窗口这两类经典算法非常典型的交叉练习题。1.2 为什么暴力枚举会被面试官一眼看穿先不谈动态规划一个完全没接触过算法思路的人最自然的想法是什么枚举。固定 nums1 的每个起始位置 i再固定 nums2 的每个起始位置 j然后把这两段逐位往后比看公共部分最长能撑到多远。听起来没毛病但代价很吓人。假设 nums1 长度是 nnums2 长度是 m枚举起点需要 O(nm)对每个起点组合最坏还要往后比较 min(n, m) 位整体复杂度是 O(nm*min(n,m))。当 n 和 m 都到 1000就是十亿次操作Java 单线程跑起来已经是肉眼可见的卡顿一旦数据规模放大到 10^4 甚至 10^5这个算法基本等于死循环。在实际的系统设计或者日常开发里数组规模上万太常见了暴力法连及格线都够不着。而且暴力枚举还有一个隐蔽的问题它反复比较了同一段区间。比如 (i, j) 这个起点组合匹配了前三位(i1, j1) 又从头开始比较明明前两位刚刚比较过但没有任何状态被保存下来所有工作重来一遍。这就是典型的“重复子问题”信号而动态规划恰恰就是冲着消除重复计算来的。所以下一步的思路很清晰能不能把“以某个位置结尾的公共子数组长度”记下来让后面的计算直接复用前面的结果能这就是 DP 表格。2. 动态规划把重复匹配变成填表格2.1 状态设计dp[i][j] 到底在记录什么动态规划的第一步永远不是写代码而是定义状态。这道题的状态定义是核心也是最容易含糊的地方。我定义 dp[i][j] 为nums1 以第 i 个元素结尾、nums2 以第 j 个元素结尾时公共子数组的最大长度。注意这里的措辞是“以第 i 个元素结尾”不是“前 i 个元素里随便找一个”。为什么要卡死结尾因为子数组要求连续一段公共部分能不能继续往后延伸取决于它的末尾和下一个元素是否继续相等。如果只记录“前 i 个元素和前 j 个元素整体能匹配出多长”这个信息没有连续性没法往后接。为了处理下标边界dp 数组的尺寸要比原数组各多一行一列。dp[0][j] 和 dp[i][0] 全部初始化为 0它们相当于哨兵代表“空数组的结尾”。实际比较时nums1 的第 i 个元素对应 nums1[i-1]nums2 的第 j 个元素对应 nums2[j-1]中间差一个下标这是为了让 dp[i-1][j-1] 这个前驱状态可以自然映射到前一个元素不需要写一堆 if 判边界。这里有一个很容易问自己“为什么”的地方为什么不能像一维 DP 那样只用一个 dp[i]因为这场比赛牵涉两个数组的当前位置公共子数组的长度不仅由 nums1 的当前位置决定还由 nums2 的当前位置决定。两个维度缺一不可所以二维表是这类题目的天然归宿。当然二维表并不意味着空间复杂度必须维持 O(n*m)后面会讲滚动数组如何把这笔开销省下来。2.2 转移方程推导相等怎么走不相等怎么断状态定义清楚以后转移方程其实水到渠成。当 nums1[i-1] 等于 nums2[j-1] 时说明这两个元素能作为公共子数组的最后一个元素那么以它们结尾的最长公共子数组长度就是“以它们前一个元素结尾的最长公共子数组长度”再加 1也就是 dp[i][j] dp[i-1][j-1] 1。数学上不用犹豫语言描述也很直观今天这两个数对上了那整段匹配就能续上前一天的进度。比较关键的是不相等的情况。当 nums1[i-1] 不等于 nums2[j-1] 时dp[i][j] 必须等于 0而不是继承左边或上边的最大值。为什么因为“以它们两个元素结尾的公共子数组”根本不存在。如果强行继承之前的状态那等于在暗示“即使这两个位置对不上我也可以从更早的地方连过来”这就破坏了连续性把子数组问题悄悄变成了子序列问题。子数组一旦断了就是断了长度必须清零重新计。这也是 718 与经典的最长公共子序列LCS在转移方程上最本质的差异。LCS 的不等分支是 dp[i][j] max(dp[i-1][j], dp[i][j-1])因为子序列允许跳过元素左边和上边的最优解仍然有效而 718 的不等分支是赋 0因为两条链在这里断裂没有资格继承任何历史长度。如果把两道题放在一起对比记忆718 的表格会显得“稀疏”很多很多格子都是 0只有匹配成功的对角线上才有连续的非零值。2.3 标准二维数组的 Java 落地状态和方程都确定了写代码就是一件非常机械的事。我直接给出完整实现并标注几个关键位置的含义。public int findLength(int[] nums1, int[] nums2) { if (nums1 null || nums2 null || nums1.length 0 || nums2.length 0) { return 0; } int n nums1.length; int m nums2.length; int[][] dp new int[n 1][m 1]; int ans 0; for (int i 1; i n; i) { for (int j 1; j m; j) { if (nums1[i - 1] nums2[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; ans Math.max(ans, dp[i][j]); } else { dp[i][j] 0; } } } return ans; }代码量不大但有三个细节值得单独拎出来说。第一为什么要维护一个 ans 全局最大值而不是最后返回 dp[n][m]因为最长公共子数组不一定以两个数组的最后一个元素结尾它可能发生在整个匹配过程的中间某一段。dp[n][m] 只表示两个数组末尾元素能不能接上和整个数组的最优解没有必然关系。每次更新 dp[i][j] 后同步更新 ans才是安全的做法。第二dp 为什么开成 n1 和 m1而不是 n 和 m因为 i0 或 j0 这一整行一整列要当哨兵用。如果没有它们当 i1、j1 时访问 dp[0][0] 会越界你得写一堆 if 去判断特殊情况。多开一行一列代价极小代码却干净很多。第三默认不匹配时 dp[i][j] 其实已经是 0因为 Java 数组初始化时所有元素都是 0。这个 else 分支理论上可以省略但我建议不要省。它不仅是给读者看的语义声明在后面滚动数组版本里这个清零会变成必需品先在这里养成习惯不会吃亏。2.4 用一组真实样例把表格推演一遍纸上谈兵没有说服力我拿力扣题目里那个经典样例来手动推表。nums1 [1,2,3,2,1]nums2 [3,2,1,4,7]。肉眼扫一眼公共子数组有 [3]、[2]、[1] 这些单元素还有 [3,2,1] 连起来最长长度是 3。接下来看二维 DP 表是怎么一步步得到 3 的。j1 j2 j3 j4 j5 i1 0 0 1 0 0 i2 0 1 0 0 0 i3 1 0 0 0 0 i4 0 2 0 0 0 i5 0 0 3 0 0i1 时nums1 的 1 和 nums2 的第 3 个元素 1 相等所以 dp[1][3] dp[0][2] 1 1。i2 时nums1 的 2 和 nums2 的第 2 个元素 2 相等dp[2][2] dp[1][1] 1 1注意这里 dp[1][1] 是 0因为此前 1 和 3 并不匹配。i3 时3 和 nums2 的第 1 个元素 3 对上dp[3][1] dp[2][0] 1 1。到这里表格看起来像是分散的三点火苗互不相连。真正的递进发生在 i4 和 i5。i4 时nums1 的 2 再次对上 nums2 的第 2 个元素 2而 dp[3][1] 是 1说明前面已经有一段 [3] 接上了于是 dp[4][2] 2代表子数组 [3,2] 成立。i5 时nums1 的 1 对上 nums2 的第 3 个元素 1dp[4][2] 是 2于是 dp[5][3] 3代表 [3,2,1] 完整出现。这张表里非零值全部沿着“从左上到右下”的方向生长这不是巧合而是连续匹配的必然形态。3. 滚动数组优化从 O(nm) 空间降到 O(min(n,m))3.1 为什么只需要保留一行二维 DP 的空间复杂度是 O(n*m)当 n 和 m 都是两万时光 dp 表就需要 4 亿个 int换算成内存大约是 1.6GB这对绝大多数在线评测环境和实际应用来说都是不可接受的。好在这个转移方程有个特别友好的性质dp[i][j] 只依赖 dp[i-1][j-1]也就是它正左上方的那个格子既不依赖同一行的其他格子也不依赖 i-2 行以后的信息。这意味着当你从左往右、从上往下填表时整张表格其实只有“当前行”和“上一行”是有用的更早的行填完就再也没有人回头看它们了。既然没人用那就不需要真的存下来。用一个一维数组反复覆盖即可每一轮外层循环开始时这个一维数组里保存的是上一行的值外层循环走完一轮数组里的值就被覆盖成当前行的新值为下一轮做准备。这种技巧叫滚动数组是二维 DP 空间优化的标准操作。空间从 O(n*m) 降到 O(m)已经是质的飞跃。如果进一步把较短数组放到内层循环还能把 O(m) 压成 O(min(n,m))。因为两个数组在题目中是对称的交换它们的顺序不影响答案但 dp 数组的长度只跟内层数组长度有关让较短的那个当内层内存开销自然最小。3.2 反序遍历背后的“新与旧”博弈滚动数组最阴险的地方不是“能不能滚动”而是“往哪个方向滚动”。看转移方程 dp[i][j] dp[i-1][j-1] 1在压缩成一维 dp[j] 后等号右边的 dp[j-1] 必须还是上一轮外层循环留下的旧值也就是真正的 dp[i-1][j-1]。如果内层循环正着走也就是 j 从 1 到 m问题就来了。当你处理到 j 的时候dp[j-1] 已经在当前这一轮被更新过了它现在是 dp[i][j-1]而不是 dp[i-1][j-1]。用新值去计算等于把同一条匹配链在“同一轮”里横向借位逻辑上已经脱离了原方程。所以内层循环必须倒着走让 j 从 m 减到 1这样处理 j 时j-1 还没有被本轮触碰过dp[j-1] 里躺着的仍然是上一轮的旧值依赖关系才成立。这个“新旧博弈”是这个优化里最重要、也最容易被忽略的细节。很多人把二维数组改成滚动数组后代码看起来一模一样但结果错误排查半天发现只是循环方向不对。为什么有时候错误不明显因为当上一轮和本轮在某个位置恰好都是 1 时正序和倒序算出来的结果碰巧一样就掩盖了问题等换一组数据立刻翻车。所以老老实实记结论多维 DP 压缩成一维如果状态依赖数组下标更小的旧值内层循环一定要倒序。3.3 完整 Java 代码与两个隐性坑滚动数组版本的完整 Java 实现如下public int findLength(int[] nums1, int[] nums2) { if (nums1 null || nums2 null || nums1.length 0 || nums2.length 0) { return 0; } // 让较短的数组放在内层dp 数组才能开得更小 if (nums1.length nums2.length) { int[] tmp nums1; nums1 nums2; nums2 tmp; } int n nums1.length; int m nums2.length; int[] dp new int[m 1]; int ans 0; for (int i 1; i n; i) { for (int j m; j 1; j--) { if (nums1[i - 1] nums2[j - 1]) { dp[j] dp[j - 1] 1; ans Math.max(ans, dp[j]); } else { dp[j] 0; } } } return ans; }第一个隐性坑数组交换。代码里先判断 nums1 长度是否小于 nums2小于就交换。交换之后外层循环遍历的是较长的数组内层遍历较短数组dp 数组长度就等于较短数组长度加 1空间复杂度严格变成 O(min(n,m))。这个交换不会影响答案因为公共子数组是两个数组共同拥有的属性跟谁在前谁在后无关。第二个隐性坑else 分支的 dp[j] 0 绝对不能省。二维 DP 里数组初始值就是 0省略 else 不影响第一次赋值但滚动数组是反复复用同一个数组上一轮留下的非零值不会自动消失。如果某一对元素不匹配而你没有把 dp[j] 清零这个残留值会在下一轮被当成“历史匹配长度”使用。等下一次恰好匹配时dp[j-1] 1 就会加在一个已经断裂的旧值上答案凭空被拔高。很多滚动数组版本结果偏大十有八九就是漏了这一行。4. 滑动窗口方案不依赖额外空间的高效解法4.1 对齐思维把两个数组叠在一起比动态规划的思路是把匹配过程拆成小状态填一张大表。还有另一条完全不同的思路滑动窗口也叫对齐法它的切入角度更接近人眼观察。想象把两个数组水平放在两条轨上让它们左端先对齐然后比较重合部分。接着把上方的数组向右平移一个位置再比较一次再把下方数组向右平移一个位置再比较一次。每次平移后两个数组只有一段重叠区域这段区域里连续的相等元素就构成一个公共子数组。记录所有对齐方式下出现的最大连续相等段长度就是答案。为什么这个思路正确因为任意一段公共子数组一定对应着两个数组在某种偏移下的一段重合区域。你不可能找到一段公共子数组它在两个数组里出现的相对位置完全无法通过某种平移对齐。所以把所有可能的偏移全部枚举一遍答案一定被覆盖到。这种方法的直观性极强代码写起来也非常不容易出错尤其适合在面试时作为动态规划之外的“Plan B”展示给面试官看。4.2 枚举所有偏移的 Java 实现滑动窗口的代码结构一般拆成两部分主函数负责枚举所有对齐方式辅助函数负责统计某一段重叠区间内最长的连续匹配长度。public int findLength(int[] nums1, int[] nums2) { int n nums1.length; int m nums2.length; int ans 0; // 固定 nums2 的起点 0移动 nums1 的起点 for (int i 0; i n; i) { int len Math.min(n - i, m); ans Math.max(ans, commonLen(nums1, nums2, i, 0, len)); } // 固定 nums1 的起点 0移动 nums2 的起点 for (int j 0; j m; j) { int len Math.min(n, m - j); ans Math.max(ans, commonLen(nums1, nums2, 0, j, len)); } return ans; } private int commonLen(int[] A, int[] B, int aStart, int bStart, int len) { int cur 0; int best 0; for (int k 0; k len; k) { if (A[aStart k] B[bStart k]) { cur; best Math.max(best, cur); } else { cur 0; } } return best; }主函数里两套循环分别处理“nums1 从某个位置开始对齐到 nums2 开头”和“nums2 从某个位置开始对齐到 nums1 开头”两种情况。有人会问这两套循环是不是重复了并不是。第一种覆盖的是 nums1 的每个元素作为重叠区间最左端的情况第二种覆盖的是 nums2 的每个元素作为重叠区间最左端的情况。任意一个可能的对齐关系要么属于前者要么属于后者两者合起来才是完整的枚举全集。commonLen 函数里的逻辑和 DP 的“连续段”思路如出一辙cur 记录当前连续匹配的临时长度遇到相等就加一遇到不等就清零best 保存这一段里的最大临时值。只要重叠长度 len 大于零这个统计就是安全的。4.3 时间与空间的真实权衡滑动窗口的时间复杂度怎么算主函数两套循环加起来要尝试 O(nm) 次对齐每次对齐最长的比较长度是 min(n,m)所以整体是 O((nm)min(n,m))。这个复杂度不如动态规划的 O(nm) 好看但在很多场景下其实相差不大尤其是当一个数组特别短、另一个特别长时min(n,m) 很小滑动窗口可能跑得比 DP 还快。空间方面滑动窗口有绝对优势它只用了几个临时变量空间复杂度 O(1)连滚动数组都省了。在做内存极敏感的嵌入式开发或者数据量特别大的批量比对时这个优势很关键。实际选择上我个人的倾向是如果两个数组长度都在几千以内DP 或滚动数组更稳时间上更可控如果数组长度很大且内存吃紧滑动窗口是更好的兜底方案。两种方法都要会写因为面试官的追问往往就是“还有没有不耗额外空间的做法”。5. 踩坑记录与排查实录5.1 滚动数组正序遍历为什么结果忽高忽低滚动数组最容易犯的错误就是内层循环方向写反。我见过不少朋友写完以后对着输出发懵因为某些测试用例答案是对的某些测试用例答案偏大还有一些偏小完全摸不着规律。偏差的主导机制上文已经讲过正序遍历时 dp[j-1] 会被当前轮提前覆盖原本需要的 dp[i-1][j-1] 被偷换成了 dp[i][j-1]。这个偷换并不总是带来错误因为当上一轮和本轮在这个位置的值恰巧相等时计算结果碰巧一致。但只要数组里恰好有一段连续匹配导致本轮某个位置的值明显大于上一轮后续所有依赖它的计算就都会被“喂大”。代码表现就是答案偶尔大、偶尔正常非常难定位。排查这种问题有一个快速方法把滚动数组版本和二维数组版本同时跑一遍逐行打印 dp 内容对比出现差异的第一个位置。如果差异总是集中在内层循环更新到一半的位置基本可以断定是循环方向问题。修复方式只有一个把内层循环从正向改为反向。这类 bug 不需要死记硬背反例牢记“依赖旧值就必须让旧值存活到被使用之后”这一条就够了。5.2 漏掉 else 清零会导致答案虚高另一个高频错误出现在滚动数组的 else 分支。有人觉得 Java int 数组自动初始化为 0既然初始是 0不匹配时什么都不用做让它保持原状不就行了不行。滚动数组最本质的特征是“复用”而复用的代价就是旧值残留。我找一个具体的例子说明。nums1 [1,0,1]nums2 [1,1,0]肉眼观察两个数组的公共子数组只有单元素最长长度是 1。但如果把滚动数组代码写成这样for (int i 1; i n; i) { for (int j m; j 1; j--) { if (nums1[i - 1] nums2[j - 1]) { dp[j] dp[j - 1] 1; ans Math.max(ans, dp[j]); } // 漏掉了 else { dp[j] 0; } } }模拟到第 3 轮外层循环也就是 nums1 的第三个元素 1 时会发现在 j2 这个位置nums1 的 1 和 nums2 的第二个元素 1 匹配dp[2] 被计算成了 dp[1] 1。而这里的 dp[1] 是一个残留的旧值 1它来自此前某一次匹配和当前的连续段根本没有关系。最终 ans 被推高到 2而正确答案是 1。排查技巧也简单如果滚动数组版本的答案比二维 DP 版本大优先检查是否漏了清零。修复之后把两个版本在随机测试数据上多跑几轮对比答案保持一致才算稳。这个问题还提醒我们在二维 DP 里可以省略的代码在滚动数组里不一定可以省略。优化的每一步都要回头重新审视原有逻辑的独立性。5.3 边界条件与空值处理清单除了方向、清零这两个大坑还有一批小边界问题值得整理成清单考试和面试时直接对号入座。首先是空数组。nums1 或 nums2 为 null或者长度为 0都没有公共子数组直接返回 0。我在代码开头用一条复合判断处理了这种情况省心省事。其次是单元素数组。两个数组分别只有一个元素且值相等返回 1值不等返回 0。这个用例看着简单却能快速验证滑动窗口代码里两个 for 循环有没有把 len 计算成 0也能验证 DP 代码的哨兵行是否正常工作。再次是数组完全相等。比如 nums1 和 nums2 都是 [5,5,5]正确答案是 3。这种情况下DP 表的主对角线会全为 1滑动窗口在偏移量为 0 的那一次对齐里能统计出完整长度。最后是数组里包含大量重复元素。比如 [0,0,0,0,0] 和 [0,0,0]答案显然是 3。重复元素会让连续匹配特别长DP 表格里对角线一路递增滑动窗口里 cur 一路累加。这种情况下最容易暴露内存溢出问题二维 DP 在这个场景下会开出很大的表如果数据规模上万直接内存紧张。如果你在测试时发现答案和预期对不上先用这三组样例排除方向与清零问题空数组、单元素数组、全相等数组。这三组全过基本能说明核心逻辑是稳的剩下的问题多半出在具体实现细节。6. 扩展思考把公共子数组本身打印出来6.1 记录结束位置再回溯输出力扣 718 只要求返回长度但实际开发里我们经常需要“把匹配到的那一段拿出来看看”比如日志异常片段定位、基因序列比对结果展示。这个扩展在原本代码框架上改动很小。思路是这样的dp[i][j] 更新为非零值时如果它刷新了当前最大长度就把当时的 i 记下来作为匹配段在 nums1 中的结束位置。为什么记 i 而不是 j因为公共子数组在两个数组里是同一段内容只要知道长度和它在 nums1 里的结束位置就能通过endIdx - maxLen算出起始位置再从 nums1 里截取出来。如果非要取 nums2 里的片段那就记 j逻辑完全对称。注意一个细节不能在最终结果算出来以后直接用 dp 表回溯去找最大格子。因为滚动数组版本已经把之前的表格覆盖掉了你根本不知道那个最大格子到底出现在哪一轮。所以必须在每次更新长度时同步记录位置这也是很多只改几行代码的版本容易疏忽的地方。6.2 代码实现与验证下面是同时返回长度和子数组内容的二维 DP 版本。为了让代码更直观我直接返回了实际子数组长度可以通过数组长度得到。如果你想保留原来的 LeetCode 签名可以把结果存在两个成员变量里或者返回长度并把数组内容打印出来。public int[] findLengthWithArray(int[] nums1, int[] nums2) { if (nums1 null || nums2 null || nums1.length 0 || nums2.length 0) { return new int[0]; } int n nums1.length; int m nums2.length; int[][] dp new int[n 1][m 1]; int maxLen 0; int endIdx -1; for (int i 1; i n; i) { for (int j 1; j m; j) { if (nums1[i - 1] nums2[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; if (dp[i][j] maxLen) { maxLen dp[i][j]; endIdx i; // 记录在 nums1 中的结束位置从 1 开始 } } else { dp[i][j] 0; } } } if (maxLen 0) { return new int[0]; } // endIdx 是 dp 表里的下标对应 nums1 的 endIdx-1 int start endIdx - maxLen; return Arrays.copyOfRange(nums1, start, endIdx); }验证一下nums1 [1,2,3,2,1]nums2 [3,2,1,4,7]dp[5][3] 达到最大值 3此时 i5endIdx5start2截取 nums1 下标 2 到 4得到 [3,2,1]完全正确。这个扩展不改变时间复杂度只是多存了一个 int成本几乎可以忽略。6.3 子序列LCS和子数组的转移方程差异最后专门聊聊和最长公共子序列力扣 1143的对比因为这是我最常被问到的问题。表格直接放在下面逻辑差别一目了然对比项最长重复子数组718最长公共子序列1143要求元素在原数组中连续元素在原数组中可跳跃相等时转移dp[i][j] dp[i-1][j-1] 1dp[i][j] dp[i-1][j-1] 1不相等时转移dp[i][j] 0dp[i][j] max(dp[i-1][j], dp[i][j-1])滚动数组遍历内层必须倒序内层也必须倒序最终答案位置全程维护最大值不落在固定角格dp[n][m] 就是答案两道题看着只差一个分支背后的语义却天差地别。子序列的不等分支取 max本质上是“断就断了但我可以从前面的最优结果继续往后拼”子数组的不等分支赋 0本质上是“断就断了一切归零从头再来”。如果你在面试时能把这两道题放在一起讲清楚差异面试官通常会更愿意相信你真的理解了连续性问题而不是只会背模板。从我自己的经验来看718 这道题最适合用来检验一个人对动态规划的理解深度。它不像背包问题那样有一堆复杂的初始化规则状态定义直白转移方程简洁空间优化方向也不难想到。真正拉开差距的地方是你能不能把“为什么不等要清零”“为什么滚动数组要反向遍历”这种问题讲明白。把这种基础题吃透了后面再遇到编辑距离、最长回文子串、戳气球这些进阶 DP至少心里会有一个清晰的坐标系。
阅读完成 · 觉得有帮助?
咨询建站