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

univerexplorer2025-01-242025-01-24

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

中等（动态规划）

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

水果超市有如下促销活动：

如果你花费 prices[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, i + i] 的水果。

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

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

示例 1：

输入： prices = [3,1,2]

输出： 4

解释：

用 prices[0] = 3 个金币购买第 1 个水果，你可以免费获得第 2 个水果。

用 prices[1] = 1 个金币购买第 2 个水果，你可以免费获得第 3 个水果。

免费获得第 3 个水果。

请注意，即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

示例 2：

输入： prices = [1,10,1,1]

输出： 2

解释：

用 prices[0] = 1 个金币购买第 1 个水果，你可以免费获得第 2 个水果。

免费获得第 2 个水果。

用 prices[2] = 1 个金币购买第 3 个水果，你可以免费获得第 4 个水果。

免费获得第 4 个水果。

示例 3：

输入： prices = [26,18,6,12,49,7,45,45]

输出： 39

解释：

用 prices[0] = 26 个金币购买第 1 个水果，你可以免费获得第 2 个水果。

免费获得第 2 个水果。

用 prices[2] = 6 个金币购买第 3 个水果，你可以免费获得第 4，5，6（接下来的三个）水果。

免费获得第 4 个水果。

免费获得第 5 个水果。

用 prices[5] = 7 个金币购买第 6 个水果，你可以免费获得第 7 和第 8 个水果。

免费获得第 7 个水果。

免费获得第 8 个水果。

请注意，即使您可以免费获得第 6 个水果作为购买第 3 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

代码一：递归

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        prices = [0] + prices
        @cache
        def func1(pos):
            if pos*2+1 >= len(prices):
                return prices[pos]
            return min(func1(i) for i in range(pos+1,2*pos+2)) + prices[pos]
        return func1(1)

思路：

下标为1的水果是必须要购买的，因此从1开始。购买第 pos 个水果，那么区间 [pos + 1, 2 * pos] 中的水果是可以免费获得的。如果 pos*2+1 超过数组长度，那么就返回购买的第 pos 个水果的金币数；否则依次考虑区间中的水果是否购买，返回最小的花费。

复杂度分析

时间复杂度：O(n^2)。
空间复杂度：O(n)。

代码二：动态规划

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        def func(f):
            n = len(f)
            for i in range((n + 1) // 2 - 1, 0, -1):
                f[i - 1] += min(f[i: i * 2 + 1])
            return f[0]
        return func(prices)