Problem

You are given an 0-indexed integer array prices where prices[i] denotes the number of coins needed to purchase the (i + 1)ᵗʰ fruit.

The fruit market has the following reward for each fruit:

  • If you purchase the (i + 1)ᵗʰ fruit at prices[i] coins, you can get any number of 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 - 1] coins to receive its reward.

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

https://leetcode.cn/problems/minimum-number-of-coins-for-fruits/

Example 1:

Input: prices = [3,1,2]
Output: 4
Explanation:

  • Purchase the 1ˢᵗ fruit with prices[0] = 3 coins, you are allowed to take the 2ⁿᵈ fruit for free.
  • Purchase the 2ⁿᵈ fruit with prices[1] = 1 coin, you are allowed to take the 3ʳᵈ fruit for free.
  • Take the 3ʳᵈ fruit for free.

Note that even though you could take the 2ⁿᵈ fruit for free as a reward of buying 1ˢᵗ fruit, you purchase it to receive its reward, which is more optimal.

Example 2:

Input: prices = [1,10,1,1]
Output: 2
Explanation:

  • Purchase the 1ˢᵗ fruit with prices[0] = 1 coin, you are allowed to take the 2ⁿᵈ fruit for free.
  • Take the 2ⁿᵈ fruit for free.
  • Purchase the 3ʳᵈ fruit for prices[2] = 1 coin, you are allowed to take the 4ᵗʰ fruit for free.
  • Take the 4ᵗʰ fruit for free.

Example 3:

Input: prices = [26,18,6,12,49,7,45,45]
Output: 39
Explanation:

  • Purchase the 1ˢᵗ fruit with prices[0] = 26 coin, you are allowed to take the 2ⁿᵈ fruit for free.
  • Take the 2ⁿᵈ fruit for free.
  • Purchase the 3ʳᵈ fruit for prices[2] = 6 coin, you are allowed to take the 4ᵗʰ, 5ᵗʰ and 6ᵗʰ (the next three) fruits for free.
  • Take the 4ᵗʰ fruit for free.
  • Take the 5ᵗʰ fruit for free.
  • Purchase the 6ᵗʰ fruit with prices[5] = 7 coin, you are allowed to take the 8ᵗʰ and 9ᵗʰ fruit for free.
  • Take the 7ᵗʰ fruit for free.
  • Take the 8ᵗʰ fruit for free.

Note that even though you could take the 6ᵗʰ fruit for free as a reward of buying 3ʳᵈ fruit, you purchase it to receive its reward, which is more optimal.

Constraints:

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

Test Cases

1
2
class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('prices, expected', [
    ([3,1,2], 4),
    ([1,10,1,1], 2),
    ([26,18,6,12,49,7,45,45], 39),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
def test_solution(sol, prices, expected):
    assert sol.minimumCoins(prices.copy()) == expected

Thoughts

定义 dp(i) 表示购买第 i + 1 个水果并获得后续所有水果所需的最少 coins。所求结果即为 dp(0)。

因为购买了第 i + 1 个水果，可以免费获得第 i + 2 个到第 2i + 2 个水果（共 i + 1 个）。如果这 i + 1 个水果都直接免费获得，那么就必需买第 2i + 3 个水果，总花费为 prices[i] + dp(2i + 2)。也可以选择购买这 i + 1 个水果中的某个（设为第 j + 1 个，其中 i + 1 ≤ j ≤ 2i + 1），总花费为 prices[i] + dp(j)。

当然如果第 i + 1 个水果后边的水果个数不超过 i + 1 个，显然就不用再买了，全部免费获得即可，总花费为 prices[i]。

由此得到状态转移公式为：

dp(i)=prices[i]+{0if 2i+2≥nmin⁡i+1≤j≤2i+2{dp(j)}otherwisedp(i)=prices[i]+\begin{cases} 0 & \text{if }2i+2\ge n \\ \min_{i+1\le j\le 2i+2}\{dp(j)\} & \text{otherwise} \end{cases}

从 i 的最大值 n - 1 开始递减计算。

时间复杂度 O(n²)，空间复杂度 O(n)。

另外计算 dp(i) 的时候只需要 prices[i] 以及后边一些 dp 值，可以直接复用 prices 的空间，空间复杂度降为 O(1)。

再另外当 2i + 2 ≥ n 时，dp(i) = prices[i]，都不需要计算或处理，所以遍历的起点为 ⌈n2⌉−2=⌊n−32⌋\lceil\frac{n}{2}\rceil-2=\lfloor\frac{n-3}{2}\rfloor。

Code

solution.py
1
2
3
4
5
6
7
class Solution:
    def minimumCoins(self, prices: list[int]) -> int:
        n = len(prices)
        for i in range((n-3) // 2, -1, -1):
            prices[i] += min(prices[j] for j in range(i + 1, 2 * i + 3))

        return prices[0]

Faster

从上边状态转移公式就很容易发现有大量的重复计算，比如：

  • dp(i) = prices[i] + min{dp(i+1), dp(i+2), ..., dp(2i), dp(2i+1), dp(2i+2)}
  • dp(i-1) = prices[i-1] + min{dp(i), dp(i+1), dp(i+2), ..., dp(2i)}

其中 dp(i+1) 到 dp(2i) 的最小值判定是重复的，看看怎么避免重复计算。

从 i 过渡到 i - 1 的时候，找最小值的区间的右边减少了两个（2i + 2 和 2i + 1），左边加入了一个（i）。关键在于当区间缩小的时候，如何快速获得新区间内的最小值。

考虑借助 1475. Final Prices With a Special Discount in a Shop 中提到的单调栈。

准备一个单调递增栈（栈里的数字是严格递增的），从右向左依次把每个 dp 值按单调栈的规则入栈，即如果比栈顶的值大则直接入栈，否则把所有小于等于它的值都弹出后再入栈。从 dp(2i+2) 到 dp(i+1) 都处理完，栈底就是这组数的最小值。利用此最小值计算出 dp(i) 后按同样的规则入栈，栈底是 dp(i) 到 dp(2i+2) 的最小值。

当需要计算 dp(i-1) 时，先从栈底开始检查其中数值的来源，如果 dp(2i+2) 或 dp(2i+1) 在栈里（如果在，这俩一定在最接近栈底的位置）则从栈底弹出（相当于队列，这是对一般单调栈的变体）。操作之后的新的栈底值就是 dp(i) 到 dp(2i) 的最小值（显然栈不会为空，因为如果 dp(i) 到 dp(2i) 中有比 dp(2i+2) 和 dp(2i+1) 更小的值，栈底就不会是 dp(2i+2) 或 dp(2i+1)，也就不会有数据被弹出；反之 dp(i) 到 dp(2i) 的最小值比 dp(2i+2) 和 dp(2i+1) 大，此值一定会在栈里）。利用此最小值即可算出 dp(i-1)，再按同样规则入栈即可。

当处理完 dp(0) 后，此值位于栈顶。

为了便于处理 2i + 2 ≥ n 时的 dp 值，可以在单调栈初始化的时候，直接放入一个 0，因为任何 dp 值都大于 0，这个 0 会一直待在栈底直到当 i 降到 ⌈n2⌉−2=⌊n−32⌋\lceil\frac{n}{2}\rceil-2=\lfloor\frac{n-3}{2}\rfloor 时被弹出。

时间复杂度 O(n)，空间复杂度 O(n)。

solution2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import deque


class Solution:
    def minimumCoins(self, prices: list[int]) -> int:
        n = len(prices)
        stack = deque([(0, n)]) # Monotonically increasing stack of (dp(i), i). Use (0, n) as the fence.
        for i in range(n-1, -1, -1):
            # Remove dp(j) where j > 2i + 2.
            r = 2 * i + 2
            while stack[0][1] > r:
                stack.popleft()

            # Now the minimum dp(j) (i+1 <= j <= 2i+2) is stack[0][0].
            cost = prices[i] + stack[0][0]

            # Remove dp(j) where dp(j) >= dp(i).
            while stack and stack[-1][0] >= cost:
                stack.pop()

            # Add dp(i) to the stack.
            stack.append((cost, i))

        return stack[-1][0]
medium
参考资料
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~