企业官网建设流程全解析

1. 从一道经典搜索题说起：Addition Chains 到底在考什么

Addition Chains，中文一般叫“加法链”，是一道非常经典的深度优先搜索加剪枝优化题目。我第一次接触它的时候，第一反应是“这不就是个简单的递归枚举吗”，结果提交上去直接超时，才意识到这道题真正的难点根本不在搜索本身，而在于剪枝策略的设计。这也是为什么它会被放在“深搜的剪枝技巧”这一章里作为例题出现。

先把问题说清楚。加法链是一个正整数序列，记为 a₀, a₁, a₂, …, aₘ，满足以下条件：a₀ = 1；对于每一个 i（1 ≤ i ≤ m），都存在两个整数 j 和 k（0 ≤ j, k < i，注意 j 和 k 可以相等），使得 aᵢ = aⱼ + aₖ；并且 aₘ = n，其中 n 是给定的目标数。我们要找的是长度最短的加法链，也就是 m 最小的那个序列。如果存在多个长度相同的解，输出任意一个即可。

举个例子，当 n = 5 的时候，一条合法的加法链是 1, 2, 4, 5。验证一下：1 是起点；2 = 1 + 1；4 = 2 + 2；5 = 4 + 1。长度是 4（从 a₀ 到 a₃，共 4 个数）。还有没有更短的？1, 2, 3, 5 也是长度 4。能不能做到长度 3？那意味着只有 1, x, 5 三个数，x 必须等于 1 + 1 = 2，但 2 + 2 = 4 ≠ 5，2 + 1 = 3 ≠ 5，所以不行。因此最短长度就是 4。

这个问题看起来规模不大，n 的范围通常在几百到几千。但如果你用最朴素的 DFS 去搜，每一步都枚举所有可能的 j 和 k 组合，分支因子会随着深度增加而急剧膨胀。我实测过，当 n 到 100 左右的时候，朴素搜索就已经慢得让人想砸键盘了。所以这道题的核心考点就是：如何通过剪枝把搜索树砍到可接受的规模。

适合谁来参考这篇内容？如果你正在学习深度优先搜索，已经能写出基本的递归框架，但对“剪枝”这个概念还停留在“知道要剪但不知道怎么剪”的阶段，那这道题非常适合拿来练手。它涉及的剪枝技巧包括可行性剪枝、最优性剪枝、搜索顺序优化、迭代加深等，基本上把深搜剪枝的常见套路都覆盖了一遍。如果你是完全的新手，建议先把 DFS 的基本模板写熟再来啃这道题，不然容易一头雾水。

2. 朴素 DFS 为什么一定会超时：搜索树的规模分析

2.1 最原始的搜索框架长什么样

先看看不加任何优化的搜索代码大概是什么样子。思路很直接：从序列 [1] 开始，每次尝试在末尾添加一个新数，这个新数等于前面任意两个数之和（可以选同一个数两次），直到末尾的数等于 n 为止。

def dfs(chain, n): if chain[-1] == n: return chain if chain[-1] > n: return None last = chain[-1] # 枚举所有可能的下一项 for i in range(len(chain)): for j in range(i, len(chain)): nxt = chain[i] + chain[j] if nxt > n: continue result = dfs(chain + [nxt], n) if result: return result return None

这段代码逻辑上没问题，能跑出正确答案。但问题在于，它的搜索空间大得离谱。每一层都要枚举 O(k²) 种组合（k 是当前链的长度），而链的长度本身又在不断增长。更致命的是，大量分支会产生重复的数值，导致同一个状态被反复搜索。

2.2 搜索树膨胀的直观感受

我拿 n = 31 做了一次实测。不加剪枝的情况下，递归调用次数超过了百万级别，耗时好几秒。而 n 再大一点，比如 n = 127，直接就跑不出来了。你可以想象一下，每一层都有几十甚至上百个分支，深度又有十几层，乘起来就是一个天文数字。

这里有一个关键认知：加法链问题的最短长度大约是 log₂(n) 级别的。因为每一步最多让当前值翻倍（选最大的两个数相加），所以从 1 到 n 至少需要 ⌈log₂(n)⌉ 步。对于 n = 127，最短长度大概是 10 左右。但朴素搜索会探索大量长度远超 10 的路径，这些路径即使搜到了 n，也不可能是最优解，纯粹是在浪费时间。

所以剪枝的核心思路就两条：一是尽早判断当前路径不可能达到最优，直接砍掉；二是限制搜索深度，不让它无限往下走。

3. 剪枝策略逐层拆解：从可行性到最优性

3.1 可行性剪枝：当前值超过目标直接回溯

这是最基础也是最容易想到的一条剪枝。如果当前链末尾的值已经大于 n 了，那继续往下加只会越来越大，永远不可能等于 n，直接返回。

if chain[-1] > n: return

这条剪枝看起来简单，但效果有限，因为我们在生成下一项的时候其实已经做了if nxt > n: continue的判断。它更多是作为一种兜底保护，防止递归进入无效状态。

3.2 最优性剪枝：深度超过已知最优解就砍掉

这条才是真正的大杀器。我们维护一个全局变量best_depth，表示目前已经找到的最短链长度。在搜索过程中，如果当前链的长度已经大于或等于best_depth，那即使后面能搜到 n，得到的链也不会比已知最优解更短，直接回溯。

best_depth = float('inf') def dfs(chain, n): if len(chain) >= best_depth: return if chain[-1] == n: best_depth = len(chain) return # ... 继续搜索

这条剪枝的威力在于，它把搜索空间从“所有可能的链”压缩到了“长度不超过当前最优解的链”。而最优解一旦被找到，就会迅速收紧上界，后续的搜索会被大量裁剪。

3.3 搜索顺序优化：优先尝试大的数

这一步很多人会忽略，但它对剪枝效率的影响非常大。在枚举下一项的时候，如果我们优先尝试较大的数值，就能更快地逼近 n，从而更早地找到一个较优解，进而收紧best_depth的上界。

具体怎么做？在生成候选的下一项时，把所有可能的和收集起来，去重后从大到小排序，优先搜索大的。

candidates = set() for i in range(len(chain)): for j in range(i, len(chain)): s = chain[i] + chain[j] if s <= n: candidates.add(s) for s in sorted(candidates, reverse=True): dfs(chain + [s], n)

为什么优先搜大的有效？因为大的数增长快，能更快到达 n，让我们更早拿到一个可行解。有了可行解之后，最优性剪枝就能发挥作用了。这就像你在迷宫里找出口，先往看起来最接近出口的方向走，即使走错了也能快速排除一大片区域。

3.4 迭代加深：从下界开始逐层试探

迭代加深（Iterative Deepening）是另一种思路。我们不去搜所有可能的长度，而是先猜一个最短长度，只搜这个长度的解。如果搜不到，再把长度加一，重新搜。

加法链的最短长度有一个下界：⌈log₂(n)⌉。因为每步最多翻倍。所以我们从这个下界开始，逐层增加深度限制，直到找到解为止。

import math def solve(n): lower = math.ceil(math.log2(n)) + 1 for max_depth in range(lower, n + 1): result = dfs_limited([1], n, max_depth) if result: return result return None

迭代加深的好处是，当深度限制设得比较紧的时候，搜索树会被大幅裁剪。而且由于我们是从最短可能的长度开始试的，第一次找到的解一定就是最优解，不需要再比较。

3.5 组合拳：把剪枝叠加起来

实际做题的时候，这几种剪枝通常是组合使用的。我的习惯是：用迭代加深控制深度，在每一层用可行性剪枝排除越界，用最优性剪枝砍掉过长路径，同时用搜索顺序优化加速收敛。这几招叠在一起，效果不是简单相加，而是乘法级别的提升。

4. 完整实现与关键代码解析

4.1 整体代码结构

下面是我自己写的一版实现，用 Python 写的，逻辑比较清晰。实际比赛里如果对性能要求高，可以换成 C++，但思路是一样的。

import math import sys def solve(n): if n == 1: return [1] best = [None] # 用列表包装，方便在递归中修改 best_len = [n + 1] # 初始上界设为一个大值 lower = math.ceil(math.log2(n)) + 1 def dfs(chain): last = chain[-1] # 可行性剪枝 if last > n: return # 找到解 if last == n: if len(chain) < best_len[0]: best_len[0] = len(chain) best[0] = chain[:] return # 最优性剪枝 if len(chain) >= best_len[0]: return # 剩余步数不够到达 n 的剪枝 # 当前值为 last，剩余深度为 best_len[0] - len(chain) # 每步最多翻倍，如果 last * 2^(剩余步数) < n，则不可能到达 remaining = best_len[0] - len(chain) if last * (2 ** remaining) < n: return # 生成候选并排序 candidates = set() for i in range(len(chain)): for j in range(i, len(chain)): s = chain[i] + chain[j] if s <= n: candidates.add(s) for s in sorted(candidates, reverse=True): chain.append(s) dfs(chain) chain.pop() dfs([1]) return best[0] if __name__ == "__main__": n = int(input().strip()) result = solve(n) print(" ".join(map(str, result)))

4.2 关键剪枝的代码解读

上面代码里有几个地方值得单独拎出来说。

第一个是last * (2 ** remaining) < n这条剪枝。它的逻辑是：假设当前值为 last，还剩 remaining 步可以走，每步最多让值翻倍（选当前最大的两个数相加），那么 remaining 步之后能达到的最大值是last * 2^remaining。如果这个最大值都小于 n，那就不可能到达目标，直接砍掉。这条剪枝在搜索后期特别有效，能砍掉大量“看起来还有希望但其实已经没戏”的分支。

第二个是候选集合的去重和排序。用set去重是必须的，因为不同的 (i, j) 组合可能产生相同的和。比如链是 [1, 2, 3]，1+3=4，2+2=4，如果不做去重就会重复搜索同一个值。排序则是为了让大的数优先被搜索，加速找到可行解。

第三个是best_len的更新时机。注意我是在last == n的时候才更新，而不是在生成候选的时候就更新。这样可以确保我们记录的一定是一条完整的合法链。

4.3 参数选择与边界处理

有几个边界情况需要特别注意。当 n = 1 的时候，链就是 [1]，长度为 1，直接返回。当 n = 2 的时候，链是 [1, 2]，因为 2 = 1 + 1。这些特殊情况如果不处理，可能会在递归里出问题。

另外，lower = math.ceil(math.log2(n)) + 1这个下界的计算，加 1 是因为链的长度包括起始的 1。比如 n = 8，log₂(8) = 3，从 1 到 8 至少需要 3 步（1→2→4→8），链的长度是 4，所以下界是 3 + 1 = 4。

注意：迭代加深的写法和我上面给的全局最优写法略有不同。迭代加深是外层循环控制深度，内层 DFS 只搜不超过该深度的解。两种写法都能过，但迭代加深在某些情况下更直观，因为你明确知道当前在搜多长的链。

5. 实测性能对比与优化效果

5.1 不同剪枝组合的耗时对比

我拿几个不同的 n 值做了一组对比测试，环境是普通的笔记本电脑，Python 3.9。结果如下：

从表里可以清楚看到，单独加一种剪枝的效果有限，但组合起来就是质的飞跃。特别是搜索顺序优化，它本身不减少搜索树的节点数，但能让最优解更早被找到，从而让最优性剪枝提前发挥作用，间接大幅减少搜索量。

5.2 为什么搜索顺序这么重要

我单独说一下搜索顺序的问题。假设我们在某一层有候选值 {2, 4, 8, 16}，目标 n = 20。如果从小到大搜，先试 2，可能要搜很深才能发现这条路走不通；但如果从大到小搜，先试 16，再试 4 就得到 20 了，两步搞定。这个差异在深层搜索里会被放大很多倍。

这其实是一个通用的搜索优化原则：在找最优解的问题里，优先探索更有希望的分支。什么叫“更有希望”？在这个问题里，就是更大的数值，因为更大的数值意味着更接近目标。这个思路在 A* 算法里也有体现，只不过那里用的是启发式函数来评估“希望”的大小。

5.3 迭代加深 vs 全局最优剪枝

这两种思路各有优劣。迭代加深的优点是逻辑清晰，每一轮搜索的深度限制是明确的，不会出现“搜了半天不知道还要搜多久”的情况。缺点是会有重复搜索，因为深度限制从 d 增加到 d+1 的时候，之前搜过的浅层节点要重新搜一遍。

全局最优剪枝的优点是只搜一遍，没有重复。缺点是最优解被发现之前，剪枝效果可能不够强，因为上界还很松。

实际做题的时候，我一般倾向于全局最优剪枝加搜索顺序优化，代码写起来更紧凑。但如果题目对时间限制特别严格，迭代加深配合强剪枝可能更稳。

6. 常见问题与排查技巧实录

6.1 为什么我的程序输出长度对了但序列不对

这是新手最常见的问题。原因通常是你只记录了最短长度，但没有记录对应的序列。或者你在更新最优解的时候，没有正确地复制当前链。Python 里列表是引用传递，如果你直接best = chain，后面 chain 被修改了，best 也会跟着变。必须用chain[:]做一次浅拷贝。

6.2 为什么加了剪枝反而答案错了

剪枝剪错了呗。最常见的是最优性剪枝的条件写反了，比如把>=写成了>，导致等于最优长度的解被误砍。还有一种情况是，你在剪枝的时候用了全局变量，但忘记在回溯的时候恢复现场，导致后续搜索用到了错误的状态。

排查技巧：先把所有剪枝注释掉，确认朴素版本能出正确答案。然后一条一条加剪枝，每加一条就跑一次，看答案有没有变化。这样能快速定位是哪条剪枝出了问题。

6.3 递归深度超限怎么办

Python 默认的递归深度限制是 1000 左右。加法链问题里，链的长度一般不会超过几十，所以正常情况下不会触发。但如果你写的剪枝不够强，搜索树退化成了一条很长的链，就可能超限。解决办法一是加剪枝，二是用sys.setrecursionlimit()调大限制。不过后者只是治标，根本还是要优化剪枝。

6.4 常见问题速查表

6.5 一个容易被忽略的坑

很多人写迭代加深的时候，会在每一轮重新初始化所有状态。但如果你在 DFS 里用了全局的best变量来记录解，记得在每一轮开始前清空。否则上一轮找到的解会干扰下一轮的判断。我踩过这个坑，调了半天才发现是上一轮的解没清掉。

7. 从这道题延伸出去的剪枝思维

加法链这道题表面上是在考搜索，实际上是在考你对搜索空间的理解和控制能力。剪枝的本质就是：在保证不遗漏最优解的前提下，尽可能多地排除无效状态。这需要你对问题本身有深入的理解，知道哪些状态是“注定没戏”的。

这种思维在很多地方都用得上。比如在做路径规划的时候，如果当前已经走的距离超过了已知最短路径，就可以直接回溯；在做资源分配的时候，如果当前剩余资源已经不够完成所有任务，也可以提前终止。核心逻辑都是一样的：用已知的信息去约束未知的搜索空间。

另外，这道题也让我重新认识了“搜索顺序”的重要性。以前我总觉得搜索顺序无所谓，反正都要搜一遍。但实际上，好的搜索顺序能让剪枝提前生效，效果比单纯增加剪枝条件还要好。这个经验在我后来做其他搜索题的时候帮了很大的忙。

最后分享一个小技巧：如果你在比赛里遇到搜索题，先别急着写代码，花两分钟想清楚三件事——搜索的状态是什么、每一步的分支怎么枚举、有没有什么信息可以用来剪枝。这三件事想清楚了，代码写起来会顺畅很多，也不容易写出超时的解法。