算法解题手册：从候选到状态转移
候选定义答案，求解方式决定推进规则，状态记录继续求解所需的信息。
文章目录 · 11 章 · 约 16 分钟
从题面到代码，中间要确定三件事：答案如何表示、怎样找到答案、求解过程中要记住什么。这份手册沿着这条线，把问题定义、候选空间、状态和转移连起来，再用二分下界走完一次推导。
解题操作卡
拿到一道题，可以用下表记录推导。每一行的产出，都是下一步设计的依据。
| 步骤 | 要回答的问题 | 产出与决策 |
|---|---|---|
| 1. 形式化 | 给定什么？在什么范围内找什么？满足什么条件？返回什么？ | 写出一句完整的问题定义；区分合法性约束与求解目标。 |
| 2. 定义候选 | 一个完整答案如何表示？所有可能答案构成什么空间？ | 写出候选 c 与候选空间 C。 |
| 3. 确定求解方式 | 如何不遗漏地找到答案？最直接的穷举是什么？ | 先确定候选生成与检查规则；估算成本。超出要求时，寻找可跳过或复用的工作。 |
| 4. 定义状态 | 执行这一求解方式，必须记住什么？这些变量各表示什么？ | 写出 S 的变量、状态语义与应始终保持的不变量。 |
| 5. 确定初始状态 | 求解从哪里开始？ | 写出 S₀，验证它满足状态语义。 |
| 6. 设计动作与转移 | 当前能做什么？执行后如何得到下一状态？ | 写出可行动作 A(S) 和转移 S' = T(S, a, 结果)；确保状态有效且有进展。 |
| 7. 终止与返回 | 什么情况下停止？停止时答案在哪里？ | 写出终止条件和答案提取规则。 |
| 8. 核验与实现 | 会漏解、错解或无法结束吗？复杂度是否可接受？ | 验证覆盖性、转移正确性、终止性、结果正确性；再编码、测边界和优化。 |
候选决定要找什么，求解方式决定怎样找，状态记录继续求解所需的信息。
一、问题形式化：明确答案的定义
先用一句话写清问题：
给定 ______，我要在 ______ 中选择或构造 ______，满足 ______，最终返回 ______。
分别明确五件事：
- 输入：已知的数据及其性质，如非递减、非负、无环。
- 范围：答案允许来自哪里；区间边界、元素是否可重复选择。
- 候选：一个完整答案的表示形式。
- 约束与目标：什么算合法；是找任意可行解、全部解，还是最大化／最小化某个量。
- 输出：返回下标、数值、路径、方案、数量，还是不存在的标记。
例如，寻找第一个大于等于 target 的位置，可以写为：
给定非递减数组
nums和target，我要在0…n中选择一个位置i，使它成为第一个满足nums[i] >= target的有效下标；若没有这样的下标，最终返回n。
这里用 n 表示“未找到”，数组的有效下标为 0…n-1。
二、定义候选：答案长什么样
用最少的变量表示一个完整答案，然后给出候选空间 C。
| 问题 | 候选 c | 候选空间 C |
|---|---|---|
| 数组中找元素 | 下标 i | 所有合法下标 |
| 查找连续子数组 | 区间 (i, j) | 0 ≤ i ≤ j < n |
| 两数之和 | 下标对 (i, j) | 0 ≤ i < j < n |
| 选取若干元素 | 集合 B | 给定元素集合的子集 |
| 寻找路径 | 完整路径 P | 所有满足结构限制的路径 |
候选描述一个完整答案的形式；状态描述某种策略已经推进到哪里。比如查找下界时，候选是位置 i：线性扫描记录下一个待检查的位置，二分查找记录答案仍可能落入的范围。
三、确定求解方式：先穷举，再消除冗余
先回答：怎样系统地生成并检查候选，保证答案不被遗漏？
常用起点有两类：
- 直接枚举完整候选：一个下标用一层循环，两个下标用嵌套循环，子集可用位掩码。
- 逐步构造完整候选：排列、组合、路径等，通过连续决策得到完整解，典型方式是回溯。
确定暴力策略后，估算候选数与单次处理成本。若成本过高，先找出重复工作，再选择优化方向：
| 冗余在哪里 | 优化问题 | 常见思路 |
|---|---|---|
| 检查了大量不可能的候选 | 能否一次排除一批？ | 单调性与二分、剪枝、双指针 |
| 每个候选的判断太慢 | 能否复用局部统计或预处理？ | 前缀和、哈希、增量更新 |
| 相同子问题反复求解 | 能否让结果只计算一次？ | 记忆化、动态规划 |
| 生成顺序没有利用结构 | 能否换一种组织方式？ | 排序、图搜索、贪心（须证明选择安全） |
确定如何推进后，就可以据此选择需要记录的信息。策略改变时，状态也要随之复核。
四、定义状态：让求解可以继续
状态 S 是执行当前求解方式所需的信息摘要。 它要足以决定下一步如何推进、何时结束，以及如何得到答案；不必保存完整历史。
设计状态时，按顺序问：
- 进度：处理到哪个候选、哪个位置或哪个阶段？
- 剩余问题：哪些候选尚未排除，或哪个子问题尚待解决？
- 必要结果：哪些已计算信息可以避免后续重复计算？
只保留当前策略确实需要的变量。一个实用检验是：程序暂停后，只保留输入与 S，能否按既定规则继续？
给每组状态变量写出明确含义：
- 线性扫描：
S = i，表示下一个要检查的下标。 - 二分下界：
S = (l, r)，表示真正的答案仍在闭区间[l, r]内。 - 滑动窗口：
S = (l, r, sum)，表示当前窗口边界及其元素和。 - 回溯排列：
S = (path, used)，表示部分排列和已用元素。 - 背包 DP：
dp[i][c]对应“只考虑前i件物品、容量不超过c的最优值”这一子问题状态及其状态值。
不变量是状态语义中在整个求解过程中必须保持的性质。例如二分下界中的“答案始终在 [l,r] 内”。写出不变量，才能推导有依据的状态转移。
五、初始化：让状态从正确的位置出发
定义 S₀，并检验它是否满足状态语义和不变量。
例如，数组二分下界取 S₀ = (0, n)，因为第一个满足条件的位置一定在 0…n 内（n 表示不存在）。
初始值由状态语义决定。例如记录最小值时，需要选择适合后续比较的初始值；记录已处理元素的数量时，初始值通常为零。
六、动作与状态转移：定义每一步怎样推进
区分三个对象：
- 状态
S：当前已知的信息。 - 动作
a ∈ A(S)：当前允许进行的选择、检查或扩展。 - 转移
S' = T(S, a, o)：执行动作得到观察／计算结果o后，如何更新状态。
设计转移时检查三件事：动作是否合法、更新后不变量是否成立、求解是否向终止推进。
对于二分下界：
- 状态：
S = (l, r)。 - 动作：检查
mid = (l+r)//2。 - 转移：若
nums[mid] >= target，则r = mid；否则l = mid+1。
比较结果决定保留哪一侧；而选择中点，是为了尽量均衡地减少剩余候选范围。
七、终止与结果提取：明确算法何时完成
终止条件必须与状态语义对应，同时写清楚返回规则。
- 穷举：处理完全部必要候选；或满足提前结束条件。
- 二分：剩余候选范围收敛为唯一答案，例如
l == r。 - 回溯：部分解达到完整解的要求；整个搜索完成时返回汇总结果。
- 动态规划：目标子问题的值已计算完成。
还要说明算法为何能结束，例如循环变量严格前进、区间长度严格减小、递归深度有上界。
八、正确性与实现：先验证，再写代码
按以下顺序核验：
| 检查项 | 判断依据 |
|---|---|
| 覆盖性 | 所有可能影响答案的候选都被处理；跳过的候选有可证明的排除依据。 |
| 转移正确性 | 初始状态满足不变量，每次转移仍保持不变量。 |
| 终止性 | 存在严格推进且有界的进度量，算法不会无限运行。 |
| 结果正确性 | 终止时的输出满足约束和目标；最优化问题还需证明最优。 |
之后再完成实现：
- 复杂度：估算执行次数、每次操作成本、预处理和额外空间。
- 边界测试：空输入、单元素、重复元素、无解、全满足、边界位置等。
- 优化复核：策略变动后，重新检查状态、转移和正确性。
完整示例：从线性扫描推导二分下界
题目： 在非递减数组中，返回第一个 >= target 的下标；若不存在则返回 n。
| 步骤 | 推导 |
|---|---|
| 形式化 | 在位置 0…n 中寻找最小的可行下标。 |
| 候选 | c = i；C = {0, 1, …, n}。 |
| 初始求解方式 | 从左向右逐个检查，遇到第一个满足条件的位置返回；成本 O(n)。 |
| 优化依据 | 数组非递减，因此判断 nums[i] >= target 的结果呈先假后真的单调结构。 |
| 新策略 | 检查中点，每次排除不可能包含第一个可行下标的一半范围。 |
| 状态语义 | S = (l, r)，目标下标 i* 始终满足 l ≤ i* ≤ r。 |
| 初始化 | l = 0, r = n。 |
| 动作与转移 | 取 mid = (l+r)//2；满足条件令 r=mid，否则令 l=mid+1。 |
| 终止与输出 | l == r 时返回 l。 |
为统一处理“不存在”，定义单调判定 P(i)：当 i < n 时，检查 nums[i] >= target；当 i == n 时，约定 P(n) = True。于是答案为第一个使 P(i) 成立的位置。n 用作哨兵位置。循环中 l < r ≤ n，向下取整的中点满足 mid < r ≤ n，因此每次读取的 nums[mid] 都在有效下标内。
转移为什么正确？
P(mid)为真：第一个真值位置不可能在mid右边，所以答案留在[l, mid]。P(mid)为假：mid及其左侧都不是第一个真值位置，所以答案留在[mid+1, r]。- 每次更新都严格缩小
r-l；终止时l=r=i*。
def lower_bound(nums, target):
l, r = 0, len(nums)
while l < r:
mid = l + (r - l) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return lassert lower_bound([1, 3, 3, 7], 3) == 1
assert lower_bound([1, 3, 3, 7], 0) == 0
assert lower_bound([1, 3, 3, 7], 9) == 4
assert lower_bound([], 5) == 0以 nums = [1, 3, 3, 7]、target = 3 为例，状态变化如下：
检查前 (l, r) | mid | 比较结果 | 更新后的 (l, r) |
|---|---|---|---|
(0, 4) | 2 | nums[2] = 3 >= 3 | (0, 2) |
(0, 2) | 1 | nums[1] = 3 >= 3 | (0, 1) |
(0, 1) | 0 | nums[0] = 1 < 3 | (1, 1) |
最后 l == r == 1，返回第一个 3 的下标。重复元素保留在候选范围内，满足条件时继续收缩右边界，直到确定最左位置。
每轮将 r-l 至少缩小一半，时间复杂度为 O(log(n+1))（空数组直接返回），额外空间为 O(1)。
这个例子中，候选始终是下标 i。从线性扫描到二分，变化的是求解方式；为了执行新策略，状态由当前下标 i 变成了剩余范围 (l,r)。
写代码前，检查设计是否完整
一份可执行的算法设计，应能直接回答：
- 遍历／递归／队列围绕什么状态运行？
- 每一步执行什么动作，依据什么更新？
- 为什么没有丢失正确答案？
- 何时结束，答案从哪里取得？
这四点确定后，就可以把状态、动作和转移落实到代码。实现时遇到的循环边界、变量含义和更新方向，都应能回到前面的定义中找到依据。
可以在 算法训练台 中选一道题，逐步记录推导。关于如何从暴力解找到优化起点，另见 算法题卡住时，如何建立正确基线。