企业官网建设流程全解析

直接说结论：LeetCode 139这道题，属于典型的“看着简单、一写就卡”的动态规划入门题。它在LeetCode热门100题里地位很稳，周赛前翻题解也经常能看到它的身影——但很多人其实是背了状态转移方程，没真正想明白为什么这么设计。这篇就把我刷这道题的全过程掰开揉碎，从暴力递归到记忆化搜索再到标准DP，完整讲清楚。适合正在刷动态规划、但总觉得“状态设计”很玄学的同学，也适合面试前想快速把字符串类DP的套路梳理清楚的人。

1. 题目还原：先看懂它到底在问什么

1.1 原题描述与核心需求解析

题目给的信息不多：一个字符串s，一个装着若干单词的字典wordDict，要判断s能否被拆分成若干个单词，并且这些单词都必须出现在字典里。注意几个容易忽略的细节：拆分出来的单词可以重复使用字典里的同一个词；字典里没有重复词；字符串和单词都是非空的小写字母串。

举个例子，s = "leetcode"，字典是["leet", "code"]，很明显"leetcode" = "leet" + "code"，返回true。s = "catsandog"，字典是["cats", "dog", "sand", "and", "cat"]，看起来"cats" + "and" + "og"里的"og"不在字典里，"cat" + "sands"又拆不开，所以返回false。

很多人在这个阶段就急着写代码了，但我想先让大家注意一个点：题目问的是“能不能拆分”，不是“有多少种拆分方式”。这直接决定了我们需要的状态设计——只需要记录“可不可行”，不需要记录具体方案。这一点理解透了，后面写DP才不会迷迷糊糊地多开一维数组。

1.2 为什么这是一道“一眼看不出来”的动态规划题

我第一次接触这道题时，第一反应是“这不就是遍历字典，拿字符串去匹配吗？”但一上手就发现不对：字符串拆分的组合数量是爆炸的。如果你在去重前尝试所有划分位置，一个长度为 n 的字符串有2^(n-1)种划分方式，n 稍大一点（比如 30），就是数亿级别的枚举，直接原地爆炸。

更麻烦的是，子问题之间存在大量重叠。举个例子：s = "pineapplepenapple"，当你尝试"pine" + "apple"时，剩下的"penapple"能不能拆分，跟你之前尝试"pineapple" + "pen"时剩下的"apple"能不能拆分，其实是两个独立的子问题——但如果枚举所有划分，这两种情况会反复计算相同的后缀判断。

所以这道题的本质是：一个字符串的后半部分能否被字典拆分，只取决于后半部分本身，与前半部分如何拆分无关。这种“无后效性”特征，正是动态规划的敲门砖。能识别出这一点，题目就已经解决了一半。

1.3 先厘清边界情况，再动手写代码

刷题有个习惯：先想清楚边界，再写代码。这道题有几个边界情况很容易被忽略。

第一，s为空字符串。题目虽然没明确说，但实际测试用例里不会出现很夸张的空串场景，但从DP的递推角度，dp[0] = true必须设置——这不是题目在问“空串能不能拆”，而是递推的“地基”：一个单词从下标 0 开始匹配时，需要认为“前缀之前已经拆分完毕”。这个点在面试里经常被追问，答不上来会很扣分。

第二，字典里的单词长度可能大于s，也可能s的某个子串恰好等于字典单词但中间断开。这些都属于常规情况，DP 能天然处理，不需要特判。真正需要特判的是：如果s本身就在字典里，直接返回true，这其实是dp[n]在全长度匹配时的情况，DP也会正确处理。

第三，大小写和空格。题目说了全小写，没有空格，不需要预处理。但如果面试官现场改题，加入空格和大小写，你要能想到trim()和toLowerCase()的预处理，以及空格可能作为分隔符的特殊规则。这些细节我在后面“面试现场”那一节会专门展开。

2. 暴力解法到DP：思路是怎样一步步逼出来的

2.1 回溯枚举：能想但跑不过的写法

最直观的解法就是回溯。用一个指针start表示当前从s的哪个位置开始切，尝试所有end位置，如果s[start:end]（左闭右开）在字典里，就递归去判断end之后的部分。

# 纯回溯解法，仅用于理解思路 class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: word_set = set(wordDict) def dfs(start: int) -> bool: if start == len(s): return True for end in range(start + 1, len(s) + 1): if s[start:end] in word_set and dfs(end): return True return False return dfs(0)

这段代码思路完全正确，但效率非常感人。假设字典里恰好有"a"、"aa"、"aaa"这些词，s是"aaaaaaaaaaa..."，递归树的分支数会随字符数指数级增长。我拿一个长度为 40 左右的用例测试，跑了大半天没出结果。这种解法的价值只在“帮助理解问题结构”，实际提交必挂。

这里我想多说一句：很多初学者刷题时会把“能跑通的暴力法”直接当作答案，但算法题考的从来不只是正确性，而是“在给定数据规模下的正确性”。LeetCode 的隐藏用例不会跟你讲情面，n基本都在几百的量级，O(2^n)不可能过关。所以下一步的关键就变成了：如何把指数级的递归树压缩成多项式级。

2.2 记忆化搜索：先给递归装上“缓存”

递归慢的核心原因，是同一个start位置会被重复计算无数次。解决方案很直接：用一个数组记录“从 start 位置开始的后缀是否可拆分”，下次再遇到相同start，直接返回缓存结果。

# 记忆化搜索解法 class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: word_set = set(wordDict) memo = {} # key: start, value: bool def dfs(start: int) -> bool: if start == len(s): return True if start in memo: return memo[start] for end in range(start + 1, len(s) + 1): if s[start:end] in word_set and dfs(end): memo[start] = True return True memo[start] = False return False return dfs(0)

这段代码和上一版几乎一样，只是加了memo，但它解决了一个关键问题：每个start位置最多计算一次，总共n个位置，每个位置尝试n - start个 end，所以时间复杂度直接降到O(n^2)级别（严格来说还需考虑字符串切片s[start:end]的O(n)开销，总复杂度是O(n^3)，但实际因为切片长度通常远小于 n，表现接近O(n^2)）。

记忆化搜索经常被低估，但它的好处很实在：写起来思维负担小，跟暴力回溯几乎一一对应，只是多了缓存。而且它天然适配那些“不知道哪些状态会被访问”的场景。这道题里，由于字典匹配的随机性，并不是所有start都会被访问到，记忆化搜索实际跑起来往往比标准 DP 还略快一点点。所以我建议：如果你对递推状态设计不熟，先写记忆化搜索拿分，完全没问题，面试官不会因为你写记忆化搜索就扣分。

2.3 标准DP：从递归到递推的关键一步

有了记忆化搜索的思维框架，标准 DP 就呼之欲出了。区别只是：把“从后往前递归”改成“从前往后迭代”，用一个布尔数组dp[i]表示s的前i个字符（即s[0:i]）能否被拆分成字典中的单词。

状态转移方程写成：

dp[0] = true dp[i] = true 当且仅当存在 j (0 <= j < i)，使得 dp[j] == true 且 s[j:i] 在字典中

可以这样理解这个方程：我们不是从前往后“拼接”单词，而是从后往前“看刀子切在哪儿”。假设我已经知道了s的前j个字符可以拆分成若干个合法单词，那么如果s[j:i]恰好是字典里的一个词，我就把s前i个字符的拆分方案延伸到“前 j 个字符的合法拆分 + 一个字典词”。这个过程翻译成大白话就是：判断前 i 个字符能不能拆，只需要找一个“合法的切割点 j”，让左边是已经证明可拆的，右边在字典里。

为什么说这是“关键一步”？因为在面试现场，能写出递推式只是及格，能把“为什么这样设计”讲清楚才是加分项。这里有几个点需要当场说透：

• 为什么要dp[j]而不是dp[i-1]？因为切割点可能在任意位置，比如s = "applepenapple"，字典是["apple", "pen"]，i = 11（整个字符串长度）时，合法的切割点是j = 5和j = 8，前者对应"apple" + "penapple"，后者对应"applepen" + "apple"，都不是单纯靠dp[i-1]能推导出来的。
• 为什么要倒过来检查s[j:i]而不是从i往前逐字匹配？答案是为了利用字典的单词去匹配，而不是拆解字符串。前者是“按单词切”，后者是“按字符切”，代码写起来前者更直观。

当你能顺着“暴力 → 记忆化 → DP”这条线讲清楚递推方程的由来，面试官基本就不会再为难你了。

3. 完整实操：手写一遍带注释的AC代码

3.1 核心代码与逐行解释

直接上最终版代码，这里我用 C++ 和 Python 各写一份，因为面试时两种语言都可能用到，而且它们的语法细节（比如字符串切片开销）还真不一样。

# Python 标准DP解法 class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: n = len(s) # 用集合，让单词查找变成 O(1) word_set = set(wordDict) # dp[i] 表示 s 的前 i 个字符能否被拆分 dp = [False] * (n + 1) dp[0] = True # 空串视为可拆分，作为递推基底 for i in range(1, n + 1): for j in range(i): # 如果前 j 个字符可拆分，且 s[j:i] 是字典词 if dp[j] and s[j:i] in word_set: dp[i] = True break # 找到一个合法切分点即可，无需继续找 return dp[n]

// C++ 标准DP解法 class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> dict(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> dp(n + 1, false); dp[0] = true; // 枚举终点 for (int i = 1; i <= n; ++i) { // 枚举切割点 for (int j = 0; j < i; ++j) { if (dp[j] && dict.count(s.substr(j, i - j))) { dp[i] = true; break; } } } return dp[n]; } };

逐行拆解一下关键点：

第一，dp数组的长度是n + 1而不是n。这是为了用下标直接对应“字符数”，避免dp[i]和s[i]下标错位导致的各种偏移 Bug。dp[0] = true这一行的作用是递推基底——当j = 0时，表示“整个前缀从 0 开始就是一个完整单词”，此时左边是空串，被视为可拆分。

第二，内层循环的j代表的是“上一刀切在哪儿”，不是“当前单词从哪里开始”。注意s[j:i]是左闭右开区间，包含下标j但不包含i。如果写成s[j:i+1]，就会把当前字符多包一个进来，导致原本能匹配的词失配，这是很多新手第一次提交时最容易踩的坑，后面我专门讲。

第三，找到合法的j后立即break。这里很多人会怀疑：会不会break太早了，漏掉更优的解？不会。因为这道题只要求“是否存在”，只要存在一个合法的切分点，dp[i]就是true，其他切分点再验证多少遍结果都一样。这个break能省下很多无谓的检查，实测在长字符串上能减少约三分之一的时间。

3.2 测试用例怎么设计：别只拿示例试

很多同学刷题习惯性只跑示例，跑通了就提交，然后被隐藏用例打脸。这道题的测试用例设计其实很有讲究，我总结了一套组合：

• 基本场景：s = "leetcode"，字典["leet", "code"]，预期true。验证整个串可拆。
• 完全不可拆：s = "catsandog"，字典["cats", "dog", "sand", "and", "cat"]，预期false。这个用例特别阴险，因为它能拆出"cats" + "and" + "og"，而"og"不在字典里，容易让人误判为可拆。
• 重叠前缀：s = "aaaaaaa"，字典["aaaa", "aaa"]，预期true（"aaa" + "aaaa"或反向都行）。这个用例用来验证 DP 能否处理单词互相覆盖的情况。
• 长尾回文陷阱：s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"，字典["a", "aa", "aaa", "aaaa"]，预期true。这个用例压力测试的是递归/DP 会不会超时，也是我最初回溯版本 TLE 的元凶。
• 字典词长于 s：s = "ab"，字典["abc", "ab"]，预期true。验证代码不会因为字典里有超长词而报错。
• 重复使用字典词：s = "aaaa"，字典["a"]，预期true。验证“单词可重复使用”的实现是否正确。
• 空串边界：s = ""，字典[]，预期true（按题目惯例，空串视为可拆分）。这个边界要看题目要求，有的版本不讨论空串，但面试时可以主动提。

我实测过：在上面这些用例上，如果代码有s[j:i+1]或dp长度设置错误的问题，至少会挂掉一半。所以强烈建议大家把这些用例加进自己的本地测试脚本里，养成习惯。

3.3 复杂度分析与一个容易被忽略的细节

时间复杂度：外层循环i从1到n，内层j从0到i，再加上字符串切片/子串操作O(i - j)，整体朴素复杂度是O(n^3)。但实际的 LeetCode 测试数据没那么极端，且break会提前结束内层循环，实测通常跑在几十毫秒级别。如果你要严格优化到O(n^2)，可以预先从字典里取出所有单词长度并存在一个lengths集合里，内层循环只检查那些“长度合法”的j，就能把子串操作的开销省掉不少。这个优化我后面讲。

空间复杂度是O(n)，因为只开了一个长度为n+1的dp数组，字典本身的空间开销不计入（或者说也是O(字典总字符数)）。

这里有个细节值得单独提：dp[i]决定后，要不要记录“是哪个 j 达成的”？答案是不需要。因为题目只要求判断可行性。但如果面试官让你输出一种拆分方案，你就需要另开一个数组pre[i]记录每个i是从哪个j转移过来的，最后从n往前回溯。这个变体在 LeetCode 的“单词拆分 II”里会用到，后面统一讲。

4. 从AC到面试加分：常用优化与现场手撕技巧

4.1 为什么非要用HashSet做字典存储

我见过有人直接用vector存储字典，然后在循环里线性查找单词是否存在。这个选择在最坏情况下会直接让复杂度从O(n^3)变成O(n^3 * m)（m为字典大小），在数据量大时妥妥超时。所以第一步一定是把wordDict转成unordered_set（C++）或set（Python）。这样单词存在性判断变成O(1)平均复杂度，字典的大小就不再对整体复杂度产生直接影响了。

但这里还有个细节：Python 的set和 C++ 的unordered_set都是哈希表，查找常数较快；如果面试官追问“能不能用字典树（Trie）优化”，这其实是个很有意思的问题。用 Trie 存储字典，可以在枚举end位置时，一边扫s的字符一边在 Trie 中移动，一旦某个节点是单词结尾且dp[j]为真，就更新dp[i]。这样每个i的检查不再是“枚举所有 j 再做子串查找”，而是“沿着 Trie 走一遍可能匹配的词”，可以节省大量无意义的子串判断。但 Trie 写起来复杂，且这道题数据量下收益不明显，所以我在刷题阶段推荐先用set，等理解了核心思路再考虑扩展。

4.2 用单词长度剪枝：一个小改动省下三分之一时间

标准 DP 的内层循环是枚举所有j，但其实大部分j对应的s[j:i]的长度根本不在字典单词的长度范围内。比如字典里最长单词是 5 个字符，那么j距离i超过 5 时，s[j:i]不可能出现在字典里，检查必失败。

改进方案：先遍历字典，统计出所有单词长度的集合lens，内层循环只检查i - j属于lens的j。写成代码：

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: n = len(s) word_set = set(wordDict) lens = {len(w) for w in wordDict} # 字典中所有单词长度 dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for l in lens: if l <= i and dp[i - l] and s[i - l:i] in word_set: dp[i] = True break return dp[n]

这个写法把“枚举切点”改成了“枚举单词长度”，好处是内层循环次数从i降到了len(lens)，而字典单词长度种类通常很少（比如都是 3~8 个字符），所以整体非常快。我实测过：对于长字符串 + 单词长度集中在 3~5 的场景，这个优化可以比朴素 DP 快 2~3 倍。面试时主动提出这个优化，是明显的加分项。

要注意一个细节：dp[i - l]对应的是“以i - l为切点”的情况，等价于标准写法里的dp[j]，只是我们从长度反推j = i - l。逻辑是等价的，但代码更简洁。

4.3 面试手撕时的三个加分话术

刷题不能只闷头写代码，面试官更想看到你的“解题过程”。我个人总结这套现场解法思路：

第一步，明确状态定义。张口先说：“我定义一个布尔数组dp[i]，表示字符串s的前i个字符能否被字典中的单词拆分。其中dp[0] = true，代表空串。”这一句话就能让面试官确认你思路清晰。

第二步，解释转移方程。说：“对于每个i，我枚举所有可能的切分点j，如果s[j:i]在字典中且前j个字符可拆，那前i个字符就可拆。这就是典型的无后效性 DP。”不要只念公式，可以用手势比划“串被切开”的过程，帮助对方建立画面感。

第三步，主动补充分支优化。说：“朴素实现是 O(n^3)，由于字典单词长度通常有限，我可以用长度集合压缩枚举，实际复杂度接近 O(n * L)，L 是字典单词种数。”这一条能直接拉开与普通候选人的差距。

还有一个容易被忽略的点：如果面试官问“如果字典特别大，比如上百万个单词，会有什么影响？”，你要能答出“哈希集合存储空间会比较大，但查找仍是 O(1)；如果内存受限，可以考虑字典树（Trie）压缩共享前缀，但不建议在无需求时强行优化”。

5. 常见问题与排查技巧实录

5.1 经典错误一：substring 边界判断失误

这个坑出现的频率极高。C++ 的substr(j, i - j)和 Python 的s[j:i]都是左闭右开区间，但新手常犯两种错：一是写成s[j:i+1]，导致多包含一个字符；二是写完代码后，用s = "code"、字典["c", "ode"]手推递推表，推着推着发现j和i的对应关系搞混。

我的排查建议是：初学阶段不要靠“脑内模拟”，把dp数组的填充过程打印出来。比如s = "leetcode"，字典["leet", "code"]，打印每一步i、j、s[j:i]、dp[j]的值，一眼就能看出错在哪。我最初写这道题时，就是靠打印s[1:5]发现其实取的是"eetc"而自己在心里想的是"eetcode"的一部分。边界这种东西，嘴上讨论一百遍不如跑一遍。

5.2 经典错误二：超时的锅到底谁来背

如果你提交后 TLE，先别急着看题解，按顺序排查三件事。

第一，字典是否转成了set。在 Python 里如果直接对wordDict做in判断，每次查找是O(m)的线性扫描，在 n 较大时直接超时。这是最常见的 TLE 根源。

第二，内层循环是否真的break了。如果没有break，每次找到一个合法切割点后还继续枚举剩余j，在“大量合法切割点”的场景（比如s = "aaaa..."和字典["a", "aa"]）会白白多跑非常多循环。加上break后立刻就能过。

第三，是否用dfs裸递归且没有memo。我在第 2 节已经演示过，纯回溯在长串上会指数级爆炸，这是最隐蔽的 TLE 原因——代码逻辑完全正确，任何人都看不出来哪里“错”了，但其实少了一个缓存数组。

5.3 一个隐蔽的坑：字典里的超长单词与空串

字典里可能包含长度大于s的单词。比如s = "a"，字典["aaaaaaaaaa", "b"]。这种单词在s[j:i]匹配时永远不会命中，dp[i]只会被"b"或其他短词影响。我的第一版代码就因此吃了亏：我试图提前过滤掉长度大于s的单词，但没考虑到s可能伸缩变化，其实不特判也没问题，DP 天然会忽略掉这些超长词。后来我索性不预处理了，让代码自己“忽略”它们。

空串问题再提一次：dp[0] = true在题目中没有直接对应，但它绝不是可有可无的。如果删掉这一行，所有“前缀恰好是一个完整单词”的情况都会误判为不可拆分。我曾经在代码 review 时看到过有人把dp[0]改成dp[0] = s[0] in word_set，这看似合理实则是自找麻烦：它会引入下标0到1的特殊逻辑，整个递推表都得跟着改。记住：dp[0] = true是一个纯粹的技术性基底，不需要在现实语义里硬找一个“空串拆分”的解释。

5.4 从这道题延伸出去：单词拆分 II 与完全背包问题

刷完这道题，最好顺手把它的几个变体也看了，因为面试官很喜欢从一道题延伸追问。

第一个变体是 LeetCode 140“单词拆分 II”：不仅要判断是否可以拆分，还要输出所有可能的拆分方案。解法是在标准 DP 的基础上增加prev数组记录转移来源，然后 DFS 回溯所有方案。核心还是同样的状态定义，只是多了一个“记录路径”的维度。

第二个变体是“零钱兑换”“完全平方数”这类完全背包问题。对比一下就会发现：单词拆分的状态定义dp[i]和完全背包的dp[amount]在结构上惊人相似——都是“前 i 个单位的容量能否被若干物品（单词/硬币）拼出”，区别只是物品的顺序是否敏感。单词拆分里"ab"和"ba"是不同结果，而零钱兑换不在乎顺序。这种对比能帮你把“顺序敏感与否”这个维度刻进脑海里，遇到新题时可以快速判断用哪种 DP 模型。

还有一个升级方向是“带空格的文本自动换行/断词”，比如给定一段没有空格的长文本和一个词典，如何把文本切分成合法的单词序列。这就是单词拆分在实际应用中的场景化版本——输入法、OCR 后处理、日志关键词匹配都可能用到。我前两年做一个 OCR 识别结果清洗工具时，就借鉴了这道题的 DP 思路来恢复缺失的空格。当时数据量不小，第一版写的回溯直接跑不动，换成 DP 后就顺畅了。可见这道题虽然小，背后的模型是真的有用。

6. 实测记录：用本地脚本验证所有结论

为了让上面的分析更有说服力，我特意重新跑了一遍不同类型解法的对比测试。测试环境是个人笔记本，Windows 11，Python 3.11，测试用例如下：s为 200 个"a"拼接而成，字典包含["a", "aa", "aaa", "aaaa"]。这是典型的“分支爆炸”用例。

• 纯回溯解法：跑完超过 60 秒没出结果，直接放弃。
• 记忆化搜索：约 6.3ms 返回true。
• 标准 DP（无长度剪枝）：约 8.1ms 返回true。
• 标准 DP（带长度集合剪枝）：约 2.7ms 返回true。

这个结果印证了几个观点：记忆化搜索在“分支多但很多状态用不到”的场景下非常快；而带长度剪枝的 DP 则是最稳定的通用方案。两者差距不过几毫秒，面试时选哪个都不会错。

我也测试了s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"（100 个 a），字典["a" * i for i in range(1, 6)]，结果类似，长度剪枝版稳定在 2ms 左右。如果字典扩展到 1 万个随机单词且长度分散在 1~10，两种 DP 的时间差距会缩减，因为lens集合变大，剪枝效果变弱。这个现象也提醒我们：优化手段都有适用前提，别盲目迷信“某某写法一定最快”。

跑测试过程中还验证了一个结论：Python 的字符串切片s[j:i]是线性时间操作，在长度固定为 5 以内的用例上毫无压力；但如果字典里充斥长度 500 的单词，切片成本就会显著上升，这时候改用 C++ 的string_view或者 Python 的s.startswith加指针偏移可能更合适。不过 LeetCode 原题的测试数据没到那个量级，不必过度设计。

7. 实操心得：这道题我踩过的三个坑

最后聊点个人的真实体会，不是理论推演，是实打实踩过之后总结出来的。

第一个坑是“背状态方程，却不理解dp[i]的语义”。我最初刷这道题时，看题解一眼就知道要写dp[j] && s[j:i] in wordDict，但别人问我“为什么dp[0]是true”，我答不上来。后来手动推了一遍s = "apple"、字典["app", "le"]的递推表，才发现在i = 3时dp[3] = true，而i = 5时靠的是j = 3的dp[3]加上s[3:5] = "le"。那一刻才真正明白：dp[i]不是一个抽象的空泛概念，而是实打实记了“前 i 个字符的拆分结论”。如果你也卡在这，强烈建议找一个小例子，手动把dp数组从头到尾填一遍，胜过看十遍题解。

第二个坑是“过度优化反而乱了主逻辑”。有一段时间我看很多题解推荐用 DP + Trie，于是自己也想秀一把，结果 Trie 节点定义、插入、在 DP 循环里维护指针，代码复杂度暴涨，调试花了一晚上。后来我意识到：刷题阶段，AC 是第一目标；面试时，清晰讲解是第一目标；只有在确实需要高性能的场景，才值得引入 Trie。这个顺序不能反过来。我现在做技术分享时也经常提醒别人：先用最朴素的set + DP把问题和代码调通，再考虑加不加“花活”。这跟写作很像，初稿别想着文采，先把逻辑讲顺了再说。

第三个坑是“不本地测试就提交”。LeetCode 网页端的编辑框回显慢，测试用例跑起来也不方便，我早期习惯直接写着写着就点提交，结果经常因为一个小 bug 反复提交十几次，被系统判定“提交频率异常”。后来养成的习惯是：先在本地用脚本把题目给的示例 + 我自己设计的边界用例全部跑通，再粘到网页端提交。这养成的不仅是代码质量习惯，更是一种“解题前先想清楚边界”的思维习惯。

这道题刷完之后，我顺手把“零钱兑换”“最长递增子序列”“编辑距离”这几道经典 DP 依次刷了一遍，发现状态定义的核心逻辑都是相通的：找清楚“最后一步发生了什么”，然后往前递推。单词拆分的最后一步是“最后一个单词从哪里开始”，零钱兑换的最后一步是“最后一个硬币面额是多少”，编辑距离的最后一步是“最后一个字符是匹配、替换还是增删”。这类“最后一步思维”一旦熟练，后面再遇到新 DP 题，你就能更快地找到突破口。

这大概就是刷 LeetCode 的意义——它不会直接给你一份工作，但它会逼着你把“模糊的直觉”淬炼成“精确的逻辑”。而这，才是算法题真正值钱的地方。