单词拆分：前缀能拆，才允许在这里接一个词
dp[i] 表示 s 的前 i 个字符能否拆完。枚举最后一词的起点 j：dp[j] 为真且 s[j:i] 在词典里，dp[i] 就成立。
词典放进集合。dp[0]=true。对每个结尾 i，枚举 j∈[0,i)，若 dp[j] 且 s[j:i] 在集合中，则 dp[i]=true 并停止枚举。答案 dp[n]。时间 O(n²)，空间 O(n)。
这是 LeetCode 139. Word Break。字符串 s 和一个字符串词典 wordDict，判断 s 能不能拆成一个或多个词典里的单词。单词可以重复使用，必须恰好拼满 s，不能剩字符，不能重叠使用同一段。
主例 s = "leetcode"，wordDict = ["leet","code"]。前 4 个字符 leet 在词典里，后 4 个 code 也在，整串可拆，答案 true。演示先点亮 dp[4]，再点亮 dp[8]。
第一直觉是从左往右贪心吃最长词。"aaaaaaa" 配 ["aaaa","aaa"] 时，先吃 4 个 a 会剩 3 个，其实 3+4 也能拼。缺的是「每个前缀是否可拆」的备忘，好让后面的词接在任意一个成功前缀后面。下面从这块缺口推出前缀 DP。
固定结尾，枚举最后一词从哪切开
整串可拆，当且仅当存在一种切法让每一段都在词典里。切点可以有很多，暴力递归会在同一前缀上反复问「你能不能拆」。这个布尔答案只依赖前缀长度，应该记下来。
缺的信息是 dp[j]：s[0:j] 是否已经能拆。没有它，你在位置 i 配到一个词典词 s[j:i]，也不知道左边那截是否合法。贪心只保留一种切法，主例够用，带歧义的重复字符就会假阴性。
从缺口定义状态。dp[0]=true，空前缀视为拆好，这样第一个词可以从 0 切开。对每个 i=1..n，枚举 j=0..i−1：若 dp[j] 为真，并且 s[j:i] 在集合里，则 dp[i]=true，后面的 j 不必再看。词典先放进哈希集合，否则每次线性扫列表。
用手走主例。s 长度 8，dp 长度 9，起先只有 dp[0]=true。i 走到 4 之前，任何 s[0:i] 都不是 leet 或 code，全是 false。i=4，j=0，dp[0] 为真且 s[0:4]="leet" 在词典，dp[4]=true。演示第一帧 hit=leet。i=5、6、7 接不上新词。i=8，j=4，dp[4] 为真且 s[4:8]="code" 在词典，dp[8]=true。演示第二帧。整串可拆。
s="applepenapple"、词典含 apple 与 pen 时，dp 会在 5、8、13 依次为真，同一个 apple 用了两次，这是允许的。某前缀永远点不亮，后面即使有词也接不上。每个 (i,j) 对切一段子串，时间按 O(n²) 计；子串哈希按实现另计。Trie 可以把「从 j 出发能匹配哪些词」收成沿字符走，最坏仍和 n、词长有关。
dp[0] 必须是 true第一个词没有「再前面的前缀」。空前缀算拆好，leet 才能在 j=0 处合法切开。写成 false，主例 dp[4] 永远点不亮。
Go：DP + 词典集合
func wordBreak(s string, wordDict []string) bool {set := map[string]bool{}for _, w := range wordDict { set[w] = true }dp := make([]bool, len(s)+1)dp[0] = truefor i := 1; i <= len(s); i++ {for j := 0; j < i; j++ {if dp[j] && set[s[j:i]] {dp[i] = truebreak}}}return dp[len(s)]}
1词典进集合，判断 s[j:i] 是否成词是平均 O(1)。
2dp[0]=true。主例 i=4、j=0 时靠它点亮 leet。
3必须先有 dp[j]，再接 s[j:i]。只看词在不在词典、不问左边，会把前缀垃圾也算成功。
4命中就 break。主例 i=8 在 j=4 接上 code，不必再试别的切点。
总结
前缀可拆才能接词。主例 dp[4] 吃 leet，dp[8] 吃 code，整串 true。
- 贪心吃最长词会在重复字符上假阴性。每个前缀都要记能否拆。
- dp[0]=true 是第一个词的切口。dp[n] 才是答案。
- 词可重复使用：状态里没有「这个词用过没有」，只有前缀切没切开。