What is the main algorithmic approach for solving the Minimum Number of Days to Eat N Oranges?

The main approach is state transition dynamic programming combined with memoization, minimizing the number of days based on the optimal actions of eating 1, dividing by 2, or dividing by 3.

What are the common pitfalls when solving this problem?

Common pitfalls include incorrect base case handling, not implementing memoization, and failing to optimize recursion for large values of n.

How does memoization optimize the solution for Minimum Number of Days to Eat N Oranges?

Memoization optimizes the solution by storing previously computed results, preventing redundant calculations and improving performance for larger values of n.

What is the time complexity of the solution to the Minimum Number of Days to Eat N Oranges?

The time complexity depends on the memoization table, with each state being computed only once, making it O(n) in the worst case.

What is the base case in the Minimum Number of Days to Eat N Oranges problem?

The base case occurs when n equals 1, where only 1 day is needed to eat the last orange.

#1553

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

吃掉 N 个橘子的最少天数

厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：吃掉一个橘子。如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。每天你只能从以上 3 种方案中选择一种方案。请你返回吃掉所有 n …

动态规划记忆化

题目描述

厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：

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

每天你只能从以上 3 种方案中选择一种方案。

请你返回吃掉所有 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 个橘子。

示例 3：

输入：n = 1
输出：1

示例 4：

输入：n = 56
输出：6

提示：

1 <= n <= 2*10^9

lightbulb

解题思路

方法一：记忆化搜索

根据题目描述，对于每个 $n$ ，我们可以选择三种方式之一：

将 $n$ 减少 $1$ ；
如果 $n$ 能被 $2$ 整除，将 $n$ 的值除以 $2$ ；
如果 $n$ 能被 $3$ 整除，将 $n$ 的值除以 $3$ 。

因此，问题等价于求解通过上述三种方式，将 $n$ 减少到 $0$ 的最少天数。

我们设计一个函数 $dfs(n)$ ，表示将 $n$ 减少到 $0$ 的最少天数。函数 $dfs(n)$ 的执行过程如下：

如果 $n < 2$ ，返回 $n$ ；
否则，我们可以先通过 $n \bmod 2$ 次操作 $1$ ，将 $n$ 减少到 $2$ 的倍数，然后执行操作 $2$ ，将 $n$ 减少到 $n/2$ ；我们也可以先通过 $n \bmod 3$ 次操作 $1$ ，将 $n$ 减少到 $3$ 的倍数，然后执行操作 $3$ ，将 $n$ 减少到 $n/3$ 。我们选择上述两种方式中最少的一种，即 $1 + \min(n \bmod 2 + dfs(n/2), n \bmod 3 + dfs(n/3))$ 。

为了避免重复计算，我们使用记忆化搜索的方法，将已经计算过的 $dfs(n)$ 的值存储在哈希表中。

时间复杂度 $O(\log^2 n)$ ，空间复杂度 $O(\log^2 n)$ 。

1

2

3

4

5

6

7

8

9

10

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

        return dfs(n)

speed

复杂度分析

指标	值
时间	complexity depends on the approach, but memoization reduces redundant calculations. The space complexity is determined by the number of states stored in the memoization table, which is proportional to n in the worst case.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understand state transition and recursive problem-solving techniques.
question_mark
Test for efficiency and correct handling of large inputs.
question_mark
Evaluate the candidate's understanding of memoization in dynamic programming.

warning

常见陷阱

外企场景

error
Incorrect base case handling could result in infinite recursion or incorrect results.
error
Not implementing memoization leads to redundant computations, significantly affecting performance.
error
For large n, failing to optimize recursion depth or memoization can lead to stack overflow or slow execution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to allow for other divisibility conditions (e.g., divide by 4 or 5).
arrow_right_alt
Alter the minimum action (e.g., allow eating multiple oranges each day).
arrow_right_alt
Extend the problem to allow additional actions like skipping days.

help

常见问题

外企场景

继续练习

#1569 将子数组重新排序得到同一个二叉搜索树的方案数 #1575 统计所有可行路径 #1611 使整数变为 0 的最少操作次数