购买水果需要的最少金币数

You are at a fruit market with different types of exotic fruits on display.

You are given a 1-indexed array prices, where prices[i] denotes the number of coins needed to purchase the ith fruit.

The fruit market has the following offer:

• If you purchase the ith fruit at prices[i] coins, you can get the next i fruits for free.

Note that even if you can take fruit j for free, you can still purchase it for prices[j] coins to receive a new offer.

Return the minimum number of coins needed to acquire all the fruits.

 

Example 1:

Input: prices = [3,1,2]
Output: 4
Explanation: You can acquire the fruits as follows:
- Purchase the 1st fruit with 3 coins, you are allowed to take the 2nd fruit for free.
- Purchase the 2nd fruit with 1 coin, you are allowed to take the 3rd fruit for free.
- Take the 3rd fruit for free.
Note that even though you were allowed to take the 2nd fruit for free, you purchased it because it is more optimal.
It can be proven that 4 is the minimum number of coins needed to acquire all the fruits.

Example 2:

Input: prices = [1,10,1,1]
Output: 2
Explanation: You can acquire the fruits as follows:
- Purchase the 1st fruit with 1 coin, you are allowed to take the 2nd fruit for free.
- Take the 2nd fruit for free.
- Purchase the 3rd fruit for 1 coin, you are allowed to take the 4th fruit for free.
- Take the 4th fruit for free.
It can be proven that 2 is the minimum number of coins needed to acquire all the fruits.

 

Constraints:

• 1 <= prices.length <= 1000
• 1 <= prices[i] <= 105

此题解采用了动态规划的思想，使用一个双端队列 (deque) 优化状态的转移过程。基本思路是从数组的末尾向前计算每个位置购买水果的最小花费。对于每个位置i，算法计算购买该水果并获取后续免费水果的总成本。双端队列用于存储可能的最小成本和对应的位置，从而快速获得后续位置的最小花费。队列中维护的是一系列（位置，花费）对，确保队列始终保持递增的花费顺序。如果当前计算的花费比队列头部的花费还低，那么头部的花费将不再有用，因此会被移除。每次计算都是基于队列中花费最小的位置来决定当前位置的最优决策。

O(n)

O(n)