MediumRating 1709
2944. Minimum Number of Coins for Fruits
arraydynamic-programmingqueueheap-priority-queuemonotonic-queue
解題說明
Minimum Number of Coins for Fruits
題目描述： 水果店有 n 種水果排成一列（1-indexed）。第 i 種水果價格為 prices[i]。購買第 i 種水果後，可以免費獲得接下來的 i 種水果（即第 i+1 到第 2i 種）。問購買所有水果的最少花費。
解題思路： 使用動態規劃。定義 dp[i] 為獲得第 i 到第 n 種所有水果的最小花費。倒序計算：
- dp[i] = prices[i] + min(dp[j])，其中 j 從 i+1 到 min(2i+1, n+1)
- j = 2i+1 表示免費水果用完後的下一個需要購買的位置
- 若 2i+1 > n，表示購買第 i 個後所有剩餘水果都免費，dp[i] = prices[i]
使用單調佇列優化區間最小值查詢，可以達到 O(n)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個元素最多進出單調佇列各一次
空間複雜度：O(n) — dp 陣列和單調佇列
虛擬碼
1. Define dp[i] = minimum cost to acquire fruits i through n (1-indexed) 2. Base case: dp[n+1] = 0 3. Process from i = n down to 1: a. Add dp[i+1] to monotonic deque (maintaining increasing order) b. Remove elements outside window [i+1, 2*i+1] from deque front c. If 2*i >= n: dp[i] = prices[i-1] (buying i covers all remaining) d. Else: dp[i] = prices[i-1] + dp[deque.front()] (min of next choices) 4. Return dp[1]
其他解法
-
純 DP 無優化：dp[i] = prices[i-1] + min(dp[i+1..2i+1])，直接遍歷求最小值。時間 O(n^2)，適合 n 較小的情況。
-
堆（Priority Queue）法：用最小堆維護可用的 dp 值。從後往前遍歷時，將 dp[i+1] 加入堆，同時移除超出範圍的元素。時間 O(n log n)，比單調佇列慢但思路更直觀。
延伸思考
- 如果購買第 i 種水果可以免費獲得接下來 k*i 種（k 為給定常數），DP 轉移如何調整？
- 如果每種水果有數量限制（最多買 m 個），問題如何建模？
- 如果要輸出具體的購買方案（哪些水果是購買的、哪些是免費獲得的），如何追蹤？