算法题卡住时，如何建立正确基线

我在算法面试中常卡在建模这一步。知道“先想暴力解，再优化”，面对具体题目时，却说不清暴力解究竟在枚举什么。题面读过几遍，脑子里仍然只有故事和几个算法名称，写代码时就容易停住。

我想练习的是：即使没认出题型，也能把所有可能性组织起来，建立一个完整的正确基线。为此，每道题都沿着下面的顺序推进：

读懂约束 → 表示候选解 → 系统枚举 → 确认正确性 → 计算代价 → 针对瓶颈优化 → 验证假设。

这里的“正确基线”可以暂时很慢。它说明问题已被建模，算法逻辑已经完整；是否满足时间和空间限制，需要另算。面试里最终仍要争取给出可提交的实现，但先建立基线，能避免把所有时间耗在尚未成形的最优解上。

这套流程也已整理进算法拆解训练台。可以先读下面的推导，再选一道陌生题，逐步记录自己的思路。

把题面翻译成对象、选择、约束和目标

读题后，先补完整一句话：

给定 ______，我要在 ______ 中选择或构造 ______，满足 ______，最终返回 ______。

例如，统计数组中和为 $k$ 的非空连续子数组数量，可以翻译为：给定整数数组，枚举所有非空连续区间，筛选区间和等于 $k$ 的区间，返回区间数。

候选对象和合法条件分别是：

(l,r),\qquad 0\le l\le r<n

\sum_{i=l}^{r}a_i=k

输出是一个整数，搜索的对象却是一对端点。同样，“最少操作次数”背后评价的是一串操作序列，“最大收益”背后评价的可能是一组选择方案。找到输出背后的方案，才能决定怎样枚举。

读题时，优先检查会改变推导的条件：是否必须连续，是否允许重复使用元素，是否存在负数，能否改变顺序，要求恰好满足还是至少满足，以及返回一个解、所有解还是方案数。还要确认输入规模和无解时的约定。

这些条件参与算法成立的理由。例如，原数组中的连续区间依赖原来的相邻关系；先排序就会改变问题。

这一步完成时，应能用两三句话准确复述输入、约束和目标。

用变量表示一个候选解，或定义完整状态

“先想暴力”还要继续问：一个候选解由什么组成，用哪些变量能表示？

候选解能直接表示时，先列出变量和范围：

候选对象	表示方式	直接枚举
一对不同位置	$(i,j)$	枚举 $i<j$
一个连续区间	$(l,r)$	枚举左右端点
一个子集	每个元素选或不选	枚举选择组合
一个排列	每个位置放哪个元素	逐位置尝试未使用元素
一种切分方案	分割点	逐步枚举下一个分割点
一串操作	状态与下一步动作	从初始状态展开搜索

基线的结构应当能写成：

生成所有必要的候选
检查每个候选是否合法
根据目标计数、取最值，或返回方案

如果完整方案不好一次表示，就一次决定一步：当前局面有哪些合法选择？为了确定这些选择及其效果，必须保留哪些信息？

这就是定义状态。可以用一个对照来检查它是否充分：

两段不同历史压缩成同一个状态后，它们之后允许的选择，以及执行选择后的效果，是否一致？

如果不一致，就需要补信息。迷宫里是否拿到钥匙会影响能不能开门，状态就不能只有当前位置。先把状态定义充分，再考虑压缩。MIT 的动态规划讲义也把扩展或约束子问题作为补足信息的方法。MIT 6.006：动态规划子问题

650：从操作序列推到一个有限搜索

LeetCode 650「两个键的键盘」：屏幕最初有一个 A，允许“复制全部”和“粘贴”，求恰好得到 $n$ 个 A 的最少操作数，范围为 $1\le n\le1000$ 。

即使暂时没有发现数学规律，也可以直接按题意组织搜索。

屏幕相同，不代表后续问题相同

搜索对象是一串操作序列。当前状态需要记录屏幕字符数 $s$ 和剪贴板字符数 $c$ ：

\text{state}=(s,c),\qquad \text{start}=(1,0)

只记录 $s$ 会丢信息。屏幕都是 4 个字符时，剪贴板有 1 个和有 2 个，下一次粘贴分别得到 5 个和 6 个字符。两段历史的未来效果不同，不能合并。

两个合法转移直接来自题面：

\text{复制全部：}(s,c)\rightarrow(s,s)

\text{粘贴：}(s,c)\rightarrow(s+c,c)

目标是到达任意 $s=n$ 的状态，最终剪贴板的内容不影响答案。

每次转移的代价都是 1，因此可以用 BFS，按操作次数从小到大扩展。BFS 求无权图的最少边数；这道题的一条边对应一次操作，所以最少边数就是最少操作数。MIT 6.006：广度优先搜索

先说明搜索为什么会结束

屏幕字符数不会减少。一旦 $s>n$ ，就无法回到目标，可以排除这类状态。剪贴板来自复制操作，因此在保留的状态中也有 $0\le c\le n$ 。

复制已经相同的内容、粘贴空剪贴板，都可能回到原状态。用完整的 $(s,c)$ 去重即可避免反复探索。BFS 第一次到达一个状态时已经使用了最少操作数；后续再到达同一状态，不会提供更便宜的后续方案。

from collections import deque


def min_steps(n: int) -> int:
    if n < 1:
        raise ValueError("n 必须是正整数")

    queue = deque([(1, 0, 0)])  # 屏幕、剪贴板、操作数
    seen = {(1, 0)}

    while queue:
        screen, clipboard, steps = queue.popleft()
        if screen == n:
            return steps

        next_states = (
            (screen, screen),
            (screen + clipboard, clipboard),
        )

        for next_screen, next_clipboard in next_states:
            if next_screen > n:
                continue

            state = (next_screen, next_clipboard)
            if state in seen:
                continue

            seen.add(state)
            queue.append((next_screen, next_clipboard, steps + 1))

    return -1

这段代码覆盖每个状态的合法动作，排除了无法到达目标的超限状态，并且每个完整状态最多入队一次。状态数有一个宽松的 $O(n^2)$ 上界，每个状态最多生成两个转移；按哈希集合操作平均 $O(1)$ 估算，时间和额外空间均有 $O(n^2)$ 上界。实际可达状态不一定填满这个范围。

此时已经有一个完整基线：操作序列、完整状态、合法转移、有限范围和等代价最短路，都有了明确含义。

状态简化需要解释信息为什么可以丢掉

有了搜索基线，再观察最后一次复制。假设那时屏幕有 $d$ 个字符，之后只粘贴，直到得到 $n$ 个字符。于是 $d$ 必须整除 $n$ ；这个阶段的一次复制和 $n/d-1$ 次粘贴，共花费 $n/d$ 次操作。

令 $dp[m]$ 表示得到 $m$ 个字符的最少操作数。 $m>1$ 时枚举最后一次复制的位置，得到：

\begin{aligned} dp[1]&=0\\ dp[m]&=\min_{\substack{d\mid m\\1\le d<m}} \left(dp[d]+\frac{m}{d}\right) \end{aligned}

依赖项 $d<m$ ，因此可以按字符数递增计算。这里能够只保留屏幕数量，是因为新阶段从复制开始，先前的剪贴板会被覆盖。状态简化由阶段定义支撑。

检查这类动态规划时，可以沿着子问题含义、转移、依赖顺序、边界、原问题答案和复杂度逐项说明。MIT 6.006：动态规划子问题

解释不漏、不误算和终止，再计算总代价

基线写出来以后，至少回答三个问题：

覆盖性：所有合法方案为什么都能被枚举到？区间由唯一端点对表示，操作序列的每一步落在已列出的合法动作中。
合法性与计数准确性：非法方案如何排除，是否重复计数，状态是否遗漏影响未来的信息？
终止性：递归规模如何缩小，图搜索如何限定范围和去重，剪枝为什么安全？

去重策略还要跟目标一致。650 求最少操作数，可以保留完整状态的最早到达；统计方案数时，不同路径可能贡献不同方案，合并状态后需要保留它们的计数贡献。

总代价可以先拆成：

总工作量 ≈ 候选或状态数量 × 单次处理代价。

区间有 $O(n^2)$ 个，如果每次都重新遍历区间求和，最坏总时间会达到 $O(n^3)$ 。两层外部循环并不能直接证明 $O(n^2)$ ；还要看循环内部做了什么。

把最大输入规模代入估算，能判断主要瓶颈。比如 $10^5$ 的平方是 $10^{10}$ ，二次枚举的工作量已经很大；具体能否通过仍取决于单次操作、语言和时间限制。空间也要单独计算，包括状态表、队列、递归栈和复制的数据。

优化时，指出要省掉哪一部分工作

有了基线，优化就有了对象。先问最贵的一步是什么，再找能替代它的依据：

基线中的浪费	需要回答的问题	可以考虑的方向
同一批元素反复求和、统计	相邻结果能否增量更新，能否预处理？	滚动维护、前缀和
每次扫描历史数据找某个值	查询条件是什么，能否提前建索引？	哈希表、查找结构
不同路径反复解决同一个剩余问题	哪些历史对未来已没有区别？	记忆化、动态规划
大量候选不可能成立	能否证明一整类候选可以排除？	剪枝、双指针
逐个尝试一段答案范围	可行性是否有明确的真假分界？	二分答案
每步只选择当前最好的	能否证明这个选择保留全局最优解？	贪心与正确性论证

表中的算法名称是方向，成立理由在中间一列。最值、连续、有序等描述，本身不足以证明动态规划、滑动窗口、二分或贪心适用。

560：从端点枚举变成历史数量查询

LeetCode 560「和为 K 的子数组」要求统计和为 $k$ 的非空连续子数组，数组允许负数，长度最多为 $2\times10^4$ 。

先建立正确基线。固定左端点，右端点逐步右移，同时维护区间和：

def subarray_sum_brute(nums: list[int], k: int) -> int:
    answer = 0
    for left in range(len(nums)):
        total = 0
        for right in range(left, len(nums)):
            total += nums[right]
            if total == k:
                answer += 1
    return answer

每个非空区间对应唯一的端点对，所以不会遗漏或重复计数。候选数为 $n(n+1)/2$ ，每次增量求和花费 $O(1)$ ，时间为 $O(n^2)$ ，额外空间为 $O(1)$ 。在题目长度上限，候选区间约有两亿个，值得继续减少枚举工作。

接下来固定右端点，问内层循环究竟在寻找什么。定义前缀和：

P[0]=0,\qquad P[r]=\sum_{i=0}^{r-1}a_i

这里改用半开区间 $[l,r)$ ，它的和为 $P[r]-P[l]$ 。合法条件可以改写为：

\begin{aligned} P[r]-P[l]&=k\\ \Longleftrightarrow\quad P[l]&=P[r]-k \end{aligned}

于是，固定右端点 $r$ 时，只需回答：此前出现过多少个值等于 $P[r]-k$ 的前缀和？

用哈希表保存前缀和出现次数，可以把逐个检查左端点换成一次数量查询：

def subarray_sum(nums: list[int], k: int) -> int:
    frequency = {0: 1}
    prefix = 0
    answer = 0

    for x in nums:
        prefix += x
        answer += frequency.get(prefix - k, 0)
        frequency[prefix] = frequency.get(prefix, 0) + 1

    return answer

每个元素触发常数次哈希操作。在哈希操作平均常数时间的假设下，总时间为 $O(n)$ ，额外空间为 $O(n)$ ；这个分析使用平均复杂度假设。

表里保存什么，决定了更新顺序

查询时的不变量是：frequency 记录当前右端点之前，所有前缀和的出现次数。

因此必须先查询，再插入当前前缀和。若先插入， $k=0$ 时会把当前前缀减去自身形成的空区间算进去。初始的 {0: 1} 则代表空前缀，让从数组开头开始的区间也能被计数。

题目求数量，表里就存次数。例如 [0, 0]、 $k=0$ 的答案是 3；只存是否存在，会丢掉重复前缀的贡献。如果目标改为最长区间，应保存合适前缀的最早位置；改为最短区间，则关注最近的位置，并仍保持 $l<r$ 。结构里存什么，由需要回答的查询决定。

负数也给出了一个能挑战窗口假设的反例：[4, -1]、 $k=3$ 。如果看到当前和 $4>3$ 就删掉左端的 4，会错过整个合法区间。后续元素可能降低区间和，所以“和太大就缩窗口”在这里没有安全依据。

用不变量和反例检验推导

编码前先写清变量或数据结构的含义。例如：

查询时，frequency 记录当前右端点之前的前缀和次数。
seen 记录已入队的完整状态，每个状态最多入队一次。

有了这些定义，“先查询还是先插入”“入队前还是出队后标记”“去重键包含什么”，都能回到含义判断。

测试需要挑会改变结论的输入。560 可以用下面四个例子：

输入	预期	检查什么
`[3]`， $k=3$	1	单元素合法区间
`[1, 2]`， $k=10$	0	无解
`[0, 0]`， $k=0$	3	重复前缀与空区间处理
`[4, -1]`， $k=3$	1	负数是否破坏窗口假设

练习时保留基线，在大量小输入上对比优化版本的输出，也能帮助发现反例。对拍提供检查线索，正确性理由仍要解释。

还可以主动修改一个条件：正数改为允许负数，求数量改为求最长，每次操作代价 1 改为不同代价。然后指出原推导的哪一步需要重做。

每道题分两轮，提示只给当前缺的那一步

第一轮完成问题、对象、枚举、正确和代价，先建立能执行的正确基线。第二轮再完成优化与验证，说明最贵的工作在哪里、替换它的依据是什么。

不必每次都把暴力代码完整写一遍。面试时先讲清基线；已经推导出可靠优化时，可以直接实现优化版本。练习记录要保留推导，便于事后定位究竟卡在候选表示、状态信息、合法转移还是优化证明。

训练台按这七步记录文字。连接本地训练服务后，可以把语音转写到当前栏目，也可以调用本地 Codex 诊断。逐栏诊断检查当前步骤，整题诊断在确认思路后进行。反馈会区分已说明、待补充、存在漏洞和尚未开始，寻找最早阻塞后续推导的缺口；空白和明确的错误推理会分别处理。

卡住时，提示也沿着缺口推进：候选对象是什么，状态是否少了信息，下一步有哪些选择，哪里重复计算，某次优化为什么安全。获得当前这一级提示后，尝试自己补出对应产物，再继续下一步。

最终，每道题可以保存成一张解题卡：

问题：输入、约束、输出是什么？哪些条件会改变解法？
对象：候选解或完整状态怎样表示，变量范围是什么？
枚举：怎样生成所有必要候选或合法动作，并更新答案？
正确：为什么不漏、不误算，为什么一定终止？
代价：候选或状态有多少，每个处理多贵，额外空间多少？
优化：最贵的工作在哪里，省掉它的依据是什么？
验证：关键不变量是什么，哪个反例最可能击穿假设？

下次遇到陌生题，先试着写出“对象”和“枚举”两栏。能明确一个候选解怎样被生成，再判断它是否合法，就有了继续推导的起点。