1553. Minimum Number of Days to Eat N Oranges

Hard
Description

有 n 個橘子，每天可以選擇三種操作之一：吃掉一個橘子；若 n 能被 2 整除，吃掉 n/2 個；若 n 能被 3 整除，吃掉 2n/3 個。求吃完所有橘子的最少天數。

Example:

Input: n = 10 Output: 4

Intuition#

不能用普通 DP（n 太大），但除以 2 或 3 會快速縮小問題規模，用記憶化搜尋 + 貪心跳到最近可整除的數。

  • n 最大到 2 * 10^9，普通 DP 不可行
  • 關鍵觀察：應該盡量使用除 2 或除 3 操作，減 1 只是為了調整到可整除
  • 從 n 開始，先減到能被 2 或 3 整除，然後除以 2 或 3

Approaches#

⭐1: 記憶化搜尋#

  • 概念: 對每個 n，先花 n % 2 天減到能被 2 整除或花 n % 3 天減到能被 3 整除，然後遞迴求解 n/2 或 n/3
  • 時間複雜度: O(log^2(n))
  • 空間複雜度: O(log^2(n))
class Solution {
    private val memo = HashMap<Int, Int>()

    fun minDays(n: Int): Int {
        if (n <= 1) return n
        memo[n]?.let { return it }

        val result = 1 + minOf(
            n % 2 + minDays(n / 2),
            n % 3 + minDays(n / 3)
        )
        memo[n] = result
        return result
    }
}

2: BFS#

  • 概念: 將問題視為圖的 BFS，但只對除 2 和除 3 的分支做展開，減 1 操作用直接計算代替
  • 時間複雜度: O(log^2(n))
  • 空間複雜度: O(log^2(n))
class Solution {
    fun minDays(n: Int): Int {
        if (n <= 1) return n
        val visited = HashMap<Int, Int>()
        val queue = java.util.PriorityQueue<IntArray>(compareBy { it[1] })
        queue.add(intArrayOf(n, 0))
        visited[n] = 0

        while (queue.isNotEmpty()) {
            val (cur, days) = queue.poll()
            if (cur == 0) return days
            if (visited.containsKey(cur) && visited[cur]!! < days) continue

            // 減到能被 2 整除然後除 2
            val d2 = days + cur % 2 + 1
            val n2 = cur / 2
            if (!visited.containsKey(n2) || visited[n2]!! > d2) {
                visited[n2] = d2
                queue.add(intArrayOf(n2, d2))
            }

            // 減到能被 3 整除然後除 3
            val d3 = days + cur % 3 + 1
            val n3 = cur / 3
            if (!visited.containsKey(n3) || visited[n3]!! > d3) {
                visited[n3] = d3
                queue.add(intArrayOf(n3, d3))
            }
        }
        return -1
    }
}

🔑 Takeaways#

  • Pattern: 記憶化搜尋 + 貪心跳躍 – 大數值問題不能逐步 DP，要利用乘除快速縮小規模
  • 關鍵技巧: n % 2 + minDays(n/2) 表示先花 n%2 天減 1 調整到偶數，再除以 2；遞迴只會產生 O(log^2 n) 個不同的子問題