LeetCode 1553. 吃掉 N 个橘子的最少天数

2024-07-24 HGNULB 约 6 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1553. 吃掉 N 个橘子的最少天数

题意分析

手上有 n 个橘子，每天必须从三种吃法里选一种：吃掉 1 个；若剩余数量是 2 的倍数，吃掉一半；若剩余数量是 3 的倍数，吃掉三分之二。问吃完全部橘子最少需要多少天。要的是天数，不需要输出具体吃法。

后两种吃法的效果值得单独翻译：吃掉一半后剩下 n / 2，吃掉三分之二后剩下 n / 3。所以三种操作在「剩余数量」这个视角下分别是减 1、除以 2、除以 3，而后两者都带整除条件。

n 的上界是 $2 \times 10^9$。这个数字直接否决了一切按数值线性推进的思路——开数组存不下，逐个状态推进也来不及。同时它也暗示答案本身很小：即使每天都能减半，$2 \times 10^9$ 也只要三十来次就归零，所以最优解的天数是对数量级的，真正需要访问的状态数远少于 n。

除以 2 和除以 3 是压缩数量最快的两种手段，减 1 只能用来把 n 修正成 2 或 3 的倍数，好让除法生效。这个「主操作 + 修正操作」的结构是全题的骨架。

边界上 n = 0 时答案是 0，n = 1 时答案是 1（只能吃 1 个）。这两个是递归的终点。

解法：记忆化搜索

核心思路

把每个剩余数量当作 BFS 节点虽然能求最短路，但“吃 1 个”会把状态沿 n,n-1,... 铺开，n 可达 $2*10^9$，队列和访问集合都不可行。关键是把连续减 1 合并成除法前的修正成本。

定义 dfs(x) 为吃完 x 个橘子的最少天数。若下一次批量操作选择除以 2，只需先吃 x%2 个使其整除，再用 1 天减半，进入 dfs(x/2)；除以 3 同理。因此：

dfs(x) = min(x%2 + 1 + dfs(x/2), x%3 + 1 + dfs(x/3))。

为什么只减到最近的倍数：若为了除以 k 多减了 k*t 个，除法后的状态只少 t。后续状态少 t 个最多节省 t 天，而前面额外花了 k*t 天，绝不会更优。因此无需保留独立的 dfs(x-1) 分支。

状态不变量：dfs(x) 返回从剩余 x 个开始的全局最少天数。 任一最优方案的第一次批量操作只能是除以 2 或除以 3，前面的单个删除已由余数精确计费；两条转移覆盖全部最优候选，取最小值即正确。边界 dfs(0)=0、dfs(1)=1。

递归只会访问由反复除以 2、3 得到的稀疏状态；同一状态可能通过不同顺序到达，所以用哈希表记忆化，避免指数级重复。

解题步骤

x<=1 时直接返回 x。

若 x 已在缓存中，直接返回。

计算走除以 2 前所需的余数天数、批量操作 1 天和子问题。

对除以 3 做同样计算，取两者较小值并缓存。

n=10 时，除以 2 分支为 1+dfs(5)=5；除以 3 分支先吃 1 个，再除以 3，为 2+dfs(3)=4，因此答案是 4。边界 n=1 直接返回 1。

若加入独立的 1+dfs(x-1)，答案不变，却会沿大量连续整数展开，破坏稀疏状态优势。

代码实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    private final Map<Integer, Integer> memo = new HashMap<>();

    public int minDays(int n) {
        if (n <= 1) {
            return n;
        }

        Integer cached = memo.get(n);
        if (cached != null) {
            return cached;
        }

        int byTwo = n % 2 + 1 + minDays(n / 2);
        int byThree = n % 3 + 1 + minDays(n / 3);
        int answer = Math.min(byTwo, byThree);
        memo.put(n, answer);
        return answer;
    }
}

func minDays(n int) int {
	memo := make(map[int]int)

	var dfs func(int) int
	dfs = func(oranges int) int {
		if oranges <= 1 {
			return oranges
		}
		if cached, exists := memo[oranges]; exists {
			return cached
		}

		byTwo := oranges%2 + 1 + dfs(oranges/2)
		byThree := oranges%3 + 1 + dfs(oranges/3)
		answer := byTwo
		if byThree < answer {
			answer = byThree
		}
		memo[oranges] = answer
		return answer
	}

	return dfs(n)
}

复杂度分析

时间复杂度： $O(\log^2 n)$。可达状态可写成反复除以 2 和 3 的组合，两个指数都只有 $O(\log n)$ 种，每个状态只计算一次。

空间复杂度： $O(\log^2 n)$，用于缓存；递归深度为 $O(\log n)$。

关键点总结

最短路形式不代表必须 BFS；巨大数值区间加“减一边”会让显式状态搜索爆炸。

连续减一只服务于下一次整除，应折叠成 x%2 或 x%3 的修正成本。

记忆化状态是剩余橘子数，转移覆盖第一次批量操作的两种选择。

状态值巨大但访问稀疏，使用哈希表而不是长度为 n 的数组。

缓存消除“先除 2 再除 3”和“先除 3 再除 2”等路径的重复子问题。

易错点总结

用数组做 dp[0..n] 或显式 BFS： n=2*10^9 时内存和遍历量都不可接受。

保留 dfs(n-1) 分支： 会沿连续整数扩展，失去对数级状态规模。

把吃掉三分之二后的剩余量写成 2*n/3： 正确子问题是 n/3。

遗漏 n=1 边界： 递推会错误地把最后一个橘子算成两天。

计算后不写缓存： 相同除法状态会被反复展开，记忆化形同虚设。

相似题目

题目	难度	考察点
397. 整数替换	中等	同为「减一修正 + 除法压缩」的最少步数，但只有除以 2 一种主操作
991. 坏了的计算器	中等	正向搜索发散，需反向从目标出发把乘 2 变成除 2，贪心即可
322. 零钱兑换	中等	状态密集且连续，适合用数组自底向上，与本题的稀疏哈希缓存正好对照
279. 完全平方数	中等	转移分支数随状态变化而非固定两条，还有四平方和定理的数学捷径
650. 两个键的键盘	中等	由质因数分解直接得到答案，是「除法压缩」类题目的数论化形态
1201. 丑数 III	中等	同样围绕整除与倍数展开，但换成在值域上二分配合容斥计数
878. 第 N 个神奇数字	困难	输入规模同为 $10^9$ 级，靠数学闭式与周期性绕开逐个枚举