题目描述
判断字符串 s 能否被拆成字典里的若干单词(可重复用)。
s = "leetcode"
dict = ["leet", "code"]
输出 = true
思路解析
直接递归试每个切分点，会有大量重复计算。用 dp 记住「前 i 个字符能不能拆」，每个位置只算一次。
从一个「能拆到」的位置 i 出发，如果 s[i:j] 正好是字典里的词，那位置 j 也「能拆到」。空串 dp[0] 是能（真），像多米诺骨牌一样往后推。
建表：dp[i] 表示「s 的前 i 个字符能不能拆分」。dp[0] = ✓（空串总能拆），其余先记 ✗。列号对应字符位置。
想清楚状态：dp[i] 为真表示「s[0:i] 这段能用字典词拼出来」。目标就是 dp[n]（整个字符串）。
i=0 → 匹配 "leet"：从 dp[0]=✓ 出发，前 4 个字符 "leet" 在字典里，所以前 4 个能拆，dp[4]=✓。
i=0 · 其他切分：从 dp[0] 出发还试了 "l"、"le"、"lee" 等切分，都不在字典，只有 "leet" 命中。
i=4 → 匹配 "code"：再从 dp[4]=✓ 出发，接下来的 "code" 在字典里，dp[8]=✓。
答案 = dp[8]：dp[8] = ✓，整个字符串能被拆分，返回 true。
「前面能到 + 这一段合法 → 后面也能到」是一类很常见的可达性 DP。
参考代码（Python）
Python
1wordSet = set(wordDict)
2dp = [False] * (n + 1)
3dp[0] = True # 空串总能拆
4for i in range(n + 1):
5 if not dp[i]: continue # i 拆不到就跳过
6 for j in range(i + 1, n + 1):
7 if s[i:j] in wordSet: # 这一段是个词
8 dp[j] = True # 那么 j 也能拆到
9return dp[n]复杂度分析
- 时间复杂度：O(n²) —— 每个 i 试每个 j(切片再 +k)
- 空间复杂度：O(n) —— dp 数组 + 字典集合
套路模板
记住骨架：dp[0]=True 当起点、只从能到的点往后推、改 valid 这一行。完全平方数、零钱凑数都是同一张多米诺骨牌。
Python
1# 凡是「前面能到 + 一段合法 → 后面也能到」都套
2dp = [False]*(n+1); dp[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[0]=True → ✅ dp[0] 必须初始化为 True（空串是递推的起点，否则全是 False）
- ❌ 字典用 list 查找 → ✅ 转成 set 再查（list 查找 O(n)，会超时）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。