LeetCode二维DP实战：交错字符串与最小ASCII删除和C++详解

昨晚刷题刷到 LeetCode 97（交错字符串）和 712（两个字符串的最小 ASCII 删除和），顺手把这两道题放在同一轮动态规划练习里做，用的是 C++。做完之后我意识到，这两道题放在一起的价值远大于单独刷任何一道——它们一个考布尔状态怎么在二维网格上有序流动，一个考怎么把“删除代价”这种看起来不太友好的目标，翻译成最长公共子序列的变体。更关键的是，这两题在 C++ 的实现细节里都有不少隐藏的坑，比如vector<bool>的特化问题、滚动数组覆盖顺序问题、char 转 int 的累加问题，随便踩一个都会让人怀疑人生。这篇就把我完整的推导过程、代码写法、踩坑记录都摊开讲讲，适合正在练二维 DP、准备 C++ 面试，或者刷题刚好刷到这个阶段的读者。

1. 这两道题为什么值得放在一起刷

先简单交代一下题目背景，方便没做过这两题的读者跟上节奏。

交错字符串（LeetCode 97）给三个字符串s1、s2、s3，判断s3能否由s1和s2交错组成。所谓交错，就是保持s1和s2各自字符的相对顺序不变，把两个序列交替穿插在一起。举个例子，s1 = "aabcc"，s2 = "dbbca"，s3 = "aadbbcbcac"，这个s3就是合法的交错结果；但同样两个源串，s3 = "aadbbbaccc"就是非法的。

两个字符串的最小 ASCII 删除和（LeetCode 712）则是一道带权重的字符串匹配题。给定s1和s2，可以删除两个字符串中的任意字符，使得删除之后两个字符串完全相同，要求删除的所有字符的 ASCII 值之和最小。比如s1 = "sea"，s2 = "eat"，最优做法是删除s1中的s（ASCII 115）和s2中的t（ASCII 116），总代价 231，剩下两个"ea"相等。

这两道题从表面看，一个是“判断能不能”，一个是“求最小代价”，题型完全不同。但深入看，它们的核心状态设计都是二维的，都依赖“两个指针分别指向两个字符串的某个位置”这种视角。更妙的是，相交字符串的重点在“选择从哪里取下一个字符”，最小 ASCII 删除和的重点在“选择保留哪些字符作为公共子序列”。一个用布尔值在网格上做可达性传递，一个用整数在做带权的最优子结构汇总。把这两题放在一起练，正好能建立二维 DP 里“状态定义决定一切”的感觉，练完再回头去做编辑距离、最长公共子序列这些经典题，思路会顺很多。

我建议的刷题顺序是：先做交错字符串，因为它的布尔转移简单直白，适合建立二维网格的直觉；再做最小 ASCII 删除和，因为这题需要一次视角转换，做完会有“原来 DP 还能这样翻译问题”的顿悟感。下面就从交错字符串开始拆解。

2. 交错字符串：双指针直觉的坍缩瞬间

我第一次看到这题的时候，第一反应是：这题不是双指针就能做吗？三个指针分别指向s1、s2、s3，遍历s3，当前字符如果和s1指针指的字符相同就推进s1，否则如果和s2指针指的字符相同就推进s2，都不相同就返回 false。逻辑简单，代码十行搞定。这么想的人不止我一个，评论区一抓一大把。

这个方案在大多数测试用例上确实能跑通，但有一个致命问题：当s3当前字符同时匹配s1和s2的指针字符时，双指针没有能力做出正确的选择。它只能按固定优先级取一个先试，如果这条路后面走不通，它不会回头尝试另一条。我用题目里的反例走一遍你就懂了。

设s1 = "aabcc"，s2 = "dbbca"，s3 = "aadbbbaccc"。双指针从头开始：

• 位置 0，s3[0] = 'a'，只有s1当前字符是a，推进s1；
• 位置 1，s3[1] = 'a'，s1当前字符还是a，继续推进s1；
• 位置 2，s3[2] = 'd'，s1当前是b，s2当前是d，只能推进s2；
• 位置 3，s3[3] = 'b'，s1当前是b，s2当前是b，两边都能匹配。双指针的固定策略里通常会优先选s1，于是推进s1；
• 位置 4，s3[4] = 'b'，s1当前是c，s2当前是b，只能推进s2；
• 位置 5，s3[5] = 'b'，s1当前是c，s2当前是b，只能推进s2；
• 位置 6，s3[6] = 'b'，s1当前是c，s2当前是c，两边都不匹配，宣告失败。

但问题来了：失败就代表s3真的交错不出来吗？不一定。刚才第 3 步那个抉择点，如果当时不推进s1，而是推进s2，后面也许还有救。双指针的问题就在于，它只有一次生命，选错了就死了，没有回溯机制。而交错字符串是一个全局可达性问题，需要的是在每一步都清楚“当前已经用掉了s1的前几个、s2的前几个”这个完整状态，然后看从这个状态能走到哪些新状态。这正是动态规划的用武之地。

这里我多说一句，很多人会误以为双指针失败是因为“优先级选错了”，那我们改成“优先选 s2”不就行了？还是不行。因为冲突点不止一个，每个冲突点都要做选择，选路的组合数是 2 的 k 次方（k 是冲突次数），本质上是在一个二维状态空间里做探索。凡是这种“多个选择组合起来决定最终结果”的问题，贪心的单一路径基本都不靠谱，老老实实上 DP 或者带记忆化的 DFS。

2.1 把“选择”翻译成“二维状态”

既然要覆盖所有选择组合，自然想到用一个二维布尔数组来描述状态。定义dp[i][j]表示：s1的前i个字符和s2的前j个字符，能否交错组成s3的前i + j个字符。

为什么是i + j而不是单独一个 k？因为交错结果的长度被i和j唯一确定。整个过程中s3被用掉的长度不可能超过i + j，也不可能少于i + j，所以s3的下标不用单独开一维，直接由i + j推导出来。这是二维 DP 里常见的“压缩维度”技巧，它能成立的前提是状态之间的长度约束是线性的。

有了这个定义后，转移就非常顺了。dp[i][j]为 true 当且仅当满足下面两个条件之一：

• s1[i-1]等于s3[i+j-1]，并且dp[i-1][j]已经是 true。也就是说，当前s3的最后一个字符是从s1里取的，而取之前的状态是合法的；
• s2[j-1]等于s3[i+j-1]，并且dp[i][j-1]已经是 true。也就是说，当前s3的最后一个字符是从s2里取的。

用逻辑表达式写就是：

dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j]) || (s2[j-1] == s3[i+j-1] && dp[i][j-1])

初始化要注意三个点。第一，dp[0][0] = true，两个空串当然能交错出空串。第二，第一行dp[0][j]只能靠s2一路匹配s3推出来，因为此时s1一个字符都没用，任何来自s1的转移都不存在。第三，第一列dp[i][0]同理，只能靠s1一路匹配推出来。

有一个很重要的预判：如果s1.size() + s2.size() != s3.size()，长度都不等，直接返回 false，不用进 DP。这个判断放在最前面，可以省掉一整张表的时间。虽然它不影响最终答案的正确性，但它能让你在数据明显不合法时快速退出，而且写出来也显得你对问题有整体感，面试时这是一个加分的小细节。

2.2 填表过程：一个 3×3 的小例子

光说公式还是有点虚，我拿一个简单例子手动填一遍。设s1 = "ab"，s2 = "cd"，s3 = "acbd"。长度校验通过，4 = 2 + 2。

初始化：

dp[0][0] = true 第一行：s2 = "cd"，s3 前 j 个字符依次是 "a"、"ac"、"acb" dp[0][1]：s3[0]='a'，s2[0]='c'，不匹配，所以 false dp[0][2]：s3[1]='c'，s2[1]='d'，不匹配（而且 dp[0][1] 已经是 false），false 第一列：s1 = "ab"，s3 前 i 个字符依次是 "a"、"ac" dp[1][0]：s3[0]='a'，s1[0]='a'，匹配，且 dp[0][0]=true，所以 true dp[2][0]：s3[1]='c'，s1[1]='b'，不匹配，false

填内部：

dp[1][1]：i=1, j=1，s3[1]='c' 看 s1[0]='a' 是否等于 'c'？不等，第一个条件不成立； 看 s2[0]='c' 是否等于 'c'？相等，且 dp[1][0]=true，所以 dp[1][1]=true dp[1][2]：i=1, j=2，s3[2]='b' 看 s1[0]='a' 是否等于 'b'？不等； 看 s2[1]='d' 是否等于 'b'？不等； 所以 false dp[2][1]：i=2, j=1，s3[2]='b' 看 s1[1]='b' 是否等于 'b'？相等，且 dp[1][1]=true，所以 true； 另一个条件不看也行，反正已经 true dp[2][2]：i=2, j=2，s3[3]='d' 看 s1[1]='b' 是否等于 'd'？不等； 看 s2[1]='d' 是否等于 'd'？相等，且 dp[2][1]=true，所以 dp[2][2]=true

最终dp[2][2]为 true，返回 true。这个例子里s3 = "acbd"，实际交错方式是a从 s1 取，c从 s2 取，b从 s1 取，d从 s2 取，完全吻合。手动填两三次之后，这个 DP 的“流动感”就出来了——true 状态像水一样从左上角向右下角蔓延，每个格子的水都只可能来自上方或左方。

2.3 C++ 代码：基础版二维布尔表

直接上代码，注释我写得比较细，方便直接对照理解。

class Solution { public: bool isInterleave(string s1, string s2, string s3) { int n = s1.size(), m = s2.size(); if (n + m != s3.size()) return false; vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false)); dp[0][0] = true; // 初始化第一列：只用 s1 的字符去匹配 s3 for (int i = 1; i <= n; ++i) { dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]); } // 初始化第一行：只用 s2 的字符去匹配 s3 for (int j = 1; j <= m; ++j) { dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { char target = s3[i + j - 1]; if (s1[i - 1] == target && dp[i - 1][j]) { dp[i][j] = true; } if (s2[j - 1] == target && dp[i][j - 1]) { dp[i][j] = true; } } } return dp[n][m]; } };

这里第一列初始化的写法dp[i][0] = dp[i-1][0] && ...是一个小小的化简，它把“上一个状态为 true 且当前字符匹配”两个条件合并到了一行。我第一次写的时候是先判断dp[i-1][0]再单独赋值，后来发现这样写更紧凑，也更不容易漏状态。我建议你也把这种初始化方式记住，因为它可以用来处理很多带前缀条件的 DP 初始化。

3. 滚动数组优化：C++ 里最容易写错的细节

交错字符串的空间复杂度是 O(n×m)，当 n 和 m 都到几百时，一张vector<vector<bool>>其实还好，LeetCode 上完全能过。但面试官大概率会追问一句：能不能把空间优化到 O(m)？

能。核心观察是转移方程里dp[i][j]只依赖dp[i-1][j]（上一行同一列）和dp[i][j-1]（当前行前一列）。也就是说，当我们按行从左到右计算时，只需要保留当前这一行的数据，上一行的数据用完即弃。这就是经典的滚动数组思路。

用一维数组dp[j]表示当前行第 j 列的值。关键是理解两个时间点：

• 在更新dp[j]之前，dp[j]里存的还是上一行同一列的值，也就是原来的dp[i-1][j]；
• 在更新dp[j]之前，dp[j-1]已经被这一轮循环更新过了，它代表的是原来的dp[i][j-1]。

所以如果你从左往右遍历 j，那么在算第 j 列时，dp[j]和dp[j-1]恰好就分别对应转移方程需要的两个值。这个“歪打正着”的顺序，其实是滚动数组能成立的核心。我见过不少人写成从右往左遍历，结果把dp[j-1]读成了上一行的值，整个 DP 直接废掉。这也是“编辑距离”“最长公共子序列”等一维优化题的共同陷阱，务必记牢。

一个容易忽略的细节是：第一列dp[0]也必须跟着每一轮 i 的更新而更新。因为dp[i][0]依赖dp[i-1][0]，在滚动数组里，dp[0]就是上一轮 i 结束时留下的值。所以循环里 j 要从 0 开始，而不是从 1 开始，否则第一列永远不更新。

我写的滚动数组版代码如下，每一行的含义都标注了：

class Solution { public: bool isInterleave(string s1, string s2, string s3) { int n = s1.size(), m = s2.size(); if (n + m != s3.size()) return false; // 为了减少空间，可以让更短的那个字符串作为 j 维度 if (n < m) { swap(s1, s2); swap(n, m); } vector<bool> dp(m + 1, false); dp[0] = true; for (int i = 0; i <= n; ++i) { for (int j = 0; j <= m; ++j) { if (i == 0 && j == 0) continue; bool cur = false; if (i > 0 && s1[i - 1] == s3[i + j - 1]) { // 此时 dp[j] 尚未被覆盖，仍然是 dp[i-1][j] cur = cur || dp[j]; } if (j > 0 && s2[j - 1] == s3[i + j - 1]) { // 此时 dp[j-1] 已经在本次 i 循环中被更新过 cur = cur || dp[j - 1]; } dp[j] = cur; } } return dp[m]; } };

这里我做了一个小优化：如果s1比s2短，就把两个字符串交换，保证 j 这一维对应较短的字符串。这样空间能进一步压缩到 O(min(n, m))。代价是要注意交换后循环的上界也跟着变，我这里的n和m在swap后已经同步更新，不会出错。

另外提醒一个 C++ 特有的坑：vector<bool>不是普通的布尔数组，它是被特化过的，内部按位压缩存储，operator[]返回的是一个代理对象而不是真正的bool&。这个设计在多数场景下无感，但如果你写auto& ref = dp[j]或者试图对某个元素取地址，编译器会报错。而且因为位压缩，vector<bool>的读写性能在某些实现下反而比vector<char>慢。刷题场景下，如果追求性能稳定，可以直接用vector<char>代替vector<bool>，内存略多一点但操作更快、更直觉。不过 LeetCode 的测试数据下，vector<bool>通常也能过，不用太焦虑，知道有这回事就行。

4. 最小 ASCII 删除和：把“删除”翻译成“保留”

做完了交错字符串，再来看 712 这道题，核心难点瞬间转移到了“怎么理解问题”。

题目要求的是删除一些字符，让两个字符串相同。很多人第一反应是暴力枚举删哪些字符，但两个串加起来最长能到 1000，枚举组合数直接爆炸，这条路走不通。也有人的第一反应是“这题是不是编辑距离的变种？”，方向是对的，但要进一步想清楚权重怎么设。

我推荐一个视角转换：删除后剩下的字符串，必须同时是s1和s2的子序列。也就是说，我们实际上是在找两个字符串的一个公共子序列，并且希望这个公共子序列的 ASCII 值之和尽量大。因为总 ASCII 和是固定的，删除代价 = 总 ASCII 和 - 2 × 保留的公共子序列 ASCII 和。把“最小化删除代价”这个听起来吓人的目标，转化成“最大化保留价值”这个标准的带权 LCS 变体，问题一下子就顺了。

举例验证一下这个转换。s1 = "sea"，ASCII 和是 115 + 101 + 97 = 313；s2 = "eat"，ASCII 和是 101 + 97 + 116 = 314；总和 627。两个字符串的公共子序列有"e"（101）、"a"（97）、"ea"（198），最大的是"ea"= 198。那么删除代价就是 627 - 2 × 198 = 231，和题目示例答案一致。这个转换一旦想通，代码反而比交错字符串还简单，因为它就是一个标准的二维 DP，不带任何布尔可达性的“跳跃感”。

4.1 状态设计与转移方程

定义dp[i][j]表示s1前 i 个字符和s2前 j 个字符的公共子序列的 ASCII 值之和的最大值。这是标准的 LCS 状态定义，只是把经典的“长度 +1”换成了“ASCII 值相加”。

转移分两种情况：

• 如果s1[i-1] == s2[j-1]，说明这两个字符可以同时被保留在公共子序列里，那么dp[i][j] = dp[i-1][j-1] + int(s1[i-1])；
• 如果不相等，说明这两个字符不能同时出现在公共子序列里，只能选择放弃其中一个，取max(dp[i-1][j], dp[i][j-1])。

初始化很简单，dp[0][j]和dp[i][0]都等于 0，因为空串和任何字符串的公共子序列都为空，ASCII 和为 0。这也是为什么这题初始化比交错字符串轻松——交错字符串的第一行第一列要做匹配判断，而这里天然是 0。

代码如下：

class Solution { public: int minimumDeleteSum(string s1, string s2) { int n = s1.size(), m = s2.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + static_cast<int>(s1[i - 1]); } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } int total = 0; for (char c : s1) total += static_cast<int>(c); for (char c : s2) total += static_cast<int>(c); return total - 2 * dp[n][m]; } };

复杂度 O(n×m) 时间和 O(n×m) 空间。这个题同样可以滚动数组优化到 O(m)，因为转移只依赖上一行和当前行前一列，和交错字符串的依赖关系完全一致。但实际刷题中，712 的n、m上限大概是 1000，二维int数组 1001×1001 大约是 4 MB，完全能接受，所以我建议先把二维版本写对，有余力再优化。

4.2 另一种“直接 DP 删除代价”的写法

上面的解法是“间接法”，先求最大保留，再算删除代价。其实还有一种“直接法”，状态定义直接就是删除代价：dp[i][j]表示让s1前 i 个字符和s2前 j 个字符完全相同所需的最小 ASCII 删除和。

转移思路是这样的：

• 如果s1[i-1] == s2[j-1]，这个字符匹配上了，不需要删，dp[i][j] = dp[i-1][j-1]；
• 如果不相等，那至少要从s1或s2里删一个字符。删s1[i-1]的话，代价是dp[i-1][j] + int(s1[i-1])；删s2[j-1]的话，代价是dp[i][j-1] + int(s2[j-1])，取两者较小值。

初始化比较麻烦：dp[i][0]表示让s1前 i 个字符变成空串，只能全部删掉，所以dp[i][0] = dp[i-1][0] + int(s1[i-1])；dp[0][j]同理。

class Solution { public: int minimumDeleteSum(string s1, string s2) { int n = s1.size(), m = s2.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); for (int i = 1; i <= n; ++i) { dp[i][0] = dp[i - 1][0] + static_cast<int>(s1[i - 1]); } for (int j = 1; j <= m; ++j) { dp[0][j] = dp[0][j - 1] + static_cast<int>(s2[j - 1]); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++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] + static_cast<int>(s1[i - 1]), dp[i][j - 1] + static_cast<int>(s2[j - 1]) ); } } } return dp[n][m]; } };

两种写法对比，我个人的看法是：间接法（转 LCS）更难想到，但一旦想到，代码更短、初始化更省心；直接法更符合人的直觉，状态含义一目了然，不容易在面试时被追问“为什么这么定义”，缺点是初始化要单独处理。面试时我更推荐先说直接法，因为它好解释；如果面试官追问“有没有更简洁的思路”，再把间接法作为优化方案抛出来，会显得你对问题的理解有层次。

5. 从这两道题里提炼出的一套 C++ 刷题手记

两道题刷完，我顺手把过程中涉及的 C++ 细节和 DP 通用套路整理了一下，分享一下。

5.1 字符串 DP 里的 char 转 int：别被符号位吓到

这两道题都涉及把字符的 ASCII 值累加。char类型在 C++ 里到底是 signed 还是 unsigned，标准没有强制规定，取决于编译器实现。如果是在 x86 的 GCC/MinGW 下，char默认是 signed，取值范围是 -128 到 127。但 ASCII 码表只用到 0 到 127，所以直接把char转成int累加不会出现负数。static_cast<int>(c)这个写法在任何环境下都是安全的，建议养成习惯。不要用int(c - '0')这种写法，那是数字字符转整数的套路，这里我们要的是字符的 ASCII 值本身，不是数字含义。

有人可能会问，万一字符是扩展字符集里超过 127 的怎么办？LeetCode 的测试数据不会出现这种情况，题目也明确说了是英文小写/大写字母和常见可见字符，ASCII 值都在安全范围内。如果要更严谨，可以用unsigned char做一个中间转换，但刷题场景没必要。

5.2 二维 vector 的初始化：别写出一堆重复代码

这两题的 DP 表初始化我都用了vector<vector<bool>>(n + 1, vector<bool>(m + 1, false))这种写法。注意内层的vector<bool>(m + 1, false)不能省，否则你会得到一堆空的行。很多人刚接触二维 vector 时会写vector<vector<bool>> dp(n + 1)，然后忘记给每一行分配列，后面一访问dp[i][j]就崩。正确写法里第二个参数的意义就是“每一行初始化为一个长度为 m+1、值全为 false 的 vector”。

如果追求性能，可以用一维数组模拟二维下标，比如vector<int> dp((n + 1) * (m + 1), 0)，然后通过dp[i * (m + 1) + j]访问。这样可以减少 vector 套 vector 的指针跳转开销，在大数据量下会快一些。不过 LeetCode 这种规模，字面量二维 vector 完全够用，代码可读性更好，我建议刷题时以可读性优先。

5.3 二维 DP 的状态设计五步法

做完这两题，我总结了一个二维字符串 DP 的五步套路，后续遇到类似题可以直接套：

1. 理解清楚两个字符串的“指针”各走到哪里，用i、j表示前缀长度，这是状态的第一维和第二维；
2. 明确dp[i][j]存什么——是布尔可达性、最小代价、最大价值还是方案数，这决定了转移里的运算符是||、min还是max；
3. 写出当前字符相等和不相等两种情况下的转移表达式；如果题目语义不是“匹配字符”，就转换成“当前步能做什么决策”，比如从哪个字符串取、删哪个字符串的字符；
4. 处理初始化：第一行、第一列往往有特殊的物理含义，不要漏；
5. 考虑返回值是dp[n][m]还是需要额外计算，比如 712 题最终答案不是dp[n][m]本身，而是total - 2 * dp[n][m]。

这个五步法不是我发明的，但我是真练多了才形成肌肉记忆的。最开始刷 DP 时，我总喜欢直接上手写转移方程，结果经常在初始化上卡半小时。后来我强迫自己先花两分钟把状态定义用一句完整的话写出来，再动代码，正确率明显上来了。

5.4 关于面试追问和 DP 知识边界

LeetCode 高频题的面试价值在于，考官特别喜欢在基础题上做变形追问。交错字符串考完，可能会追问“如何输出一种具体的交错方案”，这个需要额外维护一个path决策数组，然后在 DP 完成后从dp[n][m]反向回溯，每一步检查是从上方转移来的还是从左方转移来的。最小 ASCII 删除和考完，可能会追问“如果删除代价不是 ASCII 值，而是每个字符有独立的权重，怎么做”，答案就是直接把权重数组作为转移里加的那个数，其他逻辑完全不变。

还有一种常见的延伸问题是“KMP 算法的 next 数组是不是动态规划”。这个问题看起来像是在考 DP 定义，实际上是在考你对 DP 两个核心特征（重叠子问题、最优子结构）的理解。KMP 的 next 数组推导有重叠子问题的味道，但它不满足经典 DP 的无后效性建模，特别是 next 有回退逻辑，更像是带记忆的回溯或者有限状态自动机的构建。所以严谨地说，KMP 不属于标准动态规划。面试如果被问到，可以从“状态转移里有没有决策和最优子结构”这个角度去分析，而不是死记结论。这个知识边界想在刷题之余横向巩固一下的话，可以先去做做编辑距离和正则表达式匹配（LeetCode 10），做完你对“哪些属于 DP、哪些不算”会有更清晰的体感。

5.5 给你的刷题路线建议

这两道题刷完后，我建议的下一批题目是：编辑距离（经典中的经典）、最长公共子序列（LCS 长度版）、不同的子序列（方案数版）、正则表达式匹配（状态设计更复杂的进阶）。它们全是二维字符串 DP，状态设计和转移模式高度相似，练完基本能把这类题彻底吃透。视觉上，这些题的代码结构都很像——一个二维表、两个 for 循环、三行转移逻辑，但每一题的状态含义都不同。这个“似而不同”的感觉，恰恰是动态规划最迷人的地方。

我在实际刷题中还有一个习惯，就是每做完一组同类型题，会把它们的“状态含义”和“转移方程”记在一个表格里，贴在本地笔记中。比如这组我就记了：

下次复习的时候，扫一眼表格就能回忆起一整套思路，比重新翻代码高效得多。

最后再分享一个小技巧：如果你用的是 VS Code 写 C++ 刷题，不需要配什么复杂的 CMake 工程，装好编译器后，一个简单的 tasks.json 配置单文件编译调试就够用了。我自己的配置是 g++ 编译命令加上-std=c++17 -Wall，调试器用 codelldb，遇到段错误或者数组越界也能快速定位到行号。把这些工具层面的事情提前搞定，刷题时才能把注意力全部放在算法本身上。