平时刷力扣，很多人一看到字符串题就条件反射想用双指针或者回溯，但遇到"单词拆分"这种题，往往会卡在"我到底该先切哪一刀"的思路上出不来。这题在力扣100热题里排第86，题号是139，属于非常典型的动态规划入门题，看起来只是判断一个字符串能不能被字典里的词拼出来，实际上背后藏着一套很经典的线性DP模型。今天就把这道题的整个拆解过程、状态转移推导、代码实现和容易踩的坑一次性说清楚，哪怕你之前没怎么碰过DP，跟着走一遍也能自己写出来。
为什么专门写这篇？因为网上很多题解上来就甩一个dp数组，告诉你 dp[i] = dp[j] and s[j:i] in wordDict，然后直接贴代码，完全没解释这个式子是从哪冒出来的。我当初刷这题也是看了好几篇才真正理解，后来还把这道题的思路用到了实际的分词和敏感词匹配项目里。这篇文章不适合已经能闭眼写出状态转移的人，更适合那些"看得懂题解、合上书就忘"的同学。我会把每一层思考都摆在台面上，顺便讲讲我在洛谷、周赛里遇到的类似DP题和真实工程里的应用，让你不仅会写这题，还能把模型迁移走。
1. 题目拆解：单词拆分到底在考什么
1.1 先看题目描述
这题的原题是这样：给你一个字符串s和一个字符串列表wordDict，判断s是否可以由wordDict中的单词拼接而成。注意，字典里的单词可以重复使用，且不要求全部用完。
我先拿个具体例子过一遍。比如s = "leetcode"，wordDict = ["leet", "code"]，显然"leet" + "code"就是"leetcode"，所以返回 True。再比如s = "applepenapple"，字典里有"apple"和"pen"，可以拆成"apple" + "pen" + "apple"，注意单词可以重复用，所以也是 True。还有一个反例，s = "catsandog"，字典是["cats", "dog", "sand", "and", "cat"]，你可能会想拆成"cats" + "and" + "og"，但"og"不在字典里；按其它方式拆也拼不齐，所以返回 False。
这道题的约束很有意思：s的长度不超过 300，wordDict中单词数量不超过 1000，每个单词长度不超过 20。这些限制其实是在暗示你不是让你用指数级搜索，而是引导你用 DP 这种多项式解法。很多同学看到"字符串拼接"就想用回溯枚举所有分割点，那在最坏情况下有 2 的 n 次方种切法，n 一上 300 直接爆炸。所以这题第一个考点就是识别"子串组合等价于子问题"，动态规划就是干这个的。
1.2 为什么这题是动态规划的经典模型
要理解这题为什么是 DP，得先抓住一个本质：当你把字符串的前 i 个字符切出来时，它能不能被拼出来，只取决于更短的前缀是不是能被拼出来，以及中间那一段是不是一个字典词。
这个性质在算法里叫"最优子结构"。拿人话讲，如果我想知道s[0..i)能不能拆，我可以找一个分割点j（j 在 0 到 i 之间），先把s[0..j)拆好——这是更短的子问题，再检查s[j..i)是不是恰好等于字典里的某个词。如果这两个条件同时成立，那s[0..i)就肯定能拆。反过来说，如果所有可能的 j 都不行，那s[0..i)就一定拆不了。
你看，这个描述里没有"怎么拆"的过程，只有"能不能拆"的结果，天然适合把中间结果存下来。这跟斐波那契数列很像：要算第 i 项，得先知道前两项；不同点在于斐波那契的依赖是固定的，而这里的依赖取决于哪些分割点能让后半段成为字典词。这种"当前状态由之前多个状态转移而来"的问题，正是线性 DP 最熟悉的主场。
我最早在洛谷刷动态规划题单时碰到过类似的模型，比如"数字三角形""最长上升子序列"，都是在尝试定义"以 i 结尾的某个量"，这题的dp[i]定义成"前 i 个字符能否被拆分"，本质上也是同一套路。区别只是这题的"转移条件"更隐蔽，需要你去枚举分割点，所以很多人第一眼看不出来。
1.3 暴力解法为什么不行
在讲正解之前，必须要搞清楚暴力错在哪，才不会以后看到类似题又走回头路。最直觉的写法是递归枚举：从开头取一个子串，如果在字典里，就递归处理剩下部分；否则换个更长的子串试。如果你真的这么写，函数大概长这样：
def wordBreak(s, wordDict): wordSet = set(wordDict) def dfs(start): if start == len(s): return True for end in range(start + 1, len(s) + 1): if s[start:end] in wordSet and dfs(end): return True return False return dfs(0)这段代码在示例上能跑通，但一提交就超时。原因很简单：同一个子串s[start:]会被重复计算无数次。举个例子，s = "aaaa...a"加上字典里有"a"和"aa"，你会递归地去试各种切法，dfs(2)可能从dfs(1)和dfs(0)两条路各调一次，然后往下层层重复。这种重叠子问题如果不缓存，时间复杂度是指数级的。你可以在递归里加一个@lru_cache变成记忆化搜索，那其实就是动态规划的另一种写法，后面我会专门对比。
但如果你用纯递归又不缓存，n = 30 就已经卡得要死，更别说 300 了。所以这题的核心不是"想到递归"，而是"想到把子问题的答案记下来"。
2. 动态规划思路的核心推导
2.1 状态定义：dp[i] 表示什么
动态规划的做题七分靠定义状态。这题我建议用前缀而不是下标对应的单个字符来定义，这样能避开一堆边界问题。具体来说：
dp[i]表示字符串s的前i个字符（即s[0:i]）能否拆分成字典中的单词。
注意这里的前闭后开区间。i的取值从 0 到len(s)，其中dp[0] = True，表示空字符串是可以"拆分"的。这个初始化非常重要，它是一切转移的基础，后面会细说。比如s = "leetcode"，dp[4]表示"leet"能不能拆，dp[8]表示整个"leetcode"能不能拆，所以最终答案就是dp[len(s)]。
很多同学会问：为什么要用前 i 个字符而不是以 i 结尾？其实两种都能做，但前缀定义写起来更自然，因为切分的时候s[j:i]正好是后半段，跟dp[j]配合起来语义清晰。你要是用dp[i]表示s[i:]能否拆分也可以，那就是从后往前递推，状态转移变成dp[i] = any(dp[end] and s[i:end] in wordDict for end in range(i+1, n+1))，本质一样。个人建议先从前缀版本理解，它更贴合我们平时"从短到长"的直觉。
2.2 状态转移方程是怎么来的
有了状态定义，接下来要回答"如何用更小的状态推出更大的状态"。假设我们已经知道了dp[0]到dp[i-1]的所有值，现在想求dp[i]。我就想一件事：s[0:i]要能拆分，最后一步切的这一刀应该落在哪里？
假设最后一刀把前缀分成了两部分：前半段是s[0:j]，后半段是s[j:i]，其中0 <= j < i。如果dp[j]为 True，说明前半段已经能拆分；同时如果s[j:i]恰好等于字典里的某个单词，那么整个前缀当然能拆分。所以在所有可能的 j 里面，只要存在一个 j 同时满足这两个条件，dp[i]就是 True。
写成式子就是：
dp[i] = any(dp[j] and s[j:i] in wordDict for j in range(i))这里用到了一个叫"枚举分割点"的技巧。你可能觉得这不还是在暴力试吗？注意区别：dp[j]是一个布尔值，是已经算好的答案，不需要再递归展开；我们能枚举的 j 一共只有 i 个，所以每个dp[i]的计算复杂度是 O(i) 次检查，总复杂度是 O(n^2) 级别的，跟暴力递归完全不是一个量级。
那这个any是不是每次都要从 j=0 扫到 j=i-1？是，但我们可以用一个优化，后面讲。另外，这个式子也能反过来理解：dp[i]的 True 来源不是某一个固定的转移路径，而是多条可能的路径，任何一条通了就行。这也是"单词可重复使用"在状态里的体现——后半段可以是任意长度的字典词，不受前面已经用了哪些词的限制。
2.3 剪枝与优化：从 O(n^3) 到 O(n^2)
这里有个细节很多人没注意到。如果你在代码里直接嵌套三层循环：外层 i，内层 j，再加上判断s[j:i] in wordDict时又要切一次字符串切片，Python 字符串切片的时间复杂度是 O(长度)，那么最坏情况会变成 O(n^3) 左右。虽然 n=300 时 O(n^3) 也就是 2700 万，Python 勉强能过，但更优雅的做法是用一个wordSet集合来把 O(1) 的成员判断变成可能，同时利用单词长度上限做剪枝。
具体有两种优化：
优化一：只枚举可能的单词长度。既然字典里最长单词长度不超过 20，那么s[j:i]的长度i - j也不能超过 20。换句话说，j 只需要从i - max_len枚举到i - 1就够，不用从 0 开始。这能让内层循环的上限从 i 变成最多 20，总复杂度直接降到 O(n * max_len)。
优化二：反向检查字典前缀。这也是一种思路，先把所有字典词存成集合，然后遍历字典词而不是遍历 j。也就是说，对于当前 i，我们看以 i 结尾的、长度不超过 max_len 的每个位置 j，如果s[j:i]在字典里且dp[j]为真，就置 True。两种写法的效果一样。
我个人推荐在开讲的时候先不优化，先写一个逻辑清晰的版本，通过后再加剪枝。毕竟刷题追求的是先理解模型，再优化常数。真正面试的时候，你能说出"这里可以用 max_len 剪枝"就是加分项。
3. 代码实现与细节坑
3.1 Python 参考实现
下面这段代码是我在实际刷题时用的版本，也是我认为最易读的一个。先把字典转成集合，再把 max_len 算出来作为剪枝参数，最后用一个布尔数组逐层推进。
def wordBreak(s: str, wordDict: List[str]) -> bool: wordSet = set(wordDict) max_len = max(len(w) for w in wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): # 只检查长度不超过 max_len 的分割点 for j in range(i - 1, -1, -1): if i - j > max_len: break if dp[j] and s[j:i] in wordSet: dp[i] = True break return dp[n]这个版本的关键点有三个。第一，dp长度是 n+1，多出一个位置给空字符串。第二，内层 j 从 i-1 往 0 走，一旦发现长度超过 max_len 就 break，因为我们是在倒序遍历，继续往前只会更长。第三，一旦找到可行的分割点，直接break，后面的 j 不用再看了，因为只要有一条路通，dp[i]就已经是 True。
有些朋友可能更喜欢正向遍历，写出来长这样：
for i in range(1, n + 1): for j in range(max(0, i - max_len), i): if dp[j] and s[j:i] in wordSet: dp[i] = True break两个版本一样。正向遍历需要max(0, i - max_len)来保证 j 不越界；倒序遍历可以直接判断i - j > max_len来 break，更直观一点。
3.2 边界条件与初始化
初始化dp[0] = True是这题最容易忽略但又最关键的细节。为什么空字符串算"可拆分"？因为当 j=0 时，前半段是空串，后半段是s[0:i]，如果s[0:i]恰好是字典里的词，那么dp[i]应该为 True，而这就依赖于dp[0]为 True。如果dp[0]是 False，那么所有从开头直接匹配词的情况都会被漏掉。
有人会质疑：空串又不在字典里，凭什么说它能拆分？请注意，我们的 DP 定义是"能否拼接成"，而空串是"拼接零个单词"的结果，这种数学上的约定在 DP 里很常见，就像product初始化为 1 一样。你可以把它理解成递归的终止条件，或者说是地基。没有这个地基，整栋楼都盖不起来。
另一个边界是i从 1 开始还是从 0 开始。因为dp[0]已经手动设好了，dp里面位置 0 已经没有实际字符，所以外层循环必须从 1 开始，一直到 n。如果你不小心把dp[0]当作s[0]的拆分结果，后面全乱套。建议把dp[i]中的 i 理解为"字符数量"而不是"下标"，这样就能避免混淆。
3.3 常见错误：字符串切片、集合查找、顺序遍历
我见过太多人把这题写错，错法还都挺集中。第一个错误是用s[i:j]而不是s[j:i]，因为自己定义的 i 和 j 语义没分清。我的经验是：写的时候强制执行一个规则——dp[i]对应s[:i]，后半段永远是s[j:i]，写代码之前先在注释里写清楚"j < i"。这样能少一半 bug。
第二个错误是忘记把wordDict转成set。列表的in操作是 O(k) 的，集合是平均 O(1)，虽然这题单词数不算多，但配合大字符串时差距会很明显。而且不转 set 会导致你每次切片都要线性查表，很容易被卡 TLE。当然，如果测试用例里字典很长，转 set 也可能增加内存，但这题 1000 个词完全不用担心。
第三个错误是遍历顺序。正序遍历 j 时，一旦发现可行分割点就设 True，继续循环其实没意义，因为dp[i]不会从 True 变回 False。有些人在循环里设了 True 却忘了 break，继续跑完所有 j，虽然结果不错，但浪费了时间；还有人在循环里设了 True 之后，后续还有机会把它改成 False——这绝对不行，因为布尔 OR 操作不会把 True 变成 False，所以一旦找到通路，后面的循环可以安全退出。
还有一个小坑：Python 字符串切片s[j:i]当 j=i 时会返回空字符串，注意别让 j 取到 i。我们的循环里 j 最大到 i-1，所以不会出问题。如果你写range(i, -1, -1)，那 j=i 时dp[i]还没算完就用它判断，属于自引用，逻辑会出 bug。
4. 从力扣到真实场景：这题背后的模型
4.1 词法分析、分词、敏感词匹配
单词拆分这个模型不是只活在 OJ 里。我做过一个敏感词过滤工具，给一批黑名单短语，要判断一段用户输入是否只由这些短语组成，或者是否包含这些短语——本质上先把句子拆成词，再看组合。如果拆法不唯一，你还得选择一种合法拆法，这就用到了单词拆分的 DP 结果。你看力扣这题只问一个 True/False，但真实场景往往还要你输出拆分方案，这时候就需要在 dp 数组外再记录前驱节点。
再比如中文分词里的"正向最大匹配""双向匹配"，跟这题的思路非常像：给定一个词典，把句子切成词序列，让切出来的词都能在词典里找到。当然真正的分词还要考虑词频、新词发现，比这题复杂得多，但核心的可拼接判断就是单词拆分。如果你以后要做编译器前端或者自然语言处理，这题其实就是个迷你版词法分析器。
我之前给一个小项目做日志解析，日志里包含时间戳、级别、消息三部分，需要从一整条日志字符串里识别出各字段，同样是"给出一个大字符串，让你按字典里的模式切分"，当时我就想到了这个 DP。虽然模式匹配用了正则，但整体思想一脉相承：把一个大问题拆成前缀子问题和一段可识别片段。
4.2 变种题：输出所有拆分方案
力扣上这题的进阶版本是"单词拆分 II"，要求返回所有可能的拆分结果。这时候你就不能只存 dp 的布尔值了，得让dp变成一个列表的列表，dp[i]存所有能拼出s[:i]的方案。状态转移变成：对于每一个满足条件的 j，把dp[j]里的每个方案拼接上s[j:i]，生成新的方案放到dp[i]里。
但这里有个性能大坑：方案数量可能是指数级，所以真正的"单词拆分 II"往往要求你只返回非空解，而且为了避免超时，通常会先跑一遍"能否拆分"的 DP，只对可能成功的 indices 做记忆化搜索。我在刷题时就吃过亏：直接一上来就回溯，结果超时；后来先算可行性，再记忆化，才稳过。这个经验也验证了一个方法论：能拆分的剪枝先做，再构造方案。
如果你对这类变种感兴趣，洛谷的题单里也有类似的"字符串切割"DP题，比如"回文串划分"就要求输出所有回文划分方案，解法思路几乎一模一样，只是判断后半段的条件从"在字典里"变成"是回文串"。把单词拆分的模板掌握住，回文划分就是一个替换判断谓词的事。
4.3 记忆化搜索与 DP 的等价性
这里多说一句记忆化搜索。我们之前提到暴力递归加缓存可以解决重叠子问题，其实它和自底向上的 DP 是等价的，区别只是方向：一个从大问题开始递归，先求需要的子问题；另一个从小问题开始递推，先算底层再逐步往上。就这题而言，记忆化搜索可能反而更好写：
from functools import lru_cache def wordBreak(s, wordDict): wordSet = set(wordDict) n = len(s) @lru_cache(None) def dfs(i): if i == n: return True for end in range(i + 1, n + 1): if s[i:end] in wordSet and dfs(end): return True return False return dfs(0)这个版本把"当前从 i 开始的后缀能否拆分"记下来，dfs(0)得到答案。它和 dp 数组版本在时间上是同阶的，只是空间上多了一个递归栈。我在面试时更喜欢写记忆化版，因为它更接近人脑的递归直觉，不容易写错边界；而自底向上的版本在工程上更稳，不担心递归深度。Python 的lru_cache很方便，但注意别忘记加装饰器。
如果你已经理解了自底向上，建议两个都写一遍，能加深对 DP 的理解。以后遇到复杂状态（比如多维 DP）也更容易迁移。
5. 刷题避坑实录
5.1 为什么不能用贪心
很多人看到这题的第一反应是：从前往后匹配字典里的词，匹配上就截掉，继续匹配剩下的。这就是贪心。为什么贪心不对？因为可能出现"当前匹配的路径不是最优路径"的情况。
力扣官方就有一个经典用例：s = "aaaaaaa"，wordDict = ["aaaa", "aaa"]。如果贪心从前往后找最长匹配，先匹配"aaaa"，剩下"aaa"，也能匹配；但如果先匹配"aaa"，剩下"aaaa"，也能匹配。表面看似乎都行，但换个例子就崩了：s = "cars"，wordDict = ["car", "ca", "rs"]。贪心匹配"car"后剩下"s"，匹配不了，所以返回 False；但实际你可以拆成"ca" + "rs"，正确结果是 True。这就是贪心只看到了局部最优，忽略了整体组合。
这个教训是不是很眼熟？最长上升子序列、零钱兑换里也有类似的陷阱。只要一个决策会影响后面的决策，且你无法知道当前选择是否是全局最优的一部分，就不能贪心，得用 DP 枚举所有可能决策。这题的"所有可能决策"就是所有分割点。
5.2 示例陷阱：s="aaaaaa", wordDict=["aaaa","aa"]
这个例子特别阴。字符串全是 a，字典里有两个词："aaaa"和"aa"。肉眼一看，"aaaa" + "aa"正好 6 个 a，能拆。但如果你用我上面写的倒序剪枝版本，注意max_len = 4，处理i=6时，可能先检查s[2:6] = "aaaa"，在字典里，同时dp[2]是否 True？dp[2]能不能为 True 取决于s[0:2] = "aa"是否在字典里——在，所以dp[2] = True，于是dp[6] = True。这没问题。
但换个写法，如果你从j=0开始正序枚举，可能会先发现s[0:6]太长不在字典里，然后s[1:6]...反正最终也能找到，只是多跑几次。真正容易翻车的场景是：你自认为"aaaa"比"aa"长，所以当i=6时一定用前 4 个 a 加后 2 个 a，所以dp[6]只要看dp[2]就好——不对，你没有理由排除"aa"+"aa"+"aa"的拆法。DP 之所以稳，是因为它把所有可能长度都试了一遍，而不是依赖一个固定拆法。
这类"全一样字符"的用例是测试你对状态覆盖是否完整的照妖镜。我建议刷完题以后，自己构造一些字符串重复的用例跑一下，比如s = "abababab"，字典["ab", "abab"]，思考一下结果是不是 true，以及 dp 数组每个位置的值是怎么来的。这对加深理解特别有效。
5.3 复杂度优化心得
最后聊聊复杂度。不剪枝版本的复杂度是 O(n^3)（字符串切片也算 O(n)），剪枝后是 O(n * max_len)，因为每个 i 最多枚举 max_len 个 j，每次切一个长度不超过 max_len 的子串再查 set，总操作大约 300*20=6000 次，非常快。空间复杂度是 O(n) 的 dp 数组，再加上 O(wordDict 总字符数) 的 set，完全能接受。
但我实测下来，Python 里如果不用 max_len 剪枝，n=300 其实也能过，力扣给的时间限制没那么紧。真正要注意的是别在循环里反复创建新的子串列表，比如list(s[j:i])这种操作碰都不要碰。另外，如果你想把 dp 优化成一个bytearray而不是list[bool]，也可以，但可读性会下降，不太建议。
还有一个极小但常见的性能坑：max_len = max(map(len, wordDict))时，如果wordDict为空，会报错。但题目限制了wordDict至少有一个词，所以安全。不过你自己写封装函数时要考虑这个边界，加一句max_len = max(len(w) for w in wordDict) if wordDict else 0更稳妥。
我个人刷这题的实际体会是：先把它当作一道"枚举分割点 + 记住子问题"的题来做，不要一上来就背状态转移方程。等你亲手推几个例子，比如手写出s="leetcode"时 dp[1] 到 dp[8] 的每个值，你会发现这个模型比想象中简单。我在洛谷刷题时遇到过一道"切割回文串的最小切割次数"，当时用到的思路就是先跑一遍这个可拆分判断，再加工成最少切割次数的 DP。力扣上还有个"拼接最大单词数"的题，也是同一套模型的变体。
如果再遇到类似题，你可以先问自己三个问题：子问题是什么？状态怎么定义？转移时枚举什么决策？想清楚这三件事，代码基本就出来了。最后再分享一个小技巧：面试时如果写了 DP，一定要随手补一句"这里 dp[0] 表示空串可拆分，是递推的起点"，面试官一听就知道你是真懂，而不是背模板。这题不难，但细节能体现功力，希望这篇拆解能帮你把这题彻底吃透。
