【算法】动态规划第七篇（终章）：单词拆分 II——缓存结论的完全体，与两个系列的合龙

【算法】动态规划第七篇（终章）：单词拆分 II——缓存结论的完全体，与两个系列的合龙摘要 DP 系列第七篇，终章。LC140 单词拆分 II——回溯系列里三度交锋的老对手（417 万次调用、缓存候选词列表"一个数字都没差"、“缓存结论不缓存选择"的判据），带着六级 DP 的装备回来合龙。本篇三块内容：修复 can2[end]（回溯只查"词匹配"不查"后缀可行性”——死路照样迈步，补上这一个条件，

发表于 2026/09/20

作者 贾永琪

29 分钟阅读

文章信息
原文链接：https://jiayq.blog.csdn.net/article/details/164458105
发布时间：2026-09-20 20:11:37
标签：#Golang, #算法, ##算法讲解, ##单词拆分多解法

【算法】动态规划第七篇（终章）：单词拆分 II——缓存结论的完全体，与两个系列的合龙

摘要

DP 系列第七篇，终章。LC140 单词拆分 II——回溯系列里三度交锋的老对手（417 万次调用、缓存候选词列表”一个数字都没差”、“缓存结论不缓存选择”的判据），带着六级 DP 的装备回来合龙。本篇三块内容：修复can2[end]（回溯只查”词匹配”不查”后缀可行性”——死路照样迈步，补上这一个条件，地狱用例从走进去 N 步变成 1 次调用 ）；memo 完全体 （map[int][]string 缓存完整产出——递归从”走路”变成”回答问题”，198 打家劫舍演化链的第一步在字符串世界重演）；两条路线实测对照 （预计算 vs 惰性：死路海洋里 1 vs 77，活路重复里 6 vs 7——各有主场，合体最优）。最后把回溯三篇 + DP 七篇串成一张地图：从决策树到状态机，正好走完一个圆。

前置阅读：动态规划第六篇：状态机DP——股票家族全集与三例副作用死刑。配套代码仓库（按题号分目录）：https://github.com/a18792721831/studyleetCode

系列篇目：
一、从打家劫舍到状态设计的三堂课
二、双序列DP三课——继承、计步与断链
三、背包第一课——贪心之死与正序倒序开关
四、背包收官——min哨兵、计数世界与组合排列分水岭
五、区间DP——从看什么都像背包到最后戳谁
六、状态机DP——股票家族全集与三例副作用死刑
七、单词拆分 II——缓存结论的完全体，与两个系列的合龙（本篇，终章）

1. 修复：`can2[end]`——死路不许迈步

上一版代码的骨架已经全对：倒序可行性表 can2 + 回溯枚举。但跑起来总感觉哪里不对——回溯的匹配条件是这样的：

  
if idx+len(wordDict[i]) <= len(s) && s[idx:idx+len(wordDict[i])] == wordDict[i] {
    // 词匹配就下沉
}

只查了”词匹配”，没查 can2 表。 表辛辛苦苦算出来了，下沉之前却不看一眼——词匹配但后缀必死的分支，照样迈步走进去，等整棵子树撞墙返回，才知道这条路白走。

修复就一行：

  
end := idx + len(w)
if end <= len(s) && s[idx:end] == w && can2[end] {   // ← 补上 can2[end]
    path = append(path, w)
    backtrack(path, end)
    path = path[:len(path)-1]
}

实测效果，用回溯三的老朋友（22 个 a + b，字典 a 到 aaaaaaaaaa，无解用例）：

22 个 a + b：
can2[end] 修复后：  1 次调用

1 次。 backtrack(0) 进去，词表里每个词都匹配 s 开头的 a（a、aa、aaa 都能对上），但 can2[end] 全是 false——b 在字典里没有，所有后缀全部必死。于是 for 循环扫完五个词，一步都没下沉，函数返回。整棵指数级的搜索树，在根节点就被摁死了。

这是”折叠判断”招式的又一次登场：把”从这走到底有没有戏”这个指数级的判断，折叠成一次 O(1) 查表。回溯三里数过这个招式的四次登场（131 回文表、140 can 数组、464 位掩码、51 对角线标记），本篇是第五次——也是它最风光的一次。

1.1 一个冷知识：can 表算了，但没用

最终代码里其实躺着两张表：can（正序，can[i] = 前 i 个字符能否拆完）和 can2（倒序，can2[i] = 从 i 到末尾能否拆完）。剪枝用的只有 can2——can 算完了没人消费。

为什么？回溯站在位置 idx，切出一个词到达 end，它要问的问题是：“从 end 往后还拆得动吗？” ——这是 can2[end]。而 can[end] 回答的是”前 end 个字符拆得动吗”——这是对过去的总结，回溯已经站在 end 了，过去不需要它操心，未来它一无所知。

can 是 139 单词拆分的 DP 解法原样搬过来的——可行性从左往右推，在 139 里它就是正确答案。但 140 的消费方变了：回溯从左往右走，它剪的是右边的枝，需要的是倒序表 。第一反应顺着 139 的惯性写了正序，写完才发现方向错位。

表的方向要跟着消费方走。can 留在代码里没删——它是思考的脚印：先按惯性写了正序，意识到剪枝要的是倒序，再补 can2。踩坑的证据比正确答案更值钱。

2. memo 完全体：缓存”从这出发的所有句子”

回溯三里，140 的记忆化死了三次：

map[int]string 缓存”这个位置选了哪个词”——缓存选择，锁死分支，只能找到一个方案
map[int][]string 缓存”这个位置能匹配的所有词”——缓存候选，正确性达标，但 22a+b 跑出来 4,169,729 次调用，和完全没有 memo 一个数字都没差 。因为命中缓存后照样要 for 循环递归展开全部候选——子树还是整棵重搜，省掉的只是”重新扫描词表做匹配”的零钱
判据立住：缓存结论，不缓存选择 。能防爆炸的只有两种——can[end]（能否拆完，false 整支不进）和完整产出（从这能拼出的所有句子，直接拼接）

终章把第三种的完整形态写出来——死刑犯的终局，缓存的完全体：

  
func wordBreak(s string, wordDict []string) []string {
	// memo[start] = 从 start 到末尾能拼出的【所有句子】
	memo := make(map[int][]string)
	var dfs func(start int) []string
	dfs = func(start int) []string {
		if start == len(s) {
			return []string{""} // 哨兵：末尾产出"一个空句子"（不是 nil！）
		}
		if r, ok := memo[start]; ok {
			return r // 第二次到达：整棵子树一步不进
		}
		var out []string
		for _, w := range wordDict {
			end := start + len(w)
			if end <= len(s) && s[start:end] == w {
				for _, tail := range dfs(end) { // 后缀能拼出的所有句子
					if tail == "" {
						out = append(out, w)          // 词恰好接到末尾：自成整句
					} else {
						out = append(out, w+" "+tail) // 词 + 空格 + 后缀句
					}
				}
			}
		}
		memo[start] = out // 缓存完整产出
		return out
	}
	return dfs(0)
}

对照回溯版骨架看，四个关键点：

① 递归有了返回值——从”走路”变成”回答问题”。 回溯版的递归是 void，做的是”沿着一条路走下去，把沿途的词记在 path 里”；memo 版的递归回答一个定义明确的问题：“从 start 到末尾能拼出哪些句子？”——答案完全由参数 start 决定。“回答问题”的函数才配被缓存 ，因为同样的输入永远给出同样的输出。回溯版为什么 memo 不上？病根就在这：它的”产出”散落在 path、res 这些伴随物里，返回值是空的——没有东西可缓存。这就是当年缓存候选词列表死刑的深层原因：它缓存的是过程碎片，不是问题的答案 。

② 哨兵的三态区分。 nil（拼不出，零种产出）≠ []string{""}（拼得出一种——空句子）≠ ["dog"]（拼得出一种——dog）。边界 return []string{""} 是拼接逻辑的地基：每个词拿到后缀的所有句子，词 + 空格 + 后缀句，统一处理。tail == "" 的特判只服务于”这个词自己就是整句”的退化情况。打家劫舍的”哨兵配对原则”在字符串世界的形态。

③ 撤销三连消失了。 没有 path、没有 append/trim、没有全局 res。选择（词）直接拼进返回值，递归返回即成型。纯函数进、纯函数出，没有副作用就没有还原义务。

④ memo 的 key 就是状态。 start——回溯三”五步法”里剥出来的那个状态（“切到哪个位置”），在这里原样成为缓存的钥匙。状态设计完成的那一刻，memo 的形态就定死了。

还有一个值得停一秒的画面：这是 198 打家劫舍演化链第一步的重演 。第一篇里，打家劫舍从”回溯枚举选/不选”走到”有返回值的递归”（robFrom(i) = max(...)），再走到 memo，再走到 DP 数组。当时是数字世界（抢或不抢），现在是字符串世界（切哪个词）——同一个演化链，换了布景再走一遍 。可见那不是打家劫舍的特殊技巧，是”回溯 → DP”的一般道路。

3. 两条路线实测：预计算 vs 惰性，各有主场

修复版（can2[end] + 回溯）和 memo 完全体都过了全部用例。有意思的是拿调用次数一比——两个用例，两个方向：

                    catsanddog        22 个 a + b（死路海洋）
can2[end]+回溯:      7 次调用              1 次调用     ← 死路一步不进
memo 完全体:         6 次调用             77 次调用     ← 活路重复全免，死路要走进去才算死

同一对算法，两个用例，胜负完全颠倒。 拆开看为什么。

3.1 死路海洋：can2 碾压（1 vs 77）

can2 是先知模式 ——自底向上，循环没开始跑之前就把整个可行性世界算完了（O(n·m) 次字符串比较），回溯阶段只需要查表。死路在出生前 就被标记，一步不用走。

memo 是现场模式 ——自顶向下，需要才算。死路必须走进去 ，把整棵子树算到头、得到一个空产出，才知道它是死的，然后缓存这个”空”让后来者跳过。77 次，全是”走进去确认死亡”的成本。

公平地说，77 依然是个好数字——417 万压到两位数，六个数量级，memo 本身是有效的。只是预计算把消灭死路的时机提前到了搜索开始之前，1 次对 77 次，先知完胜现场。

3.2 活路重复：memo 赢（6 vs 7）

catsanddog 的两条解——cat sand dog 和 cats and dog——都在位置 7 汇合（一个走 cat sand 到 7，一个走 cats and 到 7）。位置 7 之后的子树（dog），两条路都要走一遍 ：

can2 版：can2[7] = true，两条路都放行，7→10 的子树重搜两次
memo 版：第一次算完 memo[7] = ["dog"]，第二次到达直接拿产出，子树一步不进

can2 缓存的是”能不能 “（bool），同一个位置的可行性查十次还是那一个 true，帮不了第二次搜索；memo 缓存的是”所有句子 “（完整产出），第一次的搜索成果第二次直接复用。重复的活路越多，这个差距越大。

3.3 合体：各取所长

判据一句话：确定性剪枝用预计算，重复子问题用缓存 。两个判据不冲突，合体即可：

  
// 合体版核心：can2 剪死路 + memo 缓存活路产出
for _, w := range wordDict {
    end := start + len(w)
    if end <= len(s) && s[start:end] == w && can2[end] { // 死路在出生前消灭（预计算）
        for _, tail := range dfs(end) {                  // 活路的重复子树只算一次（memo）
            ...
        }
    }
}

死路多的场景吃 can2 的红利，活路重复多的场景吃 memo 的红利，两头都不亏。回溯三立下的”记忆化判据”（缓存结论、让后来者跳过子树展开）和 DP 的”重叠子问题”（多条路径坍缩到同一状态）——这两句话描述的本是同一件事，在这里正式会师 。

4. 从 417 万到 1：死刑犯的终局

把 22a+b 用例的四代实现放在一张表里：

版本	memo 里存的是什么	调用次数
纯回溯	—	4,169,729
死刑一	`map[int]string`（选了哪个词）	锁死分支，只出一个方案
死刑二	`map[int][]string`（候选词列表）	4,169,729（一个数字都没差）
memo 完全体	`map[int][]string`（完整产出）	77
can2[end] + 回溯	`[]bool`（可行性表）	1

从 417 万到 1，中间隔着一条完整的进化链：缓存选择（锁死分支）→ 缓存候选（无效，子树照样重搜）→ 缓存结论（有效，六个数量级）→ 预计算可行性 （极致，搜索树死在根上）。

每一代的差别，只在”缓存里放的是什么”——同一个 map[int][]string，值从”词的列表”换成”句子的列表”，就是 417 万和 77 的差别。数据结构一字不改，语义换血，性能换天。 这是”缓存结论，不缓存选择”判据最硬的一次实证。

5. 全系列地图：从决策树到状态机的一个圆

140 毕业，六级 DP 全部收官。把两个系列摊开看：

回溯三篇（决策树上走路）              DP 七篇（把树折叠成表）
─────────────────────              ─────────────────────
一、IP 题与万能模板                   入门、打家劫舍三课（选/不选 → 状态）
二、五个坑与验收                      双序列三课（继承、计步、断链）
三、记忆化、状态设计、N 皇后    ──→    背包两课（贪心之死；min哨兵、计数、组合排列）
                                    区间 DP（最后戳谁）
                                    状态机 DP（股票家族五题）
                                    终章 140（DP 的表 + 回溯的路）← 合龙点

两个系列的关系，用一个画面说清：回溯是决策树上走路，DP 是把整棵树折叠成一张表 。同一棵树——回溯亲历每条路径，DP 发现”不同路径会坍缩到同一状态”，于是不再走路，改为按状态填表。140 是合龙点：DP 的表（can2）决定回溯走哪条路，回溯的路（backtrack）产出 DP 表回答不了的方案列表。判据会在哪个状态坍缩，表就折到哪；方案要在哪条路上收集，路就得真的走。

5.1 跨系列的暗线盘点

十篇文章里，有几条暗线反复现身，收官时值得点名：

折叠判断（五次登场） ：131 回文表 → 140 can/can2 → 464 位掩码 → 51 对角线标记 → 本篇 can2[end] 的 1 次调用。载体每次不同，原理同一：约束的判断与路径无关，就可以预计算，把 O(n) 甚至 O(指数) 折叠成 O(1) 查表 。

“不动”分支 ：股票家族五现（max 的左半边：继续持有/继续空仓）、双序列三现（继承：dp[i-1][j]、dp[i][j-1]）、本篇 can 表的 ||（已经 true 就不再试）。同一个幽灵——“什么都不做”是一个合法且常常最优的决策 ，它永远排在转移的第一个参数，永远最容易被忘掉。

发明局部规则回避枚举（同一个元模式，多件马甲） ：博弈的”选最小”、139 的漫游匹配、300 的 maxV 摘要、416 的”放差值小的一边”、股票的落袋贪/跳天/改对迁就错。每一次的死法都一样：用运行时的局部决定替代结构里的完整枚举，一遇变体就死 。而每一次翻车，都反过来加深了同一条认知：DP 的本质是两个分支都算，回溯的本质是两个分支都走。

用例巧合家族 ：第一个用例永远测不出你的错——121 的 [7,1,5,3,6,4] 藏住全局最小/前缀最小的差别、188 的零值白送、416 的 max 恰好等于 sum/2、本篇 catsanddog 的两条路恰好都通。自测用例要么加边界（单元素、空、全重复），要么换数字重算 ——这是从第一篇用到终章的自保动作。

互证闭环 ：手推表和代码是同一张图纸的两份拷贝。188 七轮拉锯的解法（对着机器打印誊写、逐格标注 max 哪边赢）在 416 又用了一次（打印 12 行 dp 表逐格对手推）。图纸乱了，找机器要一份新的 。

5.2 给未来的自己：拿到题的 30 秒

三层漏斗（回溯三）+ 六级地图（本系列），合成最后一张速查表：

题面信号	去处
要所有方案	回溯（+ 可行性表剪枝：can2[end]）
要能不能 / 多少种 / 最优值	DP
两串比对着推	双序列（继承 + 计步 + 断链）
选与不选凑一个总量	背包（01 正序、完全倒序；组合外物品序、排列外背包序）
两端往中间收缩	区间 DP
同一天/同一步有几种处境	状态机（禁令写在转移边上）
n ≤ 20 且要枚举	回溯 + 记忆化（先问：状态和路径分离吗）
超时了	先问缓存的是什么：选择（死刑）、候选（无效）、结论（有效）、可行性表（极致）

总结

终章的三句话：

缓存什么，比缓存本身重要一百倍。 同一个 map[int][]string，存候选词列表是 417 万次，存完整产出是 77 次，再叠一张 can2 是 1 次。三次死刑一次终局，全部的差别都在”值里放的是什么”——缓存选择锁死分支，缓存候选省零钱，缓存结论省子树，缓存可行性省整棵树。

“回答问题”的函数才配被缓存。 void 回溯的产出散落在 path 和 res 里，返回值空空——没有东西可缓存。给递归一个返回值，让它回答一个由参数完全决定的问题，memo 才有落点。打家劫舍走过的演化链（回溯 → 有返回值的递归 → memo → DP 数组），在字符串世界原样重演——那是一般道路，不是个例技巧。

回溯和 DP 是同一棵树的两种走法。 回溯亲历路径，DP 折叠状态。多数题只需要其中一种；140 这种”可行性用 DP、方案用回溯”的合体题，逼着两套装备同时上场——也把两个系列焊成了一个圆。从 IP 题的第一行模板代码，到 can2[end] && 这一个条件，决策树长成了状态机，走路的人学会了填表。

十篇写完，最大的感受和回溯三收官时一致，但更深了一层：错误不是学习的代价，错误就是学习本身 。417 万次调用、1GB 栈溢出、七轮手推拉锯、三次 memo 死刑——每一条翻车记录最后都变成了判据、口诀或速查表的一行。这个系列里没有一篇是”看懂题解写出来的”，全是”撞墙撞出来的”。以后还需要继续努力。加油！

参考资料

Golang, 算法, 算法讲解, 单词拆分多解法

本文由作者按照 CC BY 4.0 进行授权

【算法】动态规划第七篇（终章）：单词拆分 II——缓存结论的完全体，与两个系列的合龙

摘要

1. 修复：can2[end]——死路不许迈步

1.1 一个冷知识：can 表算了，但没用

2. memo 完全体：缓存”从这出发的所有句子”

3. 两条路线实测：预计算 vs 惰性，各有主场

3.1 死路海洋：can2 碾压（1 vs 77）

3.2 活路重复：memo 赢（6 vs 7）

3.3 合体：各取所长

4. 从 417 万到 1：死刑犯的终局

5. 全系列地图：从决策树到状态机的一个圆

5.1 跨系列的暗线盘点

5.2 给未来的自己：拿到题的 30 秒

总结

参考资料

1. 修复：`can2[end]`——死路不许迈步