---

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

• 标签：记忆化搜索、动态规划
• 难度：困难

题目链接

• 1553. 吃掉 N 个橘子的最少天数 - 力扣

题目大意

描述：有 $n$ 个橘子。每天可以选择：

1. 吃掉 $1$ 个橘子。
2. 如果 $n$ 能被 $2$ 整除，吃掉一半（$n/2$ 个）。
3. 如果 $n$ 能被 $3$ 整除，吃掉三分之二（$2n/3$ 个，即剩 $n/3$）。

要求：返回吃完所有橘子的最少天数。

说明：

• $1 \le n \le 2 \times 10^9$。

示例：

• 示例 1：

输入：n = 10
输出：4
解释：你总共有 10 个橘子。
第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。
第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除）
第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。
第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。
你需要至少 4 天吃掉 10 个橘子。

• 示例 2：

输入：n = 6
输出：3
解释：你总共有 6 个橘子。
第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除）
第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除）
第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。
你至少需要 3 天吃掉 6 个橘子。

解题思路

思路 1：记忆化搜索 + 贪心剪枝

1. 核心思想

$n$ 最大 $2 \times 10^9$，无法线性 DP。必须用记忆化搜索 + 剪枝。

关键观察：

• 与其每天吃 $1$ 个直到能被 $2$ 或 $3$ 整除，不如直接跳到最近的能被 $2$ 或 $3$ 整除的数。
• 状态转移：
  • 每天吃 $1$ 个 → 到 $n\%2$ 后整除 $2$：$f(n) = min(n\%2 + f(n//2), n\%3 + f(n//3)) + 1$。
  • 这里的 $n\%2$ 表示先吃 $n\%2$ 天（每天 $1$ 个），然后第 $n\%2+1$ 天执行除以 $2$ 的操作。

严格定义递归：

• 如果 $n \le 1$，直接返回 $n$。
• $f(n) = 1 + min(n\%2 + f(n//2), n\%3 + f(n//3))$。

2. 具体步骤

第 1 步：定义递归函数 $dfs(n)$。

• 如果 $n \le 1$，返回 $n$。
• 如果已记忆化，直接返回。
• $res = 1 + min(n\%2 + dfs(n//2), n\%3 + dfs(n//3))$。
• 存入记忆化，返回。

第 2 步：返回 $dfs(n)$。

3. 复杂度分析

状态数约为 $O(\log n)$，因为每次递归 $n$ 至少减半。

4. 举例说明

以 $n = 10$ 为例：

• $10\%2=0$，$dfs(5)$；$10\%3=1$，$dfs(3)$。
• $dfs(5) = 1 + min(5\%2 + dfs(2), 5\%3 + dfs(1)) = 1 + min(1 + dfs(2), 2 + dfs(1))$
  • $dfs(2) = 1 + min(0 + dfs(1), 2 + dfs(0)) = 1 + min(1, 2) = 2$。
  • $dfs(1) = 1$。
  • $dfs(5) = 1 + min(1+2, 2+1) = 1 + 3 = 4$。
• $dfs(3) = 1 + min(1 + dfs(1), 0 + dfs(1)) = 1 + min(2, 1) = 2$。
• $dfs(10) = 1 + min(0 + 4, 1 + 2) = 1 + min(4, 3) = 4$。

验证：

• 方案：第 $1$ 天吃 $1$ 个（剩 $9$，能被 $3$ 整除），第 $2$ 天吃 $6$ 个（剩 $3$），第 $3$ 天吃 $2$ 个（剩 $1$），第 $4$ 天吃 $1$ 个。$4$ 天。

另一种方案：

• $10 \to 5$（除以 $2$），$5 \to 4$（吃 $1$），$4 \to 2$（除以 $2$），$2 \to 1$（除以 $2$），$1 \to 0$（吃 $1$）。$5$ 天。

最优为 $4$ 天。

思路 1：代码

from functools import lru_cache

class Solution:
    def minDays(self, n: int) -> int:
        @lru_cache(None)
        def dfs(n):
            if n <= 1:
                return n
            return 1 + min(n % 2 + dfs(n // 2), n % 3 + dfs(n // 3))

        return dfs(n)

思路 1：复杂度分析

• 时间复杂度：$O(\log^2 n)$，状态数约 $2\log_2 n$ 个。
• 空间复杂度：$O(\log n)$，递归栈和哈希表。