LC139动态规划序列 DP · 单词拆分 · 切刀扫描状态表账本

单词拆分

s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。

题目是什么

s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。

解决什么问题

当前格依赖哪些已知状态，为什么这些状态已经计算完成？

核心结论

dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。

01交互算法精讲

先说结论：这道题到底解决什么

怎样从“s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。”推导出序列 DP · 单词拆分 · 切刀扫描，并证明每次状态变化都不会漏掉答案？

中心结论：dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。

读完必须能回答

1.暴力方案在哪里重复计算，为什么仍然是正确基线？
2.当前格依赖哪些已知状态，为什么这些状态已经计算完成？
3.不变量“dp[i] true 当且仅当存在 j 使 dp[j]=true 且 s[j:i] 在 wordSet。”为什么能保证算法安全前进？

02交互算法精讲

完整题目与题意拆解

s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。

在本站主例中，s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。

算法最终需要得到或观察：leetcode → dp[8]=true；catsandog → dp[9]=false。

把题目翻译成状态

• 输入：s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。
• 机器需要维护：dp[0..n]、右边界 i、切分点 j、子串 s[j:i]。
• 最终可观察结果：leetcode → dp[8]=true；catsandog → dp[9]=false。

动画 1 · 题意扫描

先看清算法到底要维护什么

先建立输入、目标、输出和第一批状态，不急着进入模板。

Step 1/20%

题目与输入建立输入、目标与算法心智

词典: leet,code

正在加载算法场景...

发生了什么

s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。

为什么

dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。

下一步

dp[i] = 前 i 字符能否拆分：dp[0]=true

当前状态

dp[0..n]、右边界 i、切分点 j、子串 s[j:i]。

当前 Go 代码 · 高亮第 1 行

1func wordBreak(s string, wordDict []string) bool {2    words := make(map[string]bool, len(wordDict))3    for _, word := range wordDict { words[word] = true }4    dp := make([]bool, len(s)+1)

03交互算法精讲

第一层方案：暴力做法

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选，但没有保存已经确认的信息，因此同一状态会被重新计算。

动画 2 · 暴力重复

重复工作究竟发生在哪里

把重复读取或重复搜索的区域明确标出，再决定优化必须保存什么。

Step 1/20%

先做对：建立暴力基线枚举所有候选并完整验证

词典: leet,code

正在加载算法场景...

发生了什么

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

为什么

暴力法覆盖所有候选，因此可以作为题意校验版本；它的问题是重复工作，不是答案错误。

下一步

重复信息暴露出来：标出被重新计算的状态

当前状态

dp[0..n]、右边界 i、切分点 j、子串 s[j:i]。

当前 Go 代码 · 高亮第 3 行

1func wordBreak(s string, wordDict []string) bool {2    words := make(map[string]bool, len(wordDict))3    for _, word := range wordDict { words[word] = true }4    dp := make([]bool, len(s)+1)5    dp[0] = true6    for end := 1; end <= len(s); end++ {

优化方向：dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。

04交互算法精讲

整体地图：先做什么，再做什么

1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2状态只维护 dp[0..n]、右边界 i、切分点 j、子串 s[j:i]。
3转移每一步按照 dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。
4收尾读取 leetcode → dp[8]=true；catsandog → dp[9]=false。，并复核边界与复杂度。

05交互算法精讲

状态表账本：核心概念

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：dp[0..n]、右边界 i、切分点 j、子串 s[j:i]。

核心不变量

• dp[i] true 当且仅当存在 j 使 dp[j]=true 且 s[j:i] 在 wordSet。
• dp[0]=true 表示空前缀是合法起点，非最终答案。

动画 3 · 核心概念

建立“状态表账本”心智模型

用主例建立核心状态，先预测下一步，再公开正确分支和理由。

Step 1/30%

题目与输入建立输入、目标与算法心智

词典: leet,code

正在加载算法场景...

发生了什么

s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。

为什么

dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。

下一步

dp[i] = 前 i 字符能否拆分：dp[0]=true

当前状态

dp[0..n]、右边界 i、切分点 j、子串 s[j:i]。

当前 Go 代码 · 高亮第 1 行

1func wordBreak(s string, wordDict []string) bool {2    words := make(map[string]bool, len(wordDict))3    for _, word := range wordDict { words[word] = true }4    dp := make([]bool, len(s)+1)

06交互算法精讲

核心机制：状态如何一步步变化

dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。

执行过程中持续维护：dp[0..n]、右边界 i、切分点 j、子串 s[j:i]。

正确性依赖以下不变量：dp[i] true 当且仅当存在 j 使 dp[j]=true 且 s[j:i] 在 wordSet。；dp[0]=true 表示空前缀是合法起点，非最终答案。

面试时可以压缩为：dp[i] 表示前 i 字符能否拼出；dp[0]=true 为合法起点；枚举 i 为右边界、j 为切分点；wordDict 转 set；maxLen 优化切分范围；返回 dp[n]。

落到当前题，执行机制可以压缩为：dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

动画 4 · 机制构建

一次状态转移为什么成立

集中观察一次选择、计算和状态写回，让变量变化与原因同时出现。

Step 1/50%

dp[0] 真且 'leet' 在词典 → dp[4]=truedp[i]=true

切分 'leet' = ... + 'leet'

正在加载算法场景...

发生了什么

找到合法切分。

为什么

一旦 true 可提前 break。

下一步

dp[4] 真且 'code' 在词典 → dp[8]=true：dp[i]=true

当前状态

dp[4]=true via 'leet'。

当前 Go 代码 · 高亮第 2 行

1func wordBreak(s string, wordDict []string) bool {2    words := make(map[string]bool, len(wordDict))3    for _, word := range wordDict { words[word] = true }4    dp := make([]bool, len(s)+1)5    dp[0] = true

07交互算法精讲

正确性证明：为什么不会漏答案

初始化

初始化：算法开始时，全部合法候选仍在状态表示范围内；dp[i] true 当且仅当存在 j 使 dp[j]=true 且 s[j:i] 在 wordSet。

保持

保持：执行“dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。”时，只删除已经能证明不可能的候选，并把新信息写回 dp[0..n]、右边界 i、切分点 j、子串 s[j:i]。

终止

终止：没有待处理状态或达到命中条件时，当前可观察结果就是“leetcode → dp[8]=true；catsandog → dp[9]=false。”。

正确性抓手不是“样例跑通”，而是每一帧结束后仍能复述：dp[i] true 当且仅当存在 j 使 dp[j]=true 且 s[j:i] 在 wordSet。；dp[0]=true 表示空前缀是合法起点，非最终答案。

08交互算法精讲

完整执行过程

1题目与输入s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。因为：dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。
2dp[i] = 前 i 字符能否拆分准备填布尔 DP。因为：dp[i] 依赖 dp[j] 与 substring(j,i)。
3dp[0] 真且 'leet' 在词典 → dp[4]=true找到合法切分。因为：一旦 true 可提前 break。
4dp[4] 真且 'code' 在词典 → dp[8]=true找到合法切分。因为：一旦 true 可提前 break。
5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6可以拆分返回 dp[n]。因为：O(n²·L) 枚举切点。
7dp[i] = 前 i 字符能否拆分准备填布尔 DP。因为：dp[i] 依赖 dp[j] 与 substring(j,i)。
8收尾与复杂度leetcode → dp[8]=true；catsandog → dp[9]=false。因为：时间 O(n·maxLen) 基础口径 O(n²) · 空间 O(n)。dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。

动画 5 · 完整执行

从输入完整走到可观察结果

从主例第一帧运行到答案，时间轴始终显示当前状态、因果解释和下一步。

Step 1/80%

题目与输入建立输入、目标与算法心智

词典: leet,code

正在加载算法场景...

发生了什么

s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。

为什么

dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。

下一步

dp[i] = 前 i 字符能否拆分：dp[0]=true

当前状态

dp[0..n]、右边界 i、切分点 j、子串 s[j:i]。

当前 Go 代码 · 高亮第 1 行

1func wordBreak(s string, wordDict []string) bool {2    words := make(map[string]bool, len(wordDict))3    for _, word := range wordDict { words[word] = true }4    dp := make([]bool, len(s)+1)

09交互算法精讲

把动画和 Go 代码逐行对应

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段，在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

动画 6 · 代码映射

让每个动作都落到 Go 分支

重新执行关键分支，只显示当前代码附近窗口，并说明这行为什么在此刻运行。

Step 1/60%

dp[i] = 前 i 字符能否拆分dp[0]=true

词典: leet,code

正在加载算法场景...

发生了什么

准备填布尔 DP。

为什么

dp[i] 依赖 dp[j] 与 substring(j,i)。

下一步

dp[0] 真且 'leet' 在词典 → dp[4]=true：dp[i]=true

当前状态

空串可拆分。

当前 Go 代码 · 高亮第 3 行

1func wordBreak(s string, wordDict []string) bool {2    words := make(map[string]bool, len(wordDict))3    for _, word := range wordDict { words[word] = true }4    dp := make([]bool, len(s)+1)5    dp[0] = true6    for end := 1; end <= len(s); end++ {

10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法

func wordBreak(s string, wordDict []string) bool {
    words := make(map[string]bool, len(wordDict))
    for _, word := range wordDict { words[word] = true }
    dp := make([]bool, len(s)+1)
    dp[0] = true
    for end := 1; end <= len(s); end++ {
        for start := 0; start < end; start++ {
            if dp[start] && words[s[start:end]] {
                dp[end] = true
                break
            }
        }
    }
    return dp[len(s)]
}

最小测试集合

func main() {
    // 1. 主例
    //    输入：mode="word-break", text="leetcode", wordDict=["leet","code"]
    //    期望：leetcode → dp[8]=true；catsandog → dp[9]=false。
    //
    // 2. 失败 / 未命中
    //    检查：局部匹配不等于全局可拆分（catsandog）。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC140 所有拆分；LC472 拼接
}

11交互算法精讲

正确性与复杂度

时间复杂度 O(n·maxLen) 基础口径 O(n²)

执行过程中只保留仍可能影响答案的状态。dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。

空间复杂度 O(n)

额外状态主要用于维护：dp[0..n]、右边界 i、切分点 j、子串 s[j:i]。

终局不变量

• dp[i] true 当且仅当存在 j 使 dp[j]=true 且 s[j:i] 在 wordSet。
• dp[0]=true 表示空前缀是合法起点，非最终答案。

12交互算法精讲

最容易写错的地方

错误 1

局部匹配不等于全局可拆分（catsandog）。

错误 2

勿写 O(n)/O(1)；dp 数组 O(n)，切分枚举 O(n²) 或 O(n·maxLen)。

边界复查

必须额外检查空输入、单元素、未命中或不可达情况，以及恰好落在边界的输入。

13交互算法精讲

最后复盘：带走逻辑链

1题意s="leetcode", wordDict=["leet","code"] 能否被词典单词完整拼出；失败例 catsandog。
2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3优化dp[i]=s[0:i] 能否拼出；对每个 i 枚举切分点 j，若 dp[j] 且 s[j:i]∈wordSet 则 dp[i]=true。
4证明dp[i] true 当且仅当存在 j 使 dp[j]=true 且 s[j:i] 在 wordSet。；dp[0]=true 表示空前缀是合法起点，非最终答案。
5复杂度时间 O(n·maxLen) 基础口径 O(n²)，空间 O(n)

面试表达：dp[i] 表示前 i 字符能否拼出；dp[0]=true 为合法起点；枚举 i 为右边界、j 为切分点；wordDict 转 set；maxLen 优化切分范围；返回 dp[n]。

迁移练习

• LC140 所有拆分
• LC472 拼接