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

Categories:

题目描述
思路分析
1. 解法一：记忆化搜索（推荐）
相似题目

题目描述

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

思路分析

解法一：记忆化搜索（推荐）

核心思路：

每天有三种操作：吃 1 个、吃 n/2 个（n 为偶数时）、吃 2n/3 个（n 为 3 的倍数时）

直接 BFS/DFS 的状态空间高达 2×10^9，需要优化

关键观察：到达偶数 n，最优策略是先吃掉 n % 2 个（每次吃1），再吃 n/2；到达 3 的倍数同理

因此递推为：dp[n] = min(n%2 + 1 + dp[n/2], n%3 + 1 + dp[n/3])

用 HashMap 做记忆化，仅需存储实际访问的状态，规避超大数组

复杂度分析：

时间复杂度：O(log² n)，每次递归将问题规模缩小至 n/2 或 n/3

空间复杂度：O(log² n)，记忆化哈希表的状态数量

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

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

        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        // 先把多余的吃掉（每次吃1个），再使用整除操作
        int result = Math.min(
            n % 2 + 1 + minDays(n / 2),
            n % 3 + 1 + minDays(n / 3)
        );

        memo.put(n, result);

        return result;
    }
}

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

    var dfs func(n int) int
    dfs = func(n int) int {
        if n <= 1 {
            return n
        }

        if v, ok := memo[n]; ok {
            return v
        }

        // 先把多余的吃掉（每次吃1个），再使用整除操作
        res := min(n%2+1+dfs(n/2), n%3+1+dfs(n/3))
        memo[n] = res

        return res
    }

    return dfs(n)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
650. 只有两个键的键盘	中等	动态规划 / 数学
279. 完全平方数	中等	动态规划 / BFS
343. 整数拆分	中等	动态规划 / 数学
1342. 将数字变成 0 的操作次数	简单	位运算
2139. 得到目标值的最少行动次数	中等	贪心 / 递归
991. 坏了的计算器	中等	贪心 / 逆向思维

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/95190141