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

给你一个下标从 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 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

解题思路

问题分析

核心问题：
- 需要购买所有水果，找出最少的金币数
- 购买第i个水果后可以免费获得[i+1, i+i]范围内的水果
- 即使可以免费获得某个水果，仍然可以选择购买它来获得新的奖励范围
关键观察：
- 购买一个水果可能比免费获得它更优，因为购买后可以获得新的免费范围
- 需要在”免费获得”和”购买获得更多免费范围”之间做权衡
- 这是一个动态规划问题，因为当前决策会影响后续的选择

动态规划设计

状态定义：
- dp[i] 表示获得从第i个水果到最后一个水果所需的最少金币数
- i的范围是[1, n]，因为题目说明下标从1开始
状态转移：
对于第i个水果，我们有两种选择：
a) 如果之前购买的水果能免费覆盖到第i个水果：
- 可以选择免费获得它
- 也可以选择购买它来获得新的免费范围
  b) 如果之前购买的水果不能免费覆盖到第i个水果：
- 必须购买它

状态转移方程：

dp[i] = min(
    prices[i] + dp[next],  # 购买当前水果
    dp[i+1]  # 如果可以免费获得，则跳过当前水果
)

代码实现

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        
        @lru_cache(None)
        def dfs(i, free_until):
            if i > n:
                return 0
            
            # 如果当前位置已经被之前的购买覆盖
            if i <= free_until:
                # 可以选择免费获得，或者购买来获得新的免费范围
                return min(
                    dfs(i + 1, free_until),  # 免费获得
                    prices[i-1] + dfs(i + 1, i + i)  # 购买当前水果
                )
            
            # 如果当前位置没有被覆盖，必须购买
            if i <= n:
                return prices[i-1] + dfs(i + 1, i + i)
            
            return float('inf')
        
        return dfs(1, 0)

代码解释

记忆化搜索：
- 使用@lru_cache装饰器来缓存计算结果
- 避免重复计算相同状态
状态参数：
- i：当前考虑的水果下标（从1开始）
- free_until：之前购买能免费覆盖到的最远位置
决策过程：
- 如果当前水果在免费范围内，可以选择免费获得或购买
- 如果不在免费范围内，必须购买
- 购买后可以免费获得[i+1, i+i]范围内的水果