Hard

题目描述

厨房里有 n 个橘子，你决定每天按以下方式吃这些橘子：

  • 吃掉一个橘子。
  • 如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
  • 如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。

每天你只能选择其中一种行为。

给你整数 n ，请返回吃掉所有 n 个橘子的最少天数。

示例 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 <= n <= 2 * 10^9

解题思路

这道题可以用动态规划来解决，关键是要理解题目的本质。

核心观察： 虽然看似有三种操作，但实际上最优策略是：

  • 当 n 能被 2 整除时，直接执行操作 2（吃掉 n/2 个橘子，剩余 n/2 个）
  • 当 n 能被 3 整除时，直接执行操作 3（吃掉 2n/3 个橘子，剩余 n/3 个）
  • 当 n 不能被 2 或 3 整除时，先吃掉几个橘子，使其能被 2 或 3 整除

算法思路： 对于任意的 n，我们有两种选择：

  1. 先吃掉 n % 2 个橘子，然后执行操作 2
  2. 先吃掉 n % 3 个橘子，然后执行操作 3

状态转移方程为：

minDays(n) = 1 + min(n % 2 + minDays(n / 2), n % 3 + minDays(n / 3))

由于 n 的范围很大（最大 2*10^9），我们需要使用记忆化搜索来避免重复计算。这种方法避免了朴素 DP 的时间复杂度问题，因为我们只会访问到从 n 开始通过除法操作能到达的状态。

代码实现

class Solution {
    unordered_map<int, int> memo;
    
public:
    int minDays(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        if (memo.find(n) != memo.end()) {
            return memo[n];
        }
        
        int result = 1 + min(n % 2 + minDays(n / 2), n % 3 + minDays(n / 3));
        memo[n] = result;
        return result;
    }
};

class Solution:
    def minDays(self, n: int) -> int:
        memo = {}
        
        def dfs(n):
            if n == 0:
                return 0
            if n == 1:
                return 1
            
            if n in memo:
                return memo[n]
            
            result = 1 + min(n % 2 + dfs(n // 2), n % 3 + dfs(n // 3))
            memo[n] = result
            return result
        
        return dfs(n)

public class Solution {
    private Dictionary<int, int> memo = new Dictionary<int, int>();
    
    public int MinDays(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        if (memo.ContainsKey(n)) {
            return memo[n];
        }
        
        int result = 1 + Math.Min(n % 2 + MinDays(n / 2), n % 3 + MinDays(n / 3));
        memo[n] = result;
        return result;
    }
}

var minDays = function(n) {
    const memo = new Map();
    
    function dp(n) {
        if (n <= 1) return n;
        if (memo.has(n)) return memo.get(n);
        
        const result = 1 + Math.min(
            (n % 2) + dp(Math.floor(n / 2)),
            (n % 3) + dp(Math.floor(n / 3))
        );
        
        memo.set(n, result);
        return result;
    }
    
    return dp(n);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(log²n)
空间复杂度O(log²n)

说明：

  • 时间复杂度：每次递归都会将问题规模至少减少一半（除以 2 或 3），递归深度为 O(log n)，而每个深度最多有 O(log n) 个不同的状态
  • 空间复杂度：记忆化数组存储的状态数量为 O(log²n)，递归调用栈深度为 O(log n)