题目回顾：Word Break 是在问什么？
题目给定：
- 一个字符串
s； - 一个字符串数组
wordDict，表示字典。
要求：
判断s能不能被拆分成若干个单词，这些单词都必须来自wordDict，并且可以重复使用。leetcode
例如：
s = "leetcode",wordDict = ["leet", "code"]，答案是true，因为可以拆成 “leet code”。leetcodes = "applepenapple",wordDict = ["apple", "pen"]，答案是true，可以拆成 “apple pen apple”。leetcodes = "catsandog",wordDict = ["cats","dog","sand","and","cat"]，答案是false，怎么拆都不行。leetcode
本题约束：1 ≤ s.length ≤ 300，1 ≤ wordDict.length ≤ 1000。leetcode
初始思路：dp[i]表示“前 i 个字母能否被拼出”
一开始的直觉非常自然：
- 定义
dp[i]表示前 i 个字符能不能由字典里的单词拼出来。 - 用 C 字符串的说法，就是判断
s[0..i-1]这一段是不是可拆分。
这是一个非常典型、也是正确的状态定义：
dp[0]对应“前 0 个字符”，也就是空串；dp[4]对应s[0..3]，比如 “leet”；dp[n]对应整个字符串s[0..n-1]。
但是在这个定义下，有两个关键点一开始容易踩坑：
dp[0]应该是true还是false？- 匹配一个单词时，要不要把“单词中间的 dp 位置”也标记为
true？
下面按这些疑问，一点点展开。
核心概念：前缀和“前缀结束点”
理解这题 DP 的关键，是把i看成一个“前缀结束点”。
什么是前缀
对字符串s = "applepen"：
- “a”、“ap”、“apple”、“applep”……都叫
s的前缀。 - 一般说“长度为 i 的前缀”，指的是
s[0..i-1]。
什么是前缀结束点
从下标的角度看：
- 字符的下标是
0..n-1； - 切割位置有
n+1个：开头的 0，字符之间的位置1..n-1，和最后结尾的n。
把dp[i]定义成：
dp[i] = true表示：在切割位置i把字符串切一刀，左边s[0..i-1]这一整段，已经可以完全由字典单词拼出来。
换句话说，i就是一个“可行前缀的结束点”。
这有两个重要含义：
dp[i] == true的下标i，才有资格作为“下一个单词的起点”；- 单词中间的那些位置，比如 “leet” 的 1、2、3，不能作为“前面那段已经完整拼完”的位置，所以
dp[1],dp[2],dp[3]不应该被设为true。
为什么dp[0]必须是true？
dp[0]表示：前 0 个字符（空串）能不能被“若干个字典单词”拼出来。
这里有一个常见约定：
- 空串可以看作由“0 个单词”拼出来。
- 也就是：不选任何单词，结果就是空串。
这样做的好处是：
- 把下标 0 当作第一个“可行前缀结束点”；
- 为后面的第一个单词提供一个起点。
例如在 “leetcode” 里：
- 如果
dp[0] = true，并且s[0..3] == "leet"，就可以把dp[4]设为true，这表示 “leet” 可以被拼出来。 - 如果
dp[0] = false，那从 0 开始永远扩展不出任何true状态，整个 DP 直接挂掉。
顺带一提：
- 本题的约束保证
s.length >= 1，不会出现空串输入。leetcode - 如果从数学上扩展这道题，让
s = ""，绝大多数人会认为答案应为true（空串可以由 0 个单词组成），也和dp[0] = true的建模是一致的。
注意：
这里不是说“字典里有一个空串单词”，而是说“空前缀是一种已经完成的状态”。
转移逻辑：只从true的位置向后扩展
在状态和dp[0]搞清楚之后，转移的思想可以归结成一句话：
只从那些
dp[i]为true的位置出发，尝试往后贴单词，更新新的前缀结束点。
更具体地说：
状态：
dp[i]表示s[0..i-1]是否可拆分。初始化：
dp[0] = 1（true），其余为 0（false）。leetcode转移：
外层遍历i，从 0 到str_len - 1：- 如果
dp[i] == 0，说明前缀s[0..i-1]还拼不出来，直接continue，不能从这里起步。leetcode - 如果
dp[i] == 1，说明这里是一个“可行前缀结束点”，可以尝试从这里往后贴单词。
内层遍历字典中的每个
word：- 记
word_len = strlen(word)。leetcode - 如果
i + word_len > str_len，说明这个单词贴过去会越界，跳过。leetcode - 否则比较子串：如果
s[i..i+word_len-1]恰好等于这个word（例如用strncmp(s + i, word, word_len) == 0），
说明从i出发，接上这个单词，可以安全到达位置i + word_len，
所以将dp[i + word_len] = 1。leetcode
- 如果
结束：
整个字符串长度为str_len，
如果dp[str_len] == 1，表示前str_len个字符（也就是整个s）可以被完全拆分，返回true；否则返回false。leetcode
这就是你最后写出的那份 C 代码的完整逻辑：
- 分配
dp[strlen(s) + 1]； memset(dp, 0, ...)全部初始化为 0；dp[0] = 1；- 两层循环做扩展；
- 返回
dp[str_len]。leetcode
“单词中间的dp值”为什么保持为false？
一开始你有一个想法：
匹配一个单词以后，从
i到i+len中间的dp都设为true。
现在可以清晰地看到，这样做是错的。原因有两个：
1. 语义不对
dp[k]的语义是：前 k 个字符能否被“完全拆完”。
- 如果从 0 匹配 “leet” 到 4，只能说明前 4 个字符 “leet” 是可拆的，也就是
dp[4] = true。 - 不应该得出“
dp[1],dp[2],dp[3]也都可拆”的结论，因为 “l”、“le”、“lee” 并没有被字典单词完全覆盖。
2. 会制造错误的起点
- 如果把
dp[1..3]都设为true，后续在这些位置继续贴单词，会创建出实际不存在的拆分路径。 - 例如，在复杂的例子中，这可能会让算法认为某个拆法是可行的，但其实中间断掉了。
正确的做法就是：
- 只更新单词末尾那个位置：从
i匹配长度为len的单词，只把dp[i + len]置为true。 - 单词内部的位置保持
false，这样循环走到这些位置时，看到dp[k] == 0，就会“自然跳过”。
和常见“背包形式”的关系
你提到过想用常见的“背包 DP 模板”来表达：
背包中常见形式：
dp[j] = max(dp[j], dp[j - w[i]] + v[i])在 Word Break 里，可以做一个类比：
j对应“前缀结束点”；w[i]对应“某个单词的长度len”；- 没有价值
v[i]，只关心“能否到达”。
逻辑上可以写成：
对每个 j（1..n） 对每个单词 word（长度 len）： 如果 j - len >= 0，dp[j-len] == true，并且 s[j-len..j-1] == word， 则 dp[j] = dp[j] || dp[j - len]； 实际上就是 dp[j] = true。和“max 写法”的对比：
- 把 “
max” 换成 “||”（逻辑或），表示“存在一种方案就行”； - 把 “
dp[j - w[i]] + v[i]” 换成了“dp[j-len]且子串匹配成功”。
不过在实际写代码时，这种“模板形态”的形式不如直接写if更直观，所以最后代码通常还是：
如果
dp[i]为 1 且s[i..i+word_len-1] == word，就dp[i + word_len] = 1。
完整思路小结
把上面的内容压缩成一个“拿来就能用”的解题框架：
1. 定义状态
dp[i]：前 i 个字符s[0..i-1]能否被字典单词完全拆分。
2. 初始化
dp[0] = true，表示空前缀已经是一个合法拆分；- 其他位置初始为
false。
3. 状态转移
遍历i从 0 到n-1：
- 如果
dp[i] == false，跳过（这个位置不能作为起点）。 - 否则枚举字典中的每个单词
word：len = word.length()，若i + len <= n且s[i..i+len-1] == word，- 则
dp[i + len] = true。
4. 答案
看dp[n]是否为true，n是s.length。
用一句话概括：
把每个dp[i] == true的位置，看成图中的一个点，从这里出发，用字典单词当边，一条条跳到新的位置i + len(word)，最后看能不能跳到位置n。
你提交的那份 C 代码，正是完整实现了这一套逻辑，并在 LeetCode 上通过了所有测试，用时 0ms，说明理解已经非常扎实。leetcode
相关链接
- Word Break - LeetCode 题目描述
- Word Break - LeetCode 提交记录
