【LetMeFly】2944.购买水果需要的最少金币数:动态规划(O(n^2)复杂度,非最优算法)
力扣题目链接:https://leetcode.cn/problems/minimum-number-of-coins-for-fruits/
给你一个 下标从 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] <= 105
解题方法:动态规划
创建buy
数组和notBuy
数组,其中:
buy[i]
代表购买下标为i
的水果话,获得[0, i]
的水果所需的最小花费notBuy[i]
代表不购买下标为i
的水果话,获得[0, i]
的水果所需的最小花费
因此很容易想到状态转移方程:
- 购买下标为
i
的水果的话,可以在购买和不购买i - 1
这两种方案中,选择最优的那个: b u y [ i ] = min ( b u y [ i − 1 ] , n o t B u y [ i − 1 ] ) + p r i c e s [ i ] buy[i] = \min(buy[i - 1], notBuy[i - 1]) + prices[i] buy[i]=min(buy[i−1],notBuy[i−1])+prices[i] - 不购买下标为
i
的水果的话,可以在购买了下标为 [ ⌊ i 2 ⌋ , i ) [ \lfloor\frac{i}2\rfloor, i) [⌊2i⌋,i)的水果的基础上,免费获得下标为i
的水果: n o t B u y [ i ] = min j = ⌊ i 2 ⌋ i − 1 { b u y [ j ] } notBuy[i]=\min\limits_{j=\lfloor\frac{i}2\rfloor}^{i-1}\{buy[j]\} notBuy[i]=j=⌊2i⌋mini−1{buy[j]}
最终,buy[n - 1]
和notBuy[n - 1]
中最小的那个即为所求。
疑难解答
初始值怎么确定?
初始值
buy[0] = notBuy[0] = prices[0]
,因为第一个水果无法通过购买其他水果获赠得到,所以第一个水果必须购买。
为什么 b u y [ i ] = min ( b u y [ i − 1 ] , n o t B u y [ i − 1 ] ) + p r i c e s [ i ] buy[i] = \min(buy[i - 1], notBuy[i - 1]) + prices[i] buy[i]=min(buy[i−1],notBuy[i−1])+prices[i],而不是 b u y [ i ] = n o t B u y [ i − 1 ] + p r i c e s [ i ] buy[i] = notBuy[i - 1] + prices[i] buy[i]=notBuy[i−1]+prices[i]?
读者问题的核心在于是否有必要使用
min
操作判断buy[i - 1]
和notBuy[i - 1]
二者中的最小值。直觉告诉我们,似乎不买
i - 1
会比买i - 1
省钱,似乎notBuy[i - 1]
一定会小于buy[i - 1]
。其实不然,因为我们要获得所有的水果,所以不买水果
3
的话,就一定要买水果2
从而获赠水果3
。但是水果2
可能十分贵,不如购买水果1
和3
而令水果2
作为赠品。
时空复杂度分析
- 时间复杂度 O ( n 2 ) O(n^2) O(n2),其中 n = l e n ( p r i c e s ) n=len(prices) n=len(prices)
- 空间复杂度 O ( n ) O(n) O(n)
AC代码
C++
/*
* @Author: LetMeFly
* @Date: 2025-01-24 13:02:37
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-01-24 14:05:03
*/
class Solution {
public:
int minimumCoins(vector<int>& prices) {
vector<int> buy(prices.size()), notBuy(prices.size());
buy[0] = notBuy[0] = prices[0];
for (int i = 1; i < prices.size(); i++) {
buy[i] = min(notBuy[i - 1], buy[i - 1]) + prices[i]; // 不买3的话必须买2,因此buy[2]不一定大于notBuy[2]
notBuy[i] = 1000000000;
for (int j = i / 2; j < i; j++) {
notBuy[i] = min(notBuy[i], buy[j]);
}
}
return min(buy.back(), notBuy.back());
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
评论记录:
回复评论: