动态规划详解：LeetCode 139 单词拆分题解与优化

1. 先从题目本身聊起：输入、输出与约束条件

刷过一段 LeetCode 的人，基本都会在动态规划专题里撞见这道leetcode139 单词拆分。题目本身并不长：给你一个字符串s和一个单词字典wordDict，请判断s能不能被拆分成一个或多个字典中出现的单词，并且字典中的单词可以重复使用。比如s = "leetcode"，wordDict = ["leet", "code"]，答案是true，因为s可以拆成leet+code；再比如s = "applepenapple"，wordDict = ["apple", "pen"]，同样返回true，因为apple出现了两次，字典里的词本来就是可以复用的。

这道题在面试里出现频率相当高，尤其是大厂笔试和算法电面。它表面上是字符串处理，内核却是非常典型的动态规划状态设计题，同时还会牵扯到递归、记忆化搜索、哈希表优化甚至前缀树这些知识点。适合的读者也很明确：准备面试的工程师、刚开始刷动态规划的新手，以及想把这题迁移到其他拆分/拼接类问题的同学。把它吃透，后面再遇到“拼接字符串”“凑单词”“能否组成目标串”这类问题，你会觉得思路都是通的。

1.1 题目到底在问什么

很多人在第一眼看到这题时，会下意识把它当成简单的包含关系判断。比如判断s是否包含wordDict里的某个单词，或者s能否由某些单词的子串拼接出来。但题目真正要求的，是对整个字符串做一次完整分割，分割后的每一段都必须完整出现在词典里。注意措辞：“拆分”不是“匹配到就算数”，从开头到结尾必须被覆盖干净。

举个例子你就明白了。s = "catsandog"，wordDict = ["cats", "dog", "sand", "and", "cat"]。这里cat、cats、sand、and、dog都在字典里，s也确实包含这些词，但不管怎么切，总有一块接不上：你可以切cat+sand+og，但og不在字典里；也可以切cats+and+og，结果一样卡在og上；直接切cats+dog，中间的andog显然没法切。所以最终答案是false。这个例子特别适合拿来检验：你写的算法是真的在“从头到尾拆串”，还是仅仅在“找包含关系”。

题目还有个很容易忽略的细节：wordDict是一个列表，不是去重后的集合，但实际使用中应该先转成哈希集合，因为字典中可能包含重复单词。重复不会影响结果，却会拖慢查询速度。另外，字典里的单词可以被无限次使用，这意味着这不是一个“每个单词只能用一次”的匹配问题，而更像一个完全背包中的“物品可重复取”模型。

1.2 两个最容易忽略的细节

第一个细节是空字符串。LeetCode 原题一般给s.length >= 1，但如果你要自己写测试用例，或者面试官追问边界情况，应该想一想s = ""应该返回什么。按照动态规划里dp[0] = true的定义，空串可以视为已经拆分完成，不需要任何单词组合，所以答案是true。这个约定不是拍脑袋定的，它是状态转移的基石，后面你会看到所有递推都从dp[0]出发。

第二个细节是子串长度的控制。用dp[i]表示前i个字符是否可拆分时，状态转移要枚举分界点j，然后判断s[j:i]是否在字典中。这里的j必须从0遍历到i-1，而不是只挑几个看起来像单词边界的位置。因为字典里的单词长度不固定，你无法预判哪个位置能切开。即使你提前知道字典里最长的单词长度是maxLen，也只敢在i - maxLen到i这个范围内枚举，否则就可能漏掉一种拆分方式。

2. 暴力回溯为什么跑不动

看到“拆分成单词”这类描述，很多人第一反应是递归。从下标0出发，每次尝试匹配一段子串，匹配成功就从下一位置继续递归，直到指针走到字符串末尾。这套思路本身没毛病，但它会踩中一个非常经典的性能陷阱：重叠子问题。

2.1 第一直觉的递归拆法

来写个伪代码感受一下。定义一个递归函数dfs(start)，表示当前要拆s[start:]这一段。函数里从end = start + 1开始，一直试到s.length，只要s[start:end]在字典里，并且dfs(end)返回true，那整个函数就返回true。如果所有尝试都失败，返回false。

用刚才的catsandog去跑，你会发现它在一路尝试：先试cat，然后递归处理sandog；在sandog里试sand，然后处理og；处理og时发现o、og都不在字典里，于是返回false；再回溯到sandog的下一刀，试sandog本身，发现不在字典里，返回false；再回溯到第一层，试cats，递归处理andog……这条路非常直观，但效率极低。

表面上的问题是枚举所有切割点，本质上的问题是同一个子串会被反复计算。还是拿这个例子，切cat+sand+ 后续，和切cats+and+ 后续，两条不同路径最后都可能需要判断og或og附近剩余部分能不能拆。这些判断每次都重新递归一遍，完全没有复用之前的结果。

2.2 重叠子问题的定量分析

我们可以把递归树画出来：根节点是dfs(0)，每一条边代表从某个位置切出一个字典单词。假设s很长，而字典里恰好有大量短单词可以组合出它，比如s = "aaaaab"，字典是["a", "aa", "aaa", "aaaa"]，那么dfs(1)可能出现很多次：你可以在位置0切一个"a"到dfs(1)，也可以在位置0切一个"aa"到dfs(2)，然后从dfs(2)内部再切一个"a"又回到dfs(1)？严格说这里各路径到达dfs(1)的方式不同，但数值上确实会多次重复调用同一个位置。

最坏情况下，每个位置都有多个单词可以匹配，那么递归分支数是指数级的，理论复杂度可以达到O(n * 2^n)左右。凡是碰到指数级递归，第一反应就应该是：“有没有重复计算？能不能缓存？”这也是动态规划题目的典型信号。如果面试时你先写了个回溯，面试官多半会追问一句“时间复杂度多少”“能不能优化”，这时候顺势引入记忆化搜索或动态规划，反而能展现出你分析问题的能力。

3. 动态规划才是这题的常规解

暴力递归慢是因为不知道“哪些子问题已经算过了”。动态规划的思路很简单：把“前i个字符能否被完整拆分”这个问题的答案，按顺序从小往大算，存进数组里，后面直接查表。

3.1 状态定义与转移方程

定义dp[i]为布尔值，表示字符串s的前i个字符（即s[0:i]）能否被拆分成字典中的单词。初始化dp[0] = true，因为空串天然满足“拆分完成”。接下来枚举 i 从 1 到 n，每个 i 都在内部枚举分界点 j 从 0 到 i-1。

转移条件有两个，缺一不可：

1. dp[j]必须为true，说明s[0:j]已经能拆干净；
2. s[j:i]必须是一个完整出现在字典里的单词。

两个条件同时成立，就可以把dp[i]置为true，然后立即跳出内层循环，因为只需要知道“能否拆分”，不需要统计有多少种拆分方式。

这个状态定义很像“跳台阶”问题：dp[i]能否为真，取决于是否存在一个合法的“落脚点”j，从j到i恰好是一个词典单词。说白了，我们在检查字符串是否能被若干词典单词头尾相接铺满。

3.2 完整代码与复杂度

直接给出一个常见、好读的 Python 实现：

def wordBreak(s: str, wordDict: list[str]) -> bool: n = len(s) word_set = set(wordDict) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[n]

再给一个 Java 版本，方便对比：

class Solution { public boolean wordBreak(String s, List<String> wordDict) { int n = s.length(); Set<String> wordSet = new HashSet<>(wordDict); boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; } }

这里我把wordDict转成了哈希集合，这是非常重要的一步。如果不转，每次s[j:i] in wordDict都是对列表做线性扫描，整体复杂度会再乘上一个m（字典长度），在字典特别大的时候会非常难受。转换成哈希集合后，单次查询是O(1)。

至于复杂度，外层循环跑n次，内层循环平均跑i次，所以总共会产生O(n^2)对(j, i)候选；每一对候选都要从字符串中截取一段s[j:i]，截取本身需要O(i-j)的时间，所以最坏情况是O(n^3)。不过在实际刷题时，很多人习惯把它说成O(n^2)，因为当单词长度不大、且命中后立即break，实际跑起来很快。如果你想要一份更严谨的表达，可以说：时间复杂度取决于字符串长度和词典中最大单词长度，理论上界是O(n^3)，但通过长度剪枝可以显著压低。

3.3 一个小优化：限制单词长度

既然内层循环每次都要从j = 0扫到j = i-1，那在字符串很长、字典单词普遍很短时，这其实做了很多无用功。一个非常实用的优化是：先统计wordDict里最长单词的长度max_len，内层循环不再从0开始，而是从i - max_len开始。因为s[j:i]的长度如果已经超过了字典里最长单词的长度，它肯定不可能出现在字典里，没必要检查。

def wordBreak(s: str, wordDict: list[str]) -> bool: n = len(s) word_set = set(wordDict) max_len = max(len(w) for w in wordDict) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): start = max(0, i - max_len) for j in range(start, i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[n]

不要小看这个改动。当s长度是 1000，而字典里最长的单词只有 10 个字符时，内层循环从平均 500 次降到最多 10 次，整体速度快了 50 倍。我在本地用长字符串压过，长度剪枝版本几乎没有任何卡顿。面试时主动加这一步，是很强的加分项，因为它体现的不是“背题”，而是真的理解瓶颈在哪。

4. 从递归到记忆化：三条代码路径的现场对比

动态规划不是唯一能把指数级递归救回来的方法。另一种常见手段是记忆化搜索，也就是在递归函数里加一个缓存。理解这两种写法的区别，能让你在面试时不至于被追问“为什么不用 DFS”就卡壳。

4.1 记忆化搜索的实现

递归函数的定义可以改成：dfs(i)表示s[i:]这一段能否被拆分。注意，这和前面dp[i]的定义方向相反：dp[i]看的是前缀，dfs(i)看的是后缀。但本质上都在描述同一个子问题。

代码如下：

def wordBreak(s: str, wordDict: list[str]) -> bool: word_set = set(wordDict) n = len(s) memo = [-1] * n # -1 表示未计算，0 表示不可拆，1 表示可拆 def dfs(i: int) -> bool: if i == n: return True if memo[i] != -1: return memo[i] == 1 for end in range(i + 1, n + 1): if s[i:end] in word_set and dfs(end): memo[i] = 1 return True memo[i] = 0 return False return dfs(0)

这段逻辑和纯回溯一模一样，唯一区别是每次算完memo[i]，下次再碰到同样的i直接返回结果，不再重复展开递归树。它和动态规划是等价的，只是计算顺序不同：动态规划是自底向上，记忆化搜索是自顶向下。如果你对递推方向容易搞混，可以先写记忆化版本，它更贴近人的直觉。

注意：这里memo数组在用memo[i] = 1和memo[i] = 0时，一定把“未计算”和“不可拆”区分开。如果只用True/False做缓存，很容易把第一次算出的False当成“还没算”，导致重复计算。

4.2 三种解法的横向对比

为了让你看得更清楚，我把三种写法放在一起对比：

刷题时我个人的习惯是：先想状态定义，再想转移方程，然后直接写动态规划。但如果你在紧张的状态下一时半会想不出dp怎么写，记忆化搜索是完全可接受的保底方案。面试官更看重的是你能不能给出“从暴力到优化”的演进过程，而不是直接默写一个最优解。

关于空间复杂度，动态规划和记忆化搜索都要存长度为n+1的状态，所以都是O(n)。唯一的额外开销是记忆化搜索需要递归栈，最坏情况下递归深度能达到n层，虽然 LeetCode 这题的s长度一般不大，但如果在极端评测环境里，递归层数很深的题还是要优先选非递归的动态规划。

5. 进阶：四个高频变体与考点延伸

5.1 输出所有拆分方案

leetcode139只要求返回true/false，但如果面试官让你“给出所有可能的拆分方案”，那就是另一道经典题了。最简单的方式是先跑一遍动态规划，拿到dp数组，然后从后往前回溯拼接。

我写过一个参考思路：先用wordBreak的dp确定哪些分割点可行，再写一个backtrack(start, path)，从start开始尝试所有end，只要dp[end]为真且s[start:end]在字典里，就把这段加入路径，递归处理end。当start到达字符串末尾时，把path保存下来。

这个方法能大幅剪枝，因为只会在“前缀可拆分”的正确分割点上展开，不会像纯回溯那样把整棵错误分支都遍历一遍。如果你在面试中能主动说出“先用 dp 做可行性剪枝，再回溯收集方案”，这比裸写一个 DFS 要高级得多。

5.2 单词拆分与完全背包的统一视角

这题换个角度看其实是个完全背包问题：s是背包容量，字典里的单词是物品，单词可以无限次使用，目标不是让价值最大，而是判断能不能恰好填满。状态dp[i]表示容量i能否完全由物品拼出，转移时枚举最后一个放入的物品（单词），这个思路和经典的“凑零钱”问题一脉相承。

我之所以强调这个统一视角，是因为面试时问题经常不会只考原题。比如改成“给定一个字符串和单词列表，判断能否拆分成单词且拆分次数最少”“能否用这些单词拼接成目标串，每个单词最多用一次”，这些题的核心状态都是类似的dp[i]，只是转移条件、使用次数限制稍有变化。把139吃透，等于给这一类题都打了底。

5.3 大词典场景下用 Trie 进一步提速

当wordDict非常大，或者单词长度参差不齐时，哈希集合已经够用，但如果要追求极致性能，可以用前缀树（Trie）。具体做法是：把字典中所有单词插入 Trie，s[j:i]是否在字典中，等价于从 Trie 根节点开始沿着字符往下走能不能走到一个单词结束标记。

换用 Trie 的好处是，判断子串时不用每次在原字符串上截取，而是一边走一边检查前缀，一旦发现某个前缀在 Trie 中不存在，就可以提前终止。这个优化在处理长串和长词典时尤其明显。代价是实现代码变长，面试时间紧张时不建议主动引入，除非面试官明确问“能不能优化到更快”。

5.4 其他变体：返回方案数

还有一个常见变体是“返回拆分方案总数”，比如s = "leetcode"，字典里有["leet", "code", "leetcode"]，方案数应该是 2：一种是leet + code，一种是leetcode整体。这个题把布尔dp改成整数dp，dp[i]表示前i个字符的拆分方案数，转移时把所有满足条件的dp[j]累加即可。

需要注意，方案数可能非常大，题目如果没说明取模，要用 Python 的整数不用担心溢出，但在 Java/C++ 里可能要考虑long或者取模。这已经属于139的延伸讨论了，但是在面试中遇到变体题时非常有用。

6. 面试与实战中的常见坑和排查思路

6.1 五个高频 bug

bug 1：忘记初始化dp[0] = true。这是最经典的失误。没有dp[0]，所有转移都从空集出发，结果大概率是false。面试时写完代码，一定要用s = "a", wordDict = ["a"]这种最小用例手动走一遍，确认dp[1]能正确变成true。

bug 2：break位置写错。内层循环一旦找到一个合法分界点，就应该立刻置dp[i] = true并跳出。有些人会把break写在if dp[j]这个外层判断里，导致没有检查s[j:i]是否在字典中就提前结束，整个逻辑就废了。

bug 3：忘记把wordDict转成哈希集合。如果直接用列表做包含判断，虽然结果没错，但复杂度从O(n^3)直接飙升到O(n^3 * m)。在 LeetCode 上表现就是超时，而且很难排查。写完代码第一件事，看看你的查询对象是不是集合。

bug 4：下标和切片区间对不上。dp数组长度是n+1，dp[i]对应s的前i个字符，所以s[j:i]的j、i都是下标端点，而不是“第几个字符”。很多人在手动模拟s = "abcd"时，会把dp[2]误解成"bc"可拆分，实际它对应的是"ab"。一定要在脑内把“前 i 个字符”这个定义钉死。

bug 5：忽视重复点击的边界。优化长度剪枝时，start = max(0, i - max_len)，这个max(0, ...)非常关键。如果i本身小于max_len，i - max_len会变成负数，Python 切片负数不会立刻报错，但会从尾部开始取，结果完全错误。别问我怎么知道的，这种坑一旦踩过就再也不会忘。

6.2 性能排查与优化清单

如果你写完动态规划还是超时，别急着怀疑编译器，按这个顺序排查：

• 第一，wordDict是否已转哈希集合；
• 第二，内层循环是否做了大量无效截取；
• 第三，是否能用最大单词长度剪枝；
• 第四，dp[i]是否提前break；
• 第五，极端情况下考虑 Trie 替代哈希集合。

我实测过一个案例：s长度 200，wordDict有 500 个单词，不做任何优化时，哈希集合版本大约几毫秒；如果误用了列表，直接卡到几秒甚至更久。别小看这些常量的差异，LeetCode 的评测数据往往就是卡着极限来的。

6.3 面试时推荐的讲述节奏

面试中遇到这题，不要上来就写代码。先和面试官确认三件事：s可以为空吗？wordDict里允许重复吗？返回只需要布尔值还是需要方案？确认完再讲思路。

我建议的讲述顺序是：第一，说清楚状态dp[i]的定义；第二，写出转移方程“dp[i]为真，当且仅当存在j使dp[j]为真且s[j:i]在字典中”；第三，解释为什么dp[0] = true；第四，用一个小的例子手动推一遍；最后再写代码。这样面试官能跟着你的思路走，而不是看着你闷头写。写完代码后，主动补一句“这里可以把字典转成哈希集合，还可以用最大单词长度剪枝”，基本就把这道题吃透了。

就我个人刷题经验来说，这题真正的价值不在于你背下了dp写法，而在于你理解了“子串拼接覆盖”这类问题的共性：先划分阶段、定义状态，再想转移条件。把这套思维方式练熟，后面再遇到其他拆分题，你甚至不需要犹豫就能直接写出状态数组。如果时间充裕，我建议你把这题的三种写法都本地跑一遍，感受一下指数级回调和动态规划的差距，这种体感比看一百篇题解都深刻。