骗外包有机会转正，从那天以后他每天主动加班到2点

今天咱们聊一聊一道经典的算法题：整数替换。别看它题目简单，搞不好它会让你陷入深深的思考。题目要求我们将一个整数 n 通过最少的操作变成1，每次操作有两个选择：

1. n 减 1
2. 如果 n 能被 2 或 3 整除，分别可以执行 n / 2 或 n / 3 操作。

乍一看，这好像是个贼简单的题，直接减到1就完了呗？但问题就在于，如果我们粗暴地每次减 1，效率可是低得吓人，运气不好可能需要做几千步才能到达1。那么，如何更高效地解决这个问题呢？咱们一起来深入剖析。

递归的直觉解法

对于这个问题，如果我们不加任何技巧，直接从 n 开始递归处理，可能会想出这样的步骤：

1. 如果 n 是偶数，直接除以 2。
2. 如果 n 是奇数，减 1，或者加 1（这时候就能尽可能让它变成偶数）。

但递归实现直接的缺点就是计算过程重复，效率极低。假设我们要处理一个较大的 n，递归会不断计算相同的结果，导致大量的冗余计算。

动态规划来救场

为了避免这种重复计算，我们可以用“记忆化递归”来优化算法。啥是记忆化递归呢？简单来说，就是在递归过程中把计算结果给记住，以后遇到相同的数字直接返回，省去重复计算的麻烦。

import java.util.HashMap;
import java.util.Map;
public class IntegerReplacement {
    public int integerReplacement(int n) {
        // 用一个 HashMap 存储已经计算过的结果
        return integerReplacementHelper(n, new HashMap<>());
    }
    private int integerReplacementHelper(int n, Map<Integer, Integer> memo) {
        // 如果 n 是 1，直接返回 0 步
        if (n == 1) return 0;
        // 如果 n 已经计算过，直接返回缓存结果
        if (memo.containsKey(n)) return memo.get(n);
        // 计算当前 n 是偶数还是奇数的处理方式
        int result;
        if (n % 2 == 0) {
            result = 1 + integerReplacementHelper(n / 2, memo); // n 是偶数
        } else {
            int result1 = 1 + integerReplacementHelper(n - 1, memo); // 减 1
            int result2 = 1 + integerReplacementHelper(n + 1, memo); // 加 1
            result = Math.min(result1, result2); // 选择更优的操作
        }
        // 将结果存入 memo 中
        memo.put(n, result);
        return result;
    }
    public static void main(String[] args) {
        IntegerReplacement ir = new IntegerReplacement();
        System.out.println(ir.integerReplacement(8)); // 输出 3，8 -> 4 -> 2 -> 1
    }
}

代码解读

这段代码的核心就是通过递归加记忆化来避免冗余计算。具体过程如下：

1. 我们首先判断 n == 1 的基本情况，直接返回 0。
2. 接着检查 memo（缓存）中是否已经有了计算过的结果，如果有，直接返回缓存的值。
3. 如果 n 是偶数，那就直接除以 2 递归处理。
4. 如果 n 是奇数，减 1 或加 1 都能得到更接近偶数的数，我们就分别递归计算两种情况，返回较小的结果。
5. 最后，存储计算结果到 memo 中，确保之后可以直接复用。

时间复杂度

这道题的时间复杂度其实是 O(log N)，因为每次我们都在做类似除以 2 的操作，递归深度是对数级别的。通过记忆化，避免了重复计算，相比暴力递归的方法，效率提升了不少。

进一步优化

上面的递归解法虽然已经够高效，但如果你不喜欢递归（比如担心递归深度太深导致栈溢出），我们可以考虑转化为迭代形式，采用动态规划的方式。这样不仅可以消除递归的栈深度问题，还能更清晰地展示每一步的计算。

public class IntegerReplacement {
    public int integerReplacement(int n) {
        // 动态规划的解法
        int steps = 0;
        while (n > 1) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                // 选择减 1 或加 1
                if (n == 3 || (n & 2) == 0) {
                    n--;
                } else {
                    n++;
                }
            }
            steps++;
        }
        return steps;
    }
    public static void main(String[] args) {
        IntegerReplacement ir = new IntegerReplacement();
        System.out.println(ir.integerReplacement(8)); // 输出 3
    }
}

迭代解法

在这个版本中，while 循环代替了递归，直接通过不断减小 n 来找到最优解。这里的关键优化点是，如果 n 是奇数，使用位运算来判断是减 1 还是加 1，以便尽可能让 n 更容易被 2 整除。

总结

通过这道题，我们可以看到递归和动态规划在算法中的妙用。无论是递归加记忆化，还是迭代形式，都能让我们高效地求解这个问题。而且，像这样的算法题常常会出现在面试中，解得好不仅能展示你的算法思维，还能让面试官感受到你的优化能力。