2244. Minimum Rounds to Complete All Tasks

──────────────────────────────────────────────────────────────────────

2244. Minimum Rounds to Complete All Tasks

這一題可以算是經典的 Dynamic Programming 70. Climbing Stairs 的變形。只是題目從一次可以走一階兩階，變成了一次可以走兩階或三階，但是要考慮無法走完的情況。

class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        
        counter = Counter(tasks)

        @cache
        def dp(jobs):
            if jobs == 0:
                return 0
            if jobs == 1:
                return -1
            if jobs == 2 or jobs == 3:
                return 1
            
            two = dp(jobs - 2)
            three = dp(jobs - 3)
            if two == -1 and three == -1:
                return -1
            elif two == -1:
                return 1 + three
            elif three == -1:
                return 1 + two
            else:
                return 1 + min(two, three)

        count = 0
        for values in counter.values():
            curr = dp(values)
            if curr == -1:
                return -1
            count += curr

        return count

時間複雜度的分析比較複雜一點 。

1. 我們需要 $O(n)$ 的時間複雜度去計算出 tasks 的計數
2. 遞迴的部分，我們有使用了記憶體優化的方法，所以總共會計算 $O(M)$ 次，$M=max(counter.values())$，因為我們只會計算出 0 至 M 的 dp 一次。
3. 最後是我們會對每一個任務呼叫一次 dp ，總共會計算 $O(k)$ 次，$k=len(counter.values())$。

最後的時間複雜度是 $O(n+M+k)=O(n)$ 空間複雜度也是 $O(n)$。

貪心：這個 DP 有封閉解

回頭看 dp(jobs) 到底在做什麼：把 jobs 拆成若干個 2 和 3，讓份數最少。這件事不需要遞迴，可以直接算出來。

設拆成 $a$ 個 2 和 $b$ 個 3，也就是 $2a+3b=c$，要最小化 $a+b$。既然每一份最多只能吃 3 個，份數的下界就是 $\lceil c/3\rceil$。而這個下界在 $c\ge 2$ 時永遠達得到，分三種情況檢查：

• $c\equiv 0(\mathrm{mod}3)$：全部用 3，共 $c/3$ 份
• $c\equiv 1(\mathrm{mod}3)$：拿一個 3 跟落單的 1 湊成兩個 2（$3+1\to 2+2$），共 $(c-4)/3+2=\lceil c/3\rceil$ 份
• $c\equiv 2(\mathrm{mod}3)$：剩下的 2 自己一份，共 $(c-2)/3+1=\lceil c/3\rceil$ 份

唯一的例外是 $c=1$ —— 1 湊不出任何 2 和 3 的組合，直接回 -1。

class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        ans = 0
        for count in Counter(tasks).values():
            if count == 1:
                return -1
            ans += (count + 2) // 3
        return ans

(count + 2) // 3 就是 $\lceil count/3\rceil$ 的整數寫法。

貪在哪裡

貪心的動作是：每一份都盡量吃 3 個。

它安全是因為上面那個下界論證 —— 份數不可能少於 $\lceil c/3\rceil$，而「盡量吃 3」正好達到這個值，所以它就是最佳解。既然如此，就不必在每一步去試「這一份要吃 2 還是吃 3」，DP 的那個 min(two, three) 是白算的。

另外值得留意的是為什麼整題可以拆開算：不同難度的任務不能放在同一份裡，所以 $k$ 種難度就是 $k$ 個互不影響的子問題，各自求最小值再相加即可。如果題目允許同一份混不同難度，這個拆解立刻垮掉，就得回去用 DP 了。

補充

同樣是「DP 想得出來，但其實有封閉解 / 貪心解」的題：1323. Maximum 69 Number（改最左邊那個 6 就好）、2126. Destroying Asteroids（排序後由小吃到大）。判斷方式見 Greedy 模板。

複雜度

• 時間 $O(n)$ — 一次計數 $O(n)$，再掃過 $k$ 種難度，$k\le n$
• 空間 $O(k)$ — Counter 的大小

其中 $n$ 是 tasks 的長度、$k$ 是相異難度的數量。跟 DP 版本的差別在於省掉了 $O(M)$ 的記憶化表（$M$ 是最大的出現次數），以及遞迴的呼叫堆疊。