HardRating 2048
1553. Minimum Number of Days to Eat N Oranges
dynamic-programmingmemoization
解題說明
Minimum Number of Days to Eat N Oranges
題目描述:
有 n 個橘子,每天可以選擇以下三種操作之一:
- 吃掉 1 個橘子。
- 若 n 能被 2 整除,吃掉 n/2 個橘子。
- 若 n 能被 3 整除,吃掉 2n/3 個橘子。
求吃完所有橘子的最少天數。
解題思路: 直覺上可能會用 BFS 或線性 DP,但 n 最大可達 2 * 10^9,無法用陣列。
關鍵觀察:除以 2 和除以 3 是大幅縮減 n 的操作,吃 1 個的操作只在「調整 n 使其可被 2 或 3 整除」時才有用。因此:
- 先吃
n % 2個(0 或 1 個),使 n 變為偶數,然後除以 2。 - 先吃
n % 3個(0、1 或 2 個),使 n 能被 3 整除,然後除以 3。 - 取兩者的最小值。
遞迴加記憶化(memoization)。由於每次遞迴 n 至少減半或減至三分之一,狀態數量為 O(log^2 n),非常高效。
C++ 解法
複雜度分析
時間複雜度:O(log^2 n) — 每次遞迴 n 至少減半或減至三分之一,展開的狀態數量約為 O(log n * log n)。
空間複雜度:O(log^2 n) — 記憶化表中的狀態數量及遞迴堆疊深度。
虛擬碼
1. Base case: if n <= 1, return n 2. If n is in memo, return memo[n] 3. Compute two options: a. days1 = (n % 2) + 1 + minDays(n / 2) b. days2 = (n % 3) + 1 + minDays(n / 3) 4. memo[n] = min(days1, days2) 5. Return memo[n]
其他解法
BFS(最短路):從 n 開始 BFS,每步生成三種操作的結果。但 n 最大 2*10^9,不加記憶化的 BFS 會爆記憶體。搭配 visited set 和只在 n%2==0 或 n%3==0 時分支,可行但不如記憶化遞迴簡潔。
貪心逼近:每次盡量選除以 3(減最多),不行則除以 2,最後逐一減 1。貪心不一定最優(反例存在),但可作為啟發式上界。
延伸思考
- 為什麼記憶化的狀態數量是 O(log^2 n) 而非 O(n)?如何證明?
- 若新增第四種操作「若 n 能被 5 整除,吃掉 4n/5 個」,演算法如何擴展?
- 若要回傳具體的操作序列(而非只求天數),如何記錄路徑?