首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

LeetCode 2944.购买水果需要的最少金币数:动态规划(O(n^2)复杂度,非最优算法)

  • 25-02-19 03:00
  • 3962
  • 9021
blog.csdn.net

【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数组,其中:

  1. buy[i]代表购买下标为i的水果话,获得[0, i]的水果所需的最小花费
  2. notBuy[i]代表不购买下标为i的水果话,获得[0, i]的水果所需的最小花费

因此很容易想到状态转移方程:

  1. 购买下标为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]
  2. 不购买下标为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

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:http://iyenn.com/rec/1658139.html

注:本文转载自blog.csdn.net的Tisfy的文章"https://letmefly.blog.csdn.net/article/details/145340613"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top