Medium

题目描述

给你一个下标从 0 开始的整数数组 prices ，其中 prices[i] 表示购买第 i + 1 个水果需要的硬币数。

水果市场对每个水果都有如下的奖励：

  • 如果你花费 prices[i] 个硬币购买了第 i + 1 个水果，那么你可以免费获得接下来的 i 个水果。

注意，即使你可以免费获得水果 j ，你仍然可以花费 prices[j - 1] 个硬币购买它来获得它的奖励。

返回获得所有水果所需要的 最少 硬币数。

示例 1：

输入：prices = [3,1,2]
输出：4
解释：
- 购买第 1 个水果，花费 3 个硬币，可以免费获得第 2 个水果。
- 购买第 2 个水果，花费 1 个硬币，可以免费获得第 3 个水果。
- 免费获得第 3 个水果。
注意，即使你可以免费获得第 2 个水果作为购买第 1 个水果的奖励，你购买它是为了获得它的奖励，这更优。

示例 2：

输入：prices = [1,10,1,1]
输出：2
解释：
- 购买第 1 个水果，花费 1 个硬币，可以免费获得第 2 个水果。
- 免费获得第 2 个水果。
- 购买第 3 个水果，花费 1 个硬币，可以免费获得第 4 个水果。
- 免费获得第 4 个水果。

示例 3：

输入：prices = [26,18,6,12,49,7,45,45]
输出：39
解释：
- 购买第 1 个水果，花费 26 个硬币，可以免费获得第 2 个水果。
- 免费获得第 2 个水果。
- 购买第 3 个水果，花费 6 个硬币，可以免费获得接下来的 3 个水果（第 4、5、6 个）。
- 免费获得第 4 个水果。
- 免费获得第 5 个水果。
- 购买第 6 个水果，花费 7 个硬币，可以免费获得第 8 和第 9 个水果。
- 免费获得第 7 个水果。
- 免费获得第 8 个水果。

提示：

  • 1 <= prices.length <= 1000
  • 1 <= prices[i] <= 10^5

解题思路

这是一道动态规划问题，关键在于理解题意和状态转移。

核心思路：

  1. 购买第 i 个水果（下标 i-1）会获得接下来 i 个水果的免费权限
  2. 我们需要从后往前考虑，定义 dp[i] 为从第 i 个水果开始到结束所需的最少硬币数
  3. 对于第 i 个水果，我们有两种选择：购买它或者通过之前的购买免费获得

状态转移：

  • 如果我们购买第 i 个水果，花费 prices[i-1]，可以免费获得接下来 i 个水果
  • 这意味着我们下一个需要考虑购买的是第 i+i+1 个水果（即跳过 i 个）
  • 状态转移方程：dp[i] = min(dp[i], prices[i-1] + dp[j])，其中 j 在范围 [i+i+1, n] 内

优化： 可以使用单调队列优化，在每个位置维护后续状态的最小值，将时间复杂度从 O(n²) 优化到 O(n)。

推荐解法： 使用单调队列的动态规划解法，既保证了正确性又有较好的时间复杂度。

代码实现

class Solution {
public:
    int minimumCoins(vector<int>& prices) {
        int n = prices.size();
        vector<int> dp(n + 2, 0);
        deque<pair<int, int>> dq; // {value, index}
        
        // 从后往前填充dp数组
        for (int i = n; i >= 1; i--) {
            // 移除超出范围的元素
            while (!dq.empty() && dq.front().second > i + i) {
                dq.pop_front();
            }
            
            // 获取当前最小值
            int minNext = dq.empty() ? 0 : dq.front().first;
            dp[i] = prices[i - 1] + minNext;
            
            // 将当前dp[i]加入队列，保持单调性
            while (!dq.empty() && dq.back().first >= dp[i]) {
                dq.pop_back();
            }
            dq.push_back({dp[i], i});
        }
        
        return dp[1];
    }
};

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        from collections import deque
        
        n = len(prices)
        dp = [0] * (n + 2)
        dq = deque()  # (value, index)
        
        # 从后往前填充dp数组
        for i in range(n, 0, -1):
            # 移除超出范围的元素
            while dq and dq[0][1] > i + i:
                dq.popleft()
            
            # 获取当前最小值
            min_next = 0 if not dq else dq[0][0]
            dp[i] = prices[i - 1] + min_next
            
            # 将当前dp[i]加入队列，保持单调性
            while dq and dq[-1][0] >= dp[i]:
                dq.pop()
            dq.append((dp[i], i))
        
        return dp[1]

public class Solution {
    public int MinimumCoins(int[] prices) {
        int n = prices.Length;
        int[] dp = new int[n + 2];
        var dq = new LinkedList<(int value, int index)>();
        
        // 从后往前填充dp数组
        for (int i = n; i >= 1; i--) {
            // 移除超出范围的元素
            while (dq.Count > 0 && dq.First.Value.index > i + i) {
                dq.RemoveFirst();
            }
            
            // 获取当前最小值
            int minNext = dq.Count == 0 ? 0 : dq.First.Value.value;
            dp[i] = prices[i - 1] + minNext;
            
            // 将当前dp[i]加入队列，保持单调性
            while (dq.Count > 0 && dq.Last.Value.value >= dp[i]) {
                dq.RemoveLast();
            }
            dq.AddLast((dp[i], i));
        }
        
        return dp[1];
    }
}

/**
 * @param {number[]} prices
 * @return {number}
 */
var minimumCoins = function(prices) {
    const n = prices.length;
    const dp = new Array(n + 1).fill(Infinity);
    dp[n] = 0;
    
    for (let i = n - 1; i >= 0; i--) {
        dp[i] = prices[i] + dp[Math.min(n, i + (i + 1) + 1)];
        for (let j = i + 1; j <= Math.min(n, i + (i + 1)); j++) {
            dp[i] = Math.min(dp[i], prices[i] + dp[j]);
        }
    }
    
    return dp[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 每个元素最多进入和离开单调队列一次
空间复杂度O(n) - dp数组和单调队列的空间开销