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 個」，演算法如何擴展？
- 若要回傳具體的操作序列（而非只求天數），如何記錄路徑？