What is the main pattern used in Minimum Number of Coins for Fruits?

The primary pattern is state transition dynamic programming, tracking minimal coins while considering reward effects from purchased fruits.

Can a fruit be purchased even if it is available for free?

Yes, purchasing a fruit can sometimes lead to a better overall solution because it may unlock rewards that reduce total coins spent.

What data structures can optimize the DP transitions?

Using a monotonic queue or priority queue helps efficiently track the minimum cost states influenced by rewards during DP updates.

What are the constraints on the prices array?

The array length is 1 to 1000, and each price is between 1 and 105 coins.

How do I handle reward interactions in the solution?

Update DP states carefully for each fruit by considering both buying it and taking it as a free reward, choosing the option that minimizes the total coins.

#2944

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个下标从 0 开始的整数数组 prices ，其中 prices[i] 表示你购买第 i + 1 个水果需要花费的金币数目。水果超市有如下促销活动：如果你花费 prices[i] 购买了下标为 i + 1 的水果，那么你可以免费获得下标范围在 [i + 1, i + i] 的水果。注…

数组动态规划队列堆（优先队列）单调队列

题目描述

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

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

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

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

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

示例 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 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

提示：

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

lightbulb

解题思路

方法一：记忆化搜索

我们定义一个函数 $\textit{dfs}(i)$ ，表示从第 $i$ 个水果开始购买所有水果所需要的最少金币数。那么答案就是 $\textit{dfs}(1)$ 。

函数 $\textit{dfs}(i)$ 的执行逻辑如下：

如果 $i \times 2 \geq n$ ，说明只要买第 $i - 1$ 个水果即可，剩余的水果都可以免费获得，所以返回 $\textit{prices}[i - 1]$ 。
否则，我们可以购买水果 $i$ ，然后在接下来的 $i + 1$ 到 $2i + 1$ 个水果中选择一个水果 $j$ 开始购买，那么 $\textit{dfs}(i) = \textit{prices}[i - 1] + \min_{i + 1 \le j \le 2i + 1} \textit{dfs}(j)$ 。

为了避免重复计算，我们使用记忆化搜索的方法，将已经计算过的结果保存起来，下次遇到相同的情况时，直接返回结果即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{prices}$ 的长度。

1

2

3

4

5

6

7

8

9

10

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

        return dfs(1)

speed

复杂度分析

指标	值
时间	complexity depends on how transitions are implemented; using a DP array with monotonic queue can reduce redundant calculations. Space complexity is primarily the DP array plus auxiliary structures for tracking rewards.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to recognize state transition dynamic programming is required.
question_mark
Check if the candidate correctly models free fruits as reward states in DP.
question_mark
Look for efficient handling of DP transitions with queue or heap to meet constraints.

warning

常见陷阱

外企场景

error
Ignoring the benefit of purchasing a fruit even if it could be received for free.
error
Incorrectly updating DP states, leading to overcounting or missing reward interactions.
error
Not optimizing transitions, resulting in timeouts on large input arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Varying reward rules where a fruit gives multiple free fruits instead of one.
arrow_right_alt
Adding a limit on the number of fruits that can be purchased or taken for free.
arrow_right_alt
Modifying the price array to include zero-cost fruits and verifying DP correctness.

help

常见问题

外企场景

继续练习

#2945 找到最大非递减数组的长度 #2762 不间断子数组 #1696 跳跃游戏 VI