[LeetCode] 每日一题 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 个水果的奖励,但您购买它是为了获得其奖励,这是更优化的。
提示
1 <= prices.length <= 1000
1 <= prices[i] <= 10^5
解题思路
我们需要最小化购买水果的总花费,可以采用递归的方式来进行分治。以下是思路分析:
定义子问题:
定义
dfs(i)
表示在购买第i
个水果的前提下,获得第i
个及其后面的水果所需要的最少金币数如果购买第
i
个水果,那么从i + 1
到2 * i
的水果都是免费的。然后,我们需要选择一个后续购买的水果j
,并递归地计算从第j
个水果开始需要的最小金币数
状态转移:
对于每一个
i
,我们需要枚举购买的下一个水果j
,其范围为[i + 1, 2 * i + 1]
。然后计算dfs(j)
的最小值,再加上购买第i
个水果的花费prices[i]
递归终止条件:当
i
达到⌊n / 2⌋
时,后面的水果都可以免费获得
记忆化搜索优化:
由于存在重叠子问题,我们可以使用记忆化搜索来保存已经计算过的状态,避免重复计算
代码实现
class Solution {
public int minimumCoins(int[] prices) {
int[] memory = new int[(prices.length + 1) / 2];
return dfs(1, prices, memory);
}
public int dfs(int index, int[] prices, int[] memory) {
if (index * 2 >= prices.length) {
return prices[index - 1];
}
if (memory[index] != 0) {
return memory[index];
}
int res = Integer.MAX_VALUE;
for (int j = index + 1; j <= index * 2 + 1; j++) {
res = Math.min(res, dfs(j, prices, memory));
}
return memory[index] = res + prices[index - 1];
}
}
复杂度分析
时间复杂度:
由于每次递归都枚举范围
[i + 1, 2 * i + 1]
内的每个j
,因此每个状态会遍历最多O(n)
次总的时间复杂度为
O(n^2)
,其中n
为水果数量
空间复杂度:
递归的深度最多为
O(n)
,因为递归从1
到⌊n / 2⌋
逐步向后推进需要额外的空间来存储记忆化数组
memory
,空间复杂度为O(n)
总结
今天这道题目让我对递归和记忆化搜索有了更深的理解。题目本身的关键在于如何处理促销活动的规则,特别是如何利用递归去计算每个水果购买后的最优选择。通过递归分解问题,把目标从“获得所有水果最少花费”转化成了“在购买某个水果后,剩余水果的最少花费”,从而逐步求解
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。