题目描述
判断字符串 s 能否被拆成字典里的若干单词(可重复用)。
思路解析
最直接的想法：递归试每一个切分点，前缀是词就接着切剩下的。但同一段后缀（比如从第 4 个字符往后那段 "code"）会被很多条不同的前缀切法反复递归，调用数指数膨胀。慢就慢在重复子问题——很多位置「能不能拆到」被算了好多遍。
换成布尔 DP：dp[i] 表示「s 的前 i 个字符能不能用字典词拼出来」。转移：若 dp[j] 为真且 s[j:i] 是字典词，则 dp[i] 也为真。空串 dp[0]=True 当起点，像多米诺一样从能到的位置往后推。为什么能记表？每个位置「能否到达」只算一次存进 dp，后面直接查，省掉了重复递归。
建表 · 起点 dp[0]：表固定 1 行 9 列（dp[0]~dp[8]，下标=已拼好的字符数）。dp[0]=True：空串天然能拆，是整条多米诺的第一张牌。其余先全填 False，等被推到才翻成 True。
从 dp[0] 试 · "l"：dp[0] 能到，从这里往后试各种切分。先取 1 个字符 "l"：不在字典，dp[1] 仍是 False。这是一次负例：依赖格为真，但这段不是词，目标格不更新。
从 dp[0] 试 · "le"/"lee"：继续从 dp[0] 往后试 "le"、"lee"：都不是字典词，dp[2]、dp[3] 还是 False。前面这几格保持 False，正是因为没有任何合法词能落到它们身上。
从 dp[0] 试 · "leet" 命中：再取 4 个字符 "leet"：在字典！依赖格 dp[0]=True 且这段合法，两个条件同时成立，dp[4] 翻成 True。多米诺推倒了第一块——前 4 个字符能拼出来。
到 dp[1..3] · 起点不可达：轮到位置 1、2、3 当起点：但它们 dp 都是 False，自己都到不了，往后推也没意义，直接跳过（代码里的 if not dp[i]: continue）。只有能到的点才有资格往后推。
从 dp[4] 试 · "c"/"co"/"cod"：dp[4]=True，从这里往后试 "c"、"co"、"cod"：都不是字典词，dp[5]、dp[6]、dp[7] 保持 False。再次看到依赖格为真也不够，还得这段恰好是词。
从 dp[4] 试 · "code" 命中：取 "code"：在字典！依赖格 dp[4]=True 且这段合法，dp[8] 翻成 True。多米诺一路推到了终点。
答案 = dp[8]：dp[8]（整个串）= True，返回 true。中间一串 False 是「拼到这里拼不齐」的位置，只有 0、4、8 这几张被推倒的牌串成了 "leet"+"code"。
「前面能到 + 这一段合法 → 后面也能到」是一类很常见的可达性 DP。只从 dp[i]=True 的点出发往后推，避免在到不了的位置上白费力气。
参考代码（Python）
1def wordBreak(self, s, wordDict):
2 wordSet = set(wordDict) # set 查词 O(1)
3 n = len(s)
4 dp = [False] * (n + 1)
5 dp[0] = True # 空串是起点
6 for i in range(n + 1):
7 if not dp[i]: continue # 到不了 i 就跳过
8 for j in range(i + 1, n + 1):
9 if s[i:j] in wordSet: # 这一段是个词
10 dp[j] = True # 那么 j 也能拆到
11 return dp[n]复杂度分析
- 时间复杂度：O(n²) —— 外层 i、内层 j 两重循环，约 n²/2 对 (i,j)；切片比较再带 O(k)
- 空间复杂度：O(n) —— dp 数组 n+1 个布尔，外加字典集合
套路模板
记住骨架：dp[0]=True 当起点、只从能到的点往后推、改 valid 那一行。完全平方数、零钱凑数都是同一张多米诺骨牌。
1dp = [False] * (n + 1)
2dp[0] = True # 起点天然能到
3for i in range(n + 1):
4 if not dp[i]: continue # 到不了 i 就跳过
5 for j in 从 i 出发的候选终点:
6 if valid(i, j): dp[j] = True # 这段合法 → j 也能到
7return dp[n]易错点
- 错误写法：dp = [False]*(n+1) 后忘了 dp[0]=True → 正确写法：dp[0] 必须先置 True（空串是递推起点，dp[0] 是 False 的话第一个词永远推不出来，结果恒为 false）
- 错误写法：内层 j 从 i 开始或写成 range(i) → 正确写法：j 应从 i+1 到 n+1（j>i 才有非空子串）（j<=i 会取到空段或回头段，导致死循环或漏掉真正的词）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。