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

约 4 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
动态规划 记忆化

题目描述

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

image-20260929085300947

image-20260929085301076

题意分析

每天只能选择一种吃法：吃一个；数量能被 2 整除时吃掉一半；能被 3 整除时吃掉三分之二。后两种操作分别让剩余数量变成原来的二分之一、三分之一，要求吃完全部橘子的最少天数。

n 可达二十亿，逐个求出 0..n 的答案太慢。批量吃法能快速缩小规模，关键是把它之前连续“每天吃一个”的过程压缩掉。

解法：记忆化搜索

核心思路

[!blue]

定义 f(n) 为吃完剩余 n 个橘子的最少天数。若下一次批量操作是除以 2，先用 n % 2 天吃到可整除，再花一天执行批量操作，剩下 n / 2 个；总天数是 n % 2 + 1 + f(n / 2)。除以 3 的候选同理，取两者较小值。

只吃掉余数就立刻执行批量操作，不会漏掉更优方案。设除以 k 前原本准备先吃 r + k*t 个，其中 r = n % k。改成先吃 r 个、除以 k、再逐个吃 t 个，会到达同样的剩余数量，却少花 (k - 1)*t 天。因此没必要在第一次批量操作前多吃整整一组 k 个。

全程只逐个吃也不会更优：当数量至少为 2 时，先调整到偶数并批量吃一次，再逐个吃完，天数已经不超过原来的逐个吃法。所以只比较这两类批量转移即可；0、1 个橘子直接返回数量。

两条分支可能到达相同剩余数量，而后续最优天数只由这个数量决定，用哈希表缓存 f(n)。每次递归都把规模缩到一半或三分之一，避免展开所有中间数量。

解题步骤

  1. 剩余数量不超过 1 时，直接返回它所需的天数。
  2. 若缓存中已有当前数量的答案，直接复用。
  3. 分别计算“调整为偶数 + 一次二分操作 + 剩余最优值”和“调整为三的倍数 + 一次三分操作 + 剩余最优值”。
  4. 把两个候选的较小值存入缓存，再返回。

代码实现

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+1))$。递归状态可写成 $\lfloor n/(2^a3^b)\rfloor$，两种除法次数各为对数量级，每个状态只计算一次。
  • 空间复杂度：单次缓存为 $O(\log^2(n+1))$，递归栈为 $O(\log(n+1))$。Java 跨调用复用成员缓存时，空间按累计不同状态数计算。

关键点总结

[!green]

  • 一次转移包括余数调整、批量操作本身、剩余数量的最优解，三部分都要计入天数。
  • 交换操作顺序证明了只需调整余数，不必枚举任意多次逐个吃。
  • 缓存的键是剩余数量，走到该状态之前花了几天不会影响后续最优值。

易错点总结

[!yellow]

  • 不能只比较 f(n / 2)、f(n / 3)，调整到可整除以及执行操作本身都需要时间。
  • 当前不能整除时也要考虑批量分支，先吃掉余数就能使用它。
  • 0 和 1 必须作为终止状态；剩余 2 个时，统一公式会由二分分支得到最少的 2 天。
  • 直接加入 f(n - 1) 并递归展开，会重新引入大量连续状态，失去余数压缩的作用。

相似题目

题目 难度 关联与区别
397. 整数替换 中等 同样通过先调整到可整除状态再批量缩小整数，避免逐个减少的线性搜索。
991. 坏了的计算器 中等 同样可以反向或按大步操作建立更小状态，本题还允许除3对应的批量吃法。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/95190141
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！