题目描述
思路解析
一句话答案：LeetCode 139 单词拆分的标准解是布尔动态规划：dp[i] 表示 s 的前 i 个字符能否被词典完整切分，枚举最后一个词的起点 j，只要存在 dp[j] 为真且 s[j:i] 在词典里，dp[i] 就为真。贪心切最长词会让后面卡死，必须枚举所有切点。时间约 O(n² × L)、空间 O(n)。
单词拆分在判定什么
给字符串 s 和词典 wordDict，问能否把 s 从头到尾切成若干段，使每一段都恰好是词典里的词，词可以重复使用，答案只要 true 或 false。比如 s = "leetcode"、词典含 "leet" 和 "code"，切成 leet + code 即为 true。注意必须整串切干净，多一个字符盖不住都算失败，也不允许段与段重叠或留缝。
为什么不能贪心地每次匹配最长的词
直觉做法是从左往右扫，每次贪心咬下能匹配的最长词。反例很快出现：s = "aaaa"，词典是 ["aaa", "a"]，贪心先咬 "aaa"，剩下一个 "a" 能配上纯属侥幸；换成 s 长度稍变或词典稍变，先咬最长就把后面卡死，而 a + a + a + a 这样的切法明明存在。前面的选择会影响后面能不能切，单向贪心看不见这种牵连。
改成回溯搜索所有切法，最坏是指数级分支。但仔细看会发现大量重复：不同的前段切法常常在同一个位置会师，之后「剩下这一截能不能切」是同一个子问题，被反复求解。子问题只由「切到了哪个位置」决定——这就是重叠子问题加无后效性，动态规划的标准入口。
dp[i] 的含义与 dp[0] 为什么是 true
定义 dp[i] 为「s 的前 i 个字符（即 s[0:i]）能否被词典完整切分」，i 从 0 到 n，最终答案是 dp[n]。下标是「长度」而非「字符位置」，好处是空前缀有了名分：dp[0] = true，表示空串用零个词就拼成了。它不是凑数的技巧，而是第一个词的转移依据——切下开头的 "leet" 时，靠的正是「它左边的空串已经合法」。漏设 dp[0]，整张表推不起来，全盘皆否。
枚举最后一个词的转移为什么完备
算 dp[i] 时，盯住一种切法里的最后一个词：它必然从某个位置 j 开始、到 i 结束。于是「前 i 个字符可切」等价于「存在切点 j，使前 j 个字符可切，且 s[j:i] 恰好是词典里的词」。j 从 0 到 i-1 全枚举，任何合法切法的最后一刀都会被扫到，不存在漏判；找到一个成立的 j 就可以 break，因为 dp[i] 只关心存在性。
两个条件缺一不可：只查 s[j:i] 成词而不查 dp[j]，就可能接在一段根本切不开的前缀后面，链条中间是断的。把词典先存进哈希集合，s[j:i] in words 的判断均摊 O(1) 次哈希、代价主要在取子串本身。
复杂度多少，还能怎么提速
外层 i、内层 j 共约 n²/2 对切点，每对要取子串并做哈希，长度记 L，总时间约 O(n² × L)；dp 数组长 n + 1 加一个词典集合，空间 O(n) 级别。
提速有两条常用路：一是先算出词典里的最大词长 maxLen，内层 j 只需回看 i - maxLen 以内的范围，比它更早的切点不可能成词；二是把词典建成 Trie 前缀树，沿字符逐个下走做匹配，省掉反复取子串。若题目升级为列出所有具体拆分方案，那是 LeetCode 140 单词拆分 II，要用记忆化搜索去枚举句子，判定版的 dp 思路是它的地基。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这一句：每个位置看两件事——前面某处能拆 + 中间一段成词。下面每一格都在套它。
上行是 leetcode 每个字符（位置 0 到 8），下行 dp 待填。dp[i] 看的是「前 i 个字符」，从最左边开始。
空串什么都不用拆，算 0 个词拼成，所以 dp[0]=true（✓）。这是所有切分的合法起点。
判定 dp[1]：切点 j=0 处左边可拆，但中间 "l" 不在词典里，这个切法不行，再看别的切点。
前 1 个字符 "l" 试遍所有切点都不行，dp[1]=✗。但别急着放弃——后面更长的位置可能借到别的成词段。
判定 dp[2]：切点 j=0 处左边可拆，但中间 "le" 不在词典里，这个切法不行，再看别的切点。
前 2 个字符 "le" 试遍所有切点都不行，dp[2]=✗。但别急着放弃——后面更长的位置可能借到别的成词段。
判定 dp[3]：切点 j=0 处左边可拆，但中间 "lee" 不在词典里，这个切法不行，再看别的切点。
前 3 个字符 "lee" 试遍所有切点都不行，dp[3]=✗。但别急着放弃——后面更长的位置可能借到别的成词段。
判定 dp[4]：切点 j=0 处左边可拆（dp[0]=✓），中间这段 "leet" 正好是词典里的词 → dp[4] 成立！
前 4 个字符 "leet" 能拆：在 j=0 处断开，左边已可拆、右边 "leet" 成词。dp[4]=✓。
判定 dp[5]：切点 j=0 处左边可拆，但中间 "leetc" 不在词典里，这个切法不行，再看别的切点。
判定 dp[5]：切点 j=4 处左边可拆，但中间 "c" 不在词典里，这个切法不行，再看别的切点。
前 5 个字符 "leetc" 试遍所有切点都不行，dp[5]=✗。但别急着放弃——后面更长的位置可能借到别的成词段。
判定 dp[6]：切点 j=0 处左边可拆，但中间 "leetco" 不在词典里，这个切法不行，再看别的切点。
判定 dp[6]：切点 j=4 处左边可拆，但中间 "co" 不在词典里，这个切法不行，再看别的切点。
前 6 个字符 "leetco" 试遍所有切点都不行，dp[6]=✗。但别急着放弃——后面更长的位置可能借到别的成词段。
判定 dp[7]：切点 j=0 处左边可拆，但中间 "leetcod" 不在词典里，这个切法不行，再看别的切点。
判定 dp[7]：切点 j=4 处左边可拆，但中间 "cod" 不在词典里，这个切法不行，再看别的切点。
前 7 个字符 "leetcod" 试遍所有切点都不行，dp[7]=✗。但别急着放弃——后面更长的位置可能借到别的成词段。
判定 dp[8]：切点 j=0 处左边可拆，但中间 "leetcode" 不在词典里，这个切法不行，再看别的切点。
判定 dp[8]：切点 j=4 处左边可拆（dp[4]=✓），中间这段 "code" 正好是词典里的词 → dp[8] 成立！
前 8 个字符 "leetcode" 能拆：在 j=4 处断开，左边已可拆、右边 "code" 成词。dp[8]=✓。
最右 dp[8]=✓，说明整个 "leetcode" 能被拆完（leet + code）。dp[n] 就是最终答案。
边界先想清：能不能拼净，取决于是否存在一条切到底的合法链。
两个高频追问：求方案数/方案本身 → DFS+记忆化；提速 → 限切点范围或 Trie。
参考代码
def wordBreak(s, wordDict): words = set(wordDict) n = len(s) 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 words: dp[i] = True break return dp[n]复杂度
- 时间：O(n²·L)，外层 i、内层 j 共 O(n²) 个切点，每次取子串并查词典约 O(L)
- 空间：O(n)，dp 数组长度 n+1；词典用哈希集合
易错点
面试追问把动画讲成自己的话
追问如果还要列出所有拆分方案呢？
追问怎么给这题提速？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长递增子序列
LeetCode 300 · 中等 · 沿着 一维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题