图 1：本文封面，点明题目与「贪心为什么成立」的论证要求。
先说明属性：这是一篇经典题解析，题目出自本地历史面试资料，与任何公司的当前招聘无关。题面很短：给一个正整数 n，每一步如果 n 是偶数就除以 2，如果是奇数可以选择加 1 或减 1，一直处理下去，问最少多少步能变成 1。
面试现场，面试官写完规则笑而不语。不少人第一反应是反向枚举——从 n 开始做 DFS 或 BFS，把每个奇数加 1、减 1 的两条分支都走一遍取最小值。能算对，但分支指数膨胀，n 一大就超时。面试官真正想等的是：能不能不枚举，O(log n) 一步一条路直接走到底？
核心结论：可以，用贪心。
规则只有三行：偶数直接除 2；奇数如果等于 3 或者模 4 余 1，就减 1；其余奇数（模 4 余 3）加 1。沿这条规则走，每步都是局部最优，总步数就是全局最优。
为什么偶数一定除 2？
奇数加减 1，本质都是在为下一步的除法铺路。偶数除 2，一步就把二进制长度砍掉一位；如果放着除法不用先去做加减，得先花一步把偶数变奇数，再花一步变回偶数才能除——两步干别人一步的事，永远不划算。所以「偶数必除 2」没有争议，争议全在奇数。
奇数为什么看模 4？
奇数加减 1 之后必成偶数，下一步一定除 2。真正的分歧在于除完这一次的落点：n 减 1 再除 2 得 (n−1)/2，n 加 1 再除 2 得 (n+1)/2。选对了，落点继续是偶数，白赚一次连续除 2。n 模 4 余 1 时，n−1 是 4 的倍数，能连除两次；n 模 4 余 3 时，n+1 是 4 的倍数，同样能连除两次。所以局部最优的依据一句话：让下一步多除一次 2。
唯一例外是 3。按规则它模 4 余 3 应该加 1：3→4→2→1 共三步；而减 1 只要 3→2→1 两步。终点附近「连除两次」的红利来不及兑现，所以特判。
换成二进制视角，规则更直观。
除 2 就是右移一位。偶数末尾是 0，右移没成本。奇数末尾是 1，必须先消掉：末尾只有一个 1（形如 …01）时减 1 最省；末尾连着多个 1（形如 …0111）时加 1 引发进位，一次把一串 1 全消掉。贪心成立的根子还是那句话：每一步都让二进制长度缩短得最快。
写出可运行的代码。
下面这份实现附带 14 的走查和 1 到 2000 的 BFS 对拍，用 Node.js 22.15.0 直接运行（node integer-replacement.js）即可：
'use strict';
// 贪心：偶数除 2；奇数看模 4 选加减，唯一例外是 3
function minOps(n) {
let ops = 0;
while (n > 1) {
if (n % 2 === 0) n /= 2;
else if (n === 3 || n % 4 === 1) n -= 1;
else n += 1;
ops += 1;
}
return ops;
}
// 走查：14 的最短路径
const path = [];
for (let n = 14; n > 1;) {
path.push(n);
if (n % 2 === 0) n /= 2;
else if (n === 3 || n % 4 === 1) n -= 1;
else n += 1;
}
path.push(1);
console.log('14 的路径：', path.join(' → '), '，共', path.length - 1, '步');
// 对拍：BFS 暴力枚举，验证 1..2000 内贪心结果全部正确
function bfs(n) {
const dist = new Map([[1, 0]]);
const queue = [1];
while (queue.length) {
const cur = queue.shift();
if (cur === n) return dist.get(cur);
// 反向 BFS：cur 的邻居是 2*cur（正向的除 2），以及 cur 为偶数时的 cur±1（正向的奇数加减 1）
const next = [2 * cur, ...(cur % 2 === 0 ? [cur - 1, cur + 1] : [])];
for (const m of next) {
if (m >= 1 && m <= 2 * n && !dist.has(m)) {
dist.set(m, dist.get(cur) + 1);
queue.push(m);
}
}
}
return -1;
}
let bad = 0;
for (let i = 1; i <= 2000; i++) {
if (minOps(i) !== bfs(i)) bad += 1;
}
console.log('1..2000 与 BFS 对拍完成，不一致个数：', bad);
实测输出：
14 的路径： 14 → 7 → 8 → 4 → 2 → 1 ，共 5 步
1..2000 与 BFS 对拍完成，不一致个数： 0
两千个数字与暴力 BFS 全部一致，贪心正确性有了实证。走查里 7 是个有意思的并列点：减 1 走 7→6→3→2→1、加 1 走 7→8→4→2→1 都是 4 步，贪心规则选择了后者。
图 2：贪心决策规则与二进制视角的论证。
可能的追问。
「时间复杂度多少？」每次操作至少把二进制右移一位，O(log n)。「为什么不从 1 反向贪心？」正向除法有确定性，反向的乘 2 与加减没有等价的局部判据，容易把自己绕回枚举。「n 超出普通整数范围呢？」规则只依赖奇偶和模 4，用任意精度整数照样成立，每步只看最低两位。
易错点清单。
一，对奇数无脑选减 1，在 7、11 这类数上就不是最优。二，忘记特判 3，输出 3 步而不是 2 步。三，把 BFS 当满分答案讲，没意识到面试官在等贪心论证。四，只背规则说不清「为什么看模 4」，被追问一句就露馅。
回到面试现场，建议的答题节奏：先给出「偶数必除 2」的无争议部分，再把奇数的选择归约到「让下一步多除一次 2」，点出模 4 判据和 3 的例外，最后用二进制视角收尾。贪心题的高分从来不在代码，而在「为什么局部最优就是全局最优」的论证。
你在面试里被要求证明过贪心正确性吗？是讲清楚了还是当场卡壳？欢迎分享。