坏了的计算器为什么要反向贪心？目标数奇偶如何决定操作？

简化版

坏了的计算器从 startValue 正向到 target 不好贪心，反向从 target 回到 startValue 更简单。若 target 是偶数，就反向除以 2；若是奇数，就反向加 1 变偶数。直到 target <= startValue，剩下只能用减一的逆操作补齐。

详细版

正向操作是乘 2 或减 1。反向操作就是除以 2 或加 1。目标大于起点时，反向尽量除以 2 能最快缩小规模；但只有偶数能除，奇数必须先加 1 变成偶数。目标不大于起点后，正向只需要执行 startValue - target 次减 1。

时间复杂度 O(log target)，空间复杂度 O(1)。这题的核心是反向思维：把难以选择的乘 2 / 减 1，变成更明确的除 2 / 加 1。

完整版教学

一、为什么正向不好贪心

从 startValue 出发，你每步可以乘 2 或减 1。看起来应该尽量乘 2，但有时乘过头后需要多次减回来；不乘又可能太慢。

start=3, target=10
3 -> 6 -> 12 -> 11 -> 10，共 4 步
3 -> 2 -> 4 -> 8 -> 16 -> ... 更绕

正向时很难判断什么时候该乘，什么时候该减。

二、反向后操作为什么更清晰

把目标倒着变回起点。正向乘 2 的逆操作是除以 2，正向减 1 的逆操作是加 1。

正向操作	反向操作
`x * 2`	`x / 2`
`x - 1`	`x + 1`

记忆钩子：正向选择纠结时，看看反向是否能让每一步变成唯一最优。

当目标比起点大时，除以 2 的缩小效率远高于加 1，所以能除就除。

三、为什么偶数目标要除以 2

如果反向目标 target 是偶数，它可以由正向某个数乘 2 得到。反向除以 2 会快速接近起点。

target = 20
20 -> 10 -> 5

如果不除而选择加 1，目标会变大，通常只会让路径更长。偶数时除以 2 是最直接消除一次正向乘法的方式。

四、为什么奇数目标要加 1

奇数不能直接除以 2。反向只剩加 1 这条有效路，因为目标仍大于起点时，继续变大一步是为了变成偶数，下一步能除以 2。

target = 11
11 -> 12 -> 6

这对应正向路径里的：

6 -> 12 -> 11

也就是先乘 2 再减 1。

五、什么时候停止反向循环

当 target <= startValue 时，反向再除以 2 或加 1都没有必要。正向从 startValue 到较小的 target，只能通过减 1 完成。

start=10, target=6
10 -> 9 -> 8 -> 7 -> 6，需要 4 步

所以最后直接加上：

startValue - target

这个尾巴是很多人漏掉的边界。

六、代码模板

int brokenCalc(int startValue, int target) {
    int steps = 0;
    while (target > startValue) {
        if (target % 2 == 0) {
            target /= 2;
        } else {
            target += 1;
        }
        steps++;
    }
    return steps + (startValue - target);
}

循环只在目标仍大于起点时进行反向贪心。每次偶数除半，奇数先加一，目标规模整体会很快下降。

七、常见误区与追问

误区：正向一直乘 2 到超过目标。 超过多少会影响回退成本，不容易直接最优。
误区：反向奇数时减 1。 减 1 不是正向操作的逆操作；正向没有 +1，所以反向没有 -1。
误区：target 小于 start 后继续反向处理。 此时正向只能减 1，直接计算差值。
追问：为什么偶数一定除以 2？ 除以 2 是最快缩小目标并对应一次正向乘法的操作。
追问：复杂度为什么接近对数？ 大部分操作会把目标除以 2，奇数也只需加一次再除。
追问：这类题什么时候考虑反向？ 正向操作有“扩大”和“回退”纠结，而逆向操作更确定时。

八、加强记忆

坏了的计算器别从起点硬冲，倒着看更清楚。目标大于起点时，偶数就除以 2，奇数就加 1 变偶数；目标不大于起点后，剩下就是起点减到目标的步数。反向贪心的关键是把“乘不乘”的纠结变成“能不能除”的确定判断。

简化版

详细版