企业官网建设流程全解析

1. 三道题同屏出现，先看清它们各自的定位

如果你在跟代码随想录的刷题顺序，到了第四十四天，基本已经见过了01背包、完全背包、打家劫舍这一整条线。今天这三道题猛地一看全是字符串，跟前几天画风不太一样：115 是不同的子序列，583 是两个字符串的删除操作，72 是编辑距离。很多人一上来就硬刷，刷完三道发现好像懂了，又好像没懂。我今天想把它们放在一起复盘一遍，说清楚每道题到底在干什么，以及它们之间是怎么一层层递进关系的。

1.1 从问题类型看难度梯度

先看问题本身在问什么。

115 问的是：s 中有多少个不同的子序列等于 t。注意，它不关心你删哪几个字符，只关心最终生成的字符串是不是 t，而且要统计“个数”。这属于计数类动态规划，难点在于搞清楚什么时候该相加，什么时候该继承。

583 问的是：两个字符串都只允许删除字符，最少删多少个，能让它们变得相同。它允许你两个字符串都操作，求的是最小删除步数。这属于最优化问题，状态转移里会出现取最小值。

72 问的是：给你两个单词，增、删、替换三种操作随便用，把一个变成另一个最少要几步。这是最经典的字符串编辑距离问题，本质上和 583 共享同一套DP骨架，只是多了一个“替换”操作。

从难度上看，115 偏思维拐弯，583 是理解路径的中间节点，72 是收尾大BOSS。它们刚好组成一个“字符串编辑类DP”的完整进阶路径。

1.2 字符串DP的状态设计模板

这三道题全部可以统一成一个状态定义模板：

dp[i][j] 表示处理到第一个字符串的前 i 个字符、第二个字符串的前 j 个字符时，对应的答案是多少。

为什么大家都这么定义？因为两个字符串的比较天然是二维的。你不可能一维数组同时描述两个字符串的进度，所以二维DP几乎是唯一合理的选择。i 和 j 分别控制两个字符串的子串边界，每次比较都集中在最后一个字符上，然后往前缩小问题规模。

这里面有个很重要的习惯：不要把 dp[i][j] 直接对应到 s[i-1] 和 t[j-1]。下标偏移是这类题目最常见的出错点。代码里写 s[i-1] 是因为 dp 的 i 表示长度，而字符串索引从 0 开始，长度 i 的最后一个字符索引是 i-1。这个偏移一旦捋顺，后面所有递推公式都能套得上。

1.3 递推公式为什么都长得很像

比较字符是否相等时，这三道题几乎都走同一条主线：

• 如果 s[i-1] == t[j-1]，说明最后一个字符能匹配上，大概率可以直接沿对角线转移，也就是看 dp[i-1][j-1]；
• 如果 s[i-1] != t[j-1]，说明最后一个字符匹配不上，那就得考虑从左边来、从上边来，或者从对角线来，具体看操作给了你什么权限。

115 只有“删除 s 中的字符”这个隐性操作，所以不相等时只能继承 dp[i-1][j]；583 允许两个字符串都删，所以不相等时比较从上边和从左边转移谁更小；72 多了替换，所以不相等时还多了一条对角线 +1 的路。

你会发现，只要把“最后一步操作可能是什么”想清楚，递推公式基本就是手到擒来的事。

2. 115.不同的子序列：这道题考的其实是“计数时分类不能重”

2.1 题目到底在问什么

来，先把题意用大白话翻译一遍。给你一个字符串 s 和一个字符串 t，统计 s 中有多少个不同的子序列，能正好拼成 t。子序列就是可以不连续，但是字符相对顺序不能变。

举个例子：s = "rabbbit"，t = "rabbit"。肉眼扫一遍，你能找到三个不同的 rab-bbit 切分方式，答案是 3。

这里有个细节常被忽略：它问的是“不同的子序列”，不是“不同的选取位置”。如果两个选择方案拿到的子序列字符串相同，它们算同一个；但这种情况在匹配不同字符时本身也不会出现，所以计数时你的策略就是把每一种能匹配到 t 的“选取方式”都数出来。

这个统计过程不能靠肉眼猜，必须想清楚：当我在 s 中从左往右扫、在 t 中从上往下比的时候，每一个字符到底能提供几种贡献方式。

2.2 dp[i][j] 的定义：谁是谁的子序列

我习惯这样定义：

dp[i][j]：s 的前 i 个字符中，可以形成 t 的前 j 个字符的不同子序列个数。

注意方向，是“从 s 里选子序列去匹配 t”。不是“从 t 里选子序列匹配 s”，虽然可以对称着写，但最好始终固定一个方向，不然递推容易把自己绕晕。

初始化也从这个定义直接推出来：

• dp[i][0] = 1。因为空串 t 是任何字符串的子序列，你一个字符都不选，就只有这一种方式。
• dp[0][j] = 0（j > 0）。因为 s 是空的，无法形成非空 t。

这个初始化是整道题最容易错的地方。我第一次写的时候把 dp[0][0] 写成 0，结果所有结果都偏小。dp[0][0] 按定义是“空 s 中选空 t”，这也只有一种方式，所以必须等于 1。

2.3 递推关系里那个关键加法

现在来看核心转移。假设我已经算完了所有长度更小的状态，正站在 dp[i][j] 上。

如果 s[i-1] 不等于 t[j-1]，说明 s 当前的最后一个字符没资格作为 t 的最后一个字符。那我唯一能做的就是跳过这个字符，让问题回到“s 的前 i-1 个字符中找 t 的前 j 个字符”，也就是：

dp[i][j] = dp[i-1][j]

这个很好理解。但要小心，这里不是 dp[i-1][j-1] 也不是 0。原因很简单：s 的前 i-1 个字符里可能已经有足够多的匹配方案了，当前这个字符只是一个无关的干扰项，跳过它就行。

如果 s[i-1] == t[j-1]，这个字符就可以被纳入匹配。此时方案分为两类，互不重叠：

1. 不使用 s[i-1] 来匹配。那还是从 s 的前 i-1 个字符里找 t 的前 j 个字符，贡献 dp[i-1][j]。
2. 使用 s[i-1] 来匹配 t[j-1]。那 s 的前 i-1 个字符只需要配出 t 的前 j-1 个字符，贡献 dp[i-1][j-1]。

因为这两类方案集合完全不相交，所以直接相加：

dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

为什么不相交？简单说，第二类强制选了第 i 个字符作为 t 最后一个字符的匹配位置，第一类明确不选第 i 个字符。一个选了，一个没选，当然不可能重合。

很多人问：既然相等了，为什么不直接 dp[i-1][j-1]？这里的关键点在于：子序列匹配不是“必须用最后一个字符”，而是“可以做选择”。比如 s="aaa"，t="a"，最后一位相等也不能只从 dp[i-1][j-1] 继承，因为你不选最后一位时，前面两个字符本身已经能凑出若干种方案。dp[i-1][j] 正是帮你在计数时把这些“不选当前位”的情况算进去。

2.4 边界初始化与取模细节

LeetCode 115 最后要求答案对 10^9+7 取模。这个数字很大，但不代表你可以只在返回前取一次模。在递推过程中，每次相加后都要立即取模，否则中间值早就爆了你后面取模也没意义。

C++ 写法可以用 long long 存中间值，也可以直接 int 加一步取模一步，因为两个 int 相加后模掉，结果仍在 int 范围内，不会溢出。下面我给的代码就是每次计算后取模的形式。

2.5 参考代码（C++）与提交记录

class Solution { public: int numDistinct(string s, string t) { int n = s.size(), m = t.size(); vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0)); for (int i = 0; i <= n; i++) dp[i][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s[i-1] == t[j-1]) { dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % 1000000007; } else { dp[i][j] = dp[i-1][j]; } } } return (int)dp[n][m]; } };

我提交的时候踩过两个坑：一个是循环 j 没写等号，直接把最后一列漏掉；另一个是把模数写成了 1000000007，但在相加时忘了取模，等返回前再取模。看似没事，实际上内部一旦超过 int 上限就错了。这个题大家最好统一为“每算一步就取模”。

3. 583.两个字符串的删除操作：两种解法其实就是一件事

3.1 题目含义的DP翻译

583 的题干是：给定两个字符串 word1 和 word2，每一步可以从任意一个字符串中删除一个字符，求让两个字符串相等的最少删除步数。

这里必须抓住一个本质：所谓“相等”，就是保留下两个字符串各自的某个子序列，且这两个子序列完全相同。你会删掉 word1 中的某些字符，也会删掉 word2 中的某些字符，最后剩下来的字符串不是别的，正好是它们共同的一个子序列。

所以这道题可以从两个方向解：一个是直接模拟删除操作，另一个是绕到最长公共子序列（LCS）上算。两个方向最终答案一致，但思考路径完全不同，建议都写一遍。

3.2 解法一：直接模拟删除，步数最少

定义：

dp[i][j]：word1 前 i 个字符和 word2 前 j 个字符相等所需的最少删除次数。

初始化很好想：

• dp[i][0] = i，因为 word2 是空串时，要把 word1 前 i 个字符全删掉，需要 i 步；
• dp[0][j] = j，因为要把 word2 前 j 个字符全删掉才能得到空串。

转移时看两个字符串的当前末尾字符。

如果 word1[i-1] == word2[j-1]，说明这位不用删，保持原样，直接：

dp[i][j] = dp[i-1][j-1]

如果 word1[i-1] != word2[j-1]，那至少得删一个字符。要么删 word1 的末尾字符，变成 dp[i-1][j] 后再加 1；要么删 word2 的末尾字符，变成 dp[i][j-1] 后再加 1。两个方案取较小：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1

这里有一个隐藏细节：为什么不考虑“同时删掉 word1 和 word2 各一个字符”，也就是 dp[i-1][j-1] + 2？答案是因为这个方案已经被包含了。当你先删 word1 的末尾字符到达 dp[i-1][j]，这个状态里的 j 还是完整的 word2，后面再删 word2 的一位，自然会被 dp[i-1][j] 的后续转移覆盖到。min 操作自动处理了这种情况，所以不需要单独写一种删除两个字符的转移。

3.3 解法二：最长公共子序列绕个弯

另一种思路是先用标准 LCS 方法求出 word1 和 word2 的最长公共子序列长度，然后：

最少删除步数 = word1.size() + word2.size() - 2 * LCS长度

这个公式的直觉是：最长公共子序列就是我们最后能保留下来的部分。word1 中不属于这个公共子序列的字符都得删掉，word2 中也不属于这个公共子序列的字符也得删掉。所以总删除数就是两边字符串长度之和，减去公共子序列长度被算了两遍的部分。

LCS 的 dp 定义如下：

dp[i][j]：word1 前 i 个字符和 word2 前 j 个字符的最长公共子序列长度。

转移：

• 末尾相等：dp[i][j] = dp[i-1][j-1] + 1
• 末尾不等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3.4 两种解法为什么答案一致

有人会疑惑：为什么直接删除的解法结果和 LCS 绕一圈的结果完全一致？

因为本质上它们描述的是同一个优化问题的两个投影。直接删除解法在每次末尾不匹配时，决定删 word1 还是删 word2，这个过程最终留下来的字符集合一定是一个公共子序列；而为了让删除次数最少，等价于让这个公共子序列最长。所以当状态收敛到 dp[n][m] 时，直接解法得到的最小删除数，恰好等于 n + m - 2 * LCS。

我觉得这个等价关系比题目本身更重要。它解释了很多字符串编辑类问题背后的统一逻辑：你删得越少，保留的共同部分就越多；保留的共同部分越多，删除就越少。

以下是我刷 583 时写的两种方案代码。

解法一代码：

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

解法二代码：

class Solution { public: int minDistance(string word1, string word2) { int n = word1.size(), m = word2.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 (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]); } } } return n + m - 2 * dp[n][m]; } };

3.5 代码实现与注意事项

刷这道题时有两个容易忽略的细节。

第一个是初始化。直接解法里 dp[i][0] 和 dp[0][j] 必须赋成对应长度，否则后续所有删除操作的计数都会少算。赋值时注意循环写成 i <= n、j <= m，不要漏掉边界行和列。

第二个是“末尾相等直接继承”这个行为。有人会问：末尾相等时，我偏要删掉这个相等的字符，然后继续匹配，会不会更优？答案是不会，因为相等的字符留着它，不会增加任何删除成本，却能为后面的匹配多保留一个字符的位置。如果你删它，等于白白多删一步，不可能比继承 dp[i-1][j-1] 更小。所以相等时无条件走对角线即可，不必比较删掉它的方案。

4. 72.编辑距离：从“删”到“改”，递推公式是怎么长出来的

4.1 为什么编辑距离是经典中的经典

编辑距离在很多地方被称为 Levenshtein Distance，是字符串匹配、拼写纠错、DNA序列比对等场景的基础算法。面试里它也是动态规划的高频题，几乎每个刷题的人都绕不开。

题目允许三种操作：插入一个字符、删除一个字符、替换一个字符。目标是用最少的操作次数，把 word1 变成 word2。对比 583，这里多了一个替换操作。很多人一开始会纠结：插入和删除明明是两类操作，为什么递推公式里看起来只是在处理“删除”？

关键理解是：当你把 word1 当成基准时，对 word1 做插入，等价于对 word2 做删除。所以三种操作可以被统一归约成“从 word1 的角度操作”：

• 删除 word1 的一个字符；
• 在 word1 当前位置插入一个字符（等价于删除 word2 的对应字符）；
• 把 word1 的当前字符替换成 word2 的对应字符。

想通这一点，递推公式就顺理成章了。

4.2 三种操作对应三个方向的转移

定义：

dp[i][j]：word1 的前 i 个字符转换成 word2 的前 j 个字符需要的最少操作数。

初始化依旧是最简单的边界推理：

• dp[i][0] = i：把 word1 前 i 个字符全删掉，操作 i 次；
• dp[0][j] = j：从空串生成 word2 的前 j 个字符，需要插入 j 次。

为什么要单独把 dp[0][j] 看作插入？因为对于空串 word1 来说，要变成 word2，只能不断插入。这和全局定义的“编辑距离”是自洽的。

正式递推时，假设两个字符串的当前末尾分别是 c1 = word1[i-1] 和 c2 = word2[j-1]。

如果 c1 == c2，那什么都不用做，直接：

dp[i][j] = dp[i-1][j-1]

如果 c1 != c2，那最后一步只能从三种操作里选一种：

1. 删除 c1：问题变成把 word1 前 i-1 个字符转换成 word2 前 j 个字符，再补一次删除操作。代价是 dp[i-1][j] + 1。
2. 在 word1 末尾插入一个字符，让新字符与 c2 对齐：等价于让 word1 前 i 个字符去匹配 word2 前 j-1 个字符，再插入 c2。代价是 dp[i][j-1] + 1。
3. 把 c1 替换为 c2：让 word1 前 i-1 个字符和 word2 前 j-1 个字符先相等，再替换掉最后一个字符。代价是 dp[i-1][j-1] + 1。

三者取最小：

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

这里最容易产生疑问的是第 3 项：替换明明是一次操作，为什么不能拆成“删除 c1 + 插入 c2”两步？实际上拆开就是 2 次操作，而替换只要 1 次，所以取最小值时替换一定不劣于删除加插入的组合。这也是为什么编辑距离公式里没有必要显式写“删除 + 插入”这种两步组合，因为替换那条路径已经覆盖并胜出。

4.3 相等与不等：递推公式的分支

说实话，72 和 583 的代码结构非常像，唯一的区别就在不相等分支里多了一个 dp[i-1][j-1] + 1。

583 的不相等分支是 min(dp[i-1][j], dp[i][j-1]) + 1，没有对角线 + 1 的选项。为什么 583 里不需要对角线 + 1？因为 583 里没有替换操作，你要么删 word1，要么删 word2，靠两步删除才能把两个不同字符“消掉”。而 72 只需要一次替换，所以对角线 + 1 会被 min 选中，使得结果比 583 更小。

这也回答了一个常见困惑：为什么 583 的解不能直接用 LCS 公式套在 72 上？因为 LCS 只处理“匹配”和“不匹配”，没有“替换”这种等价于把不匹配变成匹配的 1 步操作。编辑距离里，即使两个字符不等，也可以直接一对一把它改成相等。

4.4 代码实现与复杂度分析

编辑距离的经典代码长这样：

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

时间和空间复杂度都是 O(n*m)。如果两个字符串比较长，可以用滚动数组降复杂度空间到 O(m)，后面避坑部分我会展开讲。

写完代码后，推荐手动推一遍 word1 = "horse", word2 = "ros" 的表格。这个例子来自 LeetCode 官方，手动推完对状态转移的直观感受会强很多。我每次面试前都会拿这个小例子快速画一遍表，三分钟就能找回手感。

4.5 从583到72的思维迁移

如果你先刷 583 再刷 72，最大的体会应该是：递推公式不是靠背的，而是靠“操作集合”变化推导出来的。

583 的操作集合是：{删除 word1 一个字符，删除 word2 一个字符}。所以不匹配时只有两个方向可以选择。

72 的操作集合是：{删除 word1 一个字符，在 word1 插入一个字符（等价于删除 word2 一个字符），替换 word1 一个字符}。所以不匹配时有三个方向可以选择。

多一个操作，就多一条转移路径。少一个操作，就少一条路径。这样理解，你就不会再把这三个公式记混。

5. 三道题刷完后的避坑清单和对比表

5.1 初始化是重灾区

这三道题里，初始化错误占了我在 LeetCode 上提交失败的一大半原因。

115 的 dp[i][0] = 1 最反直觉。你想想，dp[i][0] 表示空串出现次数，任何字符串里空串都只出现一次，所以每一行第一个都是 1。很多人下意识写成 0，结果整个 dp 表格全部偏差。

583 和 72 的初始化都是 dp[i][0] = i、dp[0][j] = j。这个初看起来合理，但只要漏掉 dp[0][0] 的位置，或者在循环里漏掉等号，第一行第一列就会错位。比如我只写了 for (int i = 1; i < n; i++) 时，dp[0][0] 还是 0，但后续 dp[1][1] 会继承一个错误的值。

写题时我有一个习惯：先把 dp 表打印出来，检查第一行、第一列是不是符合预期，再检查中间数据。打印一次比口头推理十次都管用。

5.2 遍历顺序：内外层可以怎么换

这三道题的 DP 递推都是无环的，因为 dp[i][j] 只依赖二维表中左上角的位置：dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。只要 i 和 j 都从 1 递增，就能保证每个依赖项已经被计算过。

所以外层循环 i、内层循环 j 与 外层循环 j、内层循环 i 都可以，结果不会变。我习惯固定成第一维外层，因为和 dp 定义的方向一致，写起来不容易乱。

有一些人会担心“顺序”影响结果，其实完全不必。这类字符串 DP 不像背包那样有“容量遍历方向”的限制。你在纸上画一个矩阵，按从左到右、从上到下的顺序填，天然就能满足依赖。

5.3 滚动数组的坑

如果不想用 O(n*m) 空间，可以用一维数组做滚动优化。660 583 和 72 都能优化，但要注意覆盖顺序。

因为 dp[i][j] 依赖 dp[i-1][j-1]（左上角）和 dp[i-1][j]（正上方），压缩成一维后，正上方 dp[i-1][j] 可以直接用当前数组里的 dp[j] 表示；但左上角 dp[i-1][j-1] 需要提前保存。

处理方法是：在更新 dp[j] 之前，先把旧值 dp[j-1] 记录下来，再更新。如果直接原地覆盖，左上角信息就会丢失。

以编辑距离为例的滚动数组写法：

class Solution { public: int minDistance(string word1, string word2) { int n = word1.size(), m = word2.size(); vector<int> dp(m + 1); for (int j = 0; j <= m; j++) dp[j] = j; for (int i = 1; i <= n; i++) { int pre = dp[0]; dp[0] = i; for (int j = 1; j <= m; j++) { int temp = dp[j]; if (word1[i-1] == word2[j-1]) { dp[j] = pre; } else { dp[j] = min({dp[j], dp[j-1], pre}) + 1; } pre = temp; } } return dp[m]; } };

这种写法面试中能加分，但日常刷题复盘建议先写二维版本，确保思路清晰后再优化空间。

5.4 一页纸对比：状态定义、递推公式、初始化、复杂度

下面这张表最适合在刷完三道题后对照着看：

把这张表记熟，再做变形题时基本就能一眼定位到核心转移。

5.5 刷题复盘建议

连续刷完这三道以后，最值得做的一件事是把它们和之前刷过的 LCS 题放在一起对比。你会发现，LCS、583、72 其实就是同一族题的三个版本：

• LCS 问最长公共子序列；
• 583 问删除到相等的最少步数，等价于 n + m - 2 * LCS；
• 72 在 LCS 基础上加了替换操作，使得不匹配时只需 1 步就能消掉差异。

我在复盘时会把这三个公式都手写一遍，再脑内模拟“abcdef”和“azced”这类小串的完整推演过程。别看操作小，它对建立状态转移的直觉特别有效。面试时被问到编辑距离的变体题，比如“只允许删除和替换，最少操作数是多少”，你在纸上画个 3x3 的 dp 表格，比背公式要稳得多。

最后说个刷题习惯的问题：这三道题的题解区有大量人直接贴代码，但很少人把“为什么这个状态转移是对的”写成文字。如果你也是刷完就忘的体质，建议每道题抽几分钟，用自己的话把递推公式的推导写一遍，就写在代码注释里。这个动作看起来多余，实际是我觉得最能抵抗“刷题失忆”的办法。