首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >golang 刷leetcode:从栈中取出 K 个硬币的最大面值和

golang 刷leetcode:从栈中取出 K 个硬币的最大面值和

作者头像
golangLeetcode
发布于 2022-08-02 11:50:06
发布于 2022-08-02 11:50:06
41300
代码可运行
举报
运行总次数:0
代码可运行

一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币。

每一次操作中,你可以从任意一个栈的 顶部 取出 1 个硬币,从栈中移除它,并放入你的钱包里。

给你一个列表 piles ,其中 piles[i] 是一个整数数组,分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k ,请你返回在 恰好 进行 k 次操作的前提下,你钱包里硬币面值之和 最大为多少 。

示例 1:

输入:piles = [[1,100,3],[7,8,9]], k = 2

输出:101

解释:

上图展示了几种选择 k 个硬币的不同方法。

我们可以得到的最大面值为 101 。

示例 2:

输入:piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7

输出:706

解释:

如果我们所有硬币都从最后一个栈中取,可以得到最大面值和。

提示:

n == piles.length

1 <= n <= 1000

1 <= piles[i][j] <= 105

1 <= k <= sum(piles[i].length) <= 2000

解题思路:

1,这个题可以转化成背包问题

2,stack的前n个元素的和sum可以看成,重量为n,价值为sum的物品

3,对每一个栈,有0到n种选择,一共piles.length个栈

4,递推方程为f[j]=max(f[j],f[j-w]+v)

5, 初始化情况下,一个物品也没有选,价值为0

6, 我们不断选物品,背包容量不断减少,价值越来越大,所以我们采用递减的方式迭代

7, 迭代完所有的栈,就得到最大值。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
func maxValueOfCoins(piles [][]int, k int) int {
  f := make([]int, k+1)
  sumN := 0
  for _, pile := range piles {
    n := len(pile)
    for i := 1; i < n; i++ {
      pile[i] += pile[i-1] // pile 前缀和
    }
    sumN = min(sumN+n, k) // 优化:j 从前 i 个栈的大小之和开始枚举(不超过 k)
    for j := sumN; j > 0; j-- {
      for w, v := range pile[:min(n, j)] {
        f[j] = max(f[j], f[j-w-1]+v) // 下标从 0 开始,物品体积为 w+1
      }
    }
  }
  return f[k]
}

func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-05-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 golang算法架构leetcode技术php 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
2024-03-23:用go语言,一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币, 每一次操作中,你可以从
2024-03-23:用go语言,一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币,
福大大架构师每日一题
2024/03/26
2241
2024-03-23:用go语言,一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币, 每一次操作中,你可以从
LeetCode周赛286场,高质量题目,不容错过
这一次的周赛是六方云赞助的,前500名可以获得内推码,还有按摩仪、定制水杯等奖品。
TechFlow-承志
2022/09/21
5100
LeetCode周赛286场,高质量题目,不容错过
Archived | 307-15-背包的二进制优化
Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him to determine what this minimum number is.
gyro永不抽风
2021/05/21
5040
硬币找零问题
顾名思义,就是你去商店买完东西,售货员会给你用若干枚硬币找钱,如何使用这些硬币完成找零。
你的益达
2020/08/05
1.5K0
js分类刷leetcode动态规划
动态规划,英文:Dynamic Programming,简称DP,将问题分解为互相重叠的子问题,通过反复求解子问题来解决原问题就是动态规划,如果某一问题有很多重叠子问题,使用动态规划来解是比较有效的。
js2030code
2022/12/09
1.2K0
动态规划专题刷题记录③:背包问题
从上图中可以看出,01背包每次计算i时的状态只用到了i-1的状态,所有可以舍去i这一维,优化成一维dp。
Here_SDUT
2022/06/29
1.9K0
动态规划专题刷题记录③:背包问题
力扣每日一刷(2023.9.12)
题目中要求 :使得两个子集的元素和相等。 那么就可以对数组中的所有元素求和, 如果sum%2 != 0 ,那么就直接返回false 。原因这里就不多了, 奇数怎么可能有两个相等的子集和呢?
用户11097514
2024/05/31
1310
LeetCode 1561. 你可以获得的最大硬币数目
题目 有 3n 堆数目不一的硬币,你和你的朋友们打算按以下方式分硬币: 每一轮中,你将会选出 任意 3 堆硬币(不一定连续)。 Alice 将会取走硬币数量最多的那一堆。 你将会取走硬币数量第二多的那一堆。 Bob 将会取走最后一堆。 重复这个过程,直到没有更多硬币。 给你一个整数数组 piles ,其中 pilesi 是第 i 堆中硬币的数目。 返回你可以获得的最大硬币数目。 示例 1: 输入:piles = [2,4,1,2,7,8] 输出:9 解释:选出 (2, 7, 8) ,Alice 取走 8
freesan44
2021/09/05
5770
LeetCode 1561. 你可以获得的最大硬币数目
LeetCode 1561. 你可以获得的最大硬币数目
每一轮中,你将会选出 任意 3 堆硬币(不一定连续)。 Alice 将会取走硬币数量最多的那一堆。 你将会取走硬币数量第二多的那一堆。 Bob 将会取走最后一堆。 重复这个过程,直到没有更多硬币。 给你一个整数数组 piles ,其中 piles[i] 是第 i 堆中硬币的数目。
freesan44
2021/12/06
3910
动态规划专题——背包模型
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。
浪漫主义狗
2022/09/19
1.1K0
【C++】算法集锦(9):背包问题
给你一个载重量为 W 的背包,以及一堆物品,这些物品都有属于自己的两个属性:价值var和质量wt,试问这个背包最多能装多少价值的物品。
看、未来
2021/09/18
7410
额,没想到,背包问题解题也有套路。。。
背包问题是一类比较 特殊的动态规划 问题,这篇文章的侧重点会在答案的推导过程上,我们还是会使用之前提到的解动态规划问题的四个步骤来思考这类问题。
五分钟学算法
2020/01/15
1K0
额,没想到,背包问题解题也有套路。。。
JS算法_知识点精讲
该系列的文章,大部分都是前面文章的知识点汇总,如果想具体了解相关内容,请移步相关系列,进行探讨。
前端柒八九
2022/12/19
2.3K0
JS算法_知识点精讲
golang刷leetcode动态规划(4)分割等和子集(0,1背包问题)
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
golangLeetcode
2022/08/02
3480
搞定大厂算法面试之leetcode精讲3.动态规划
动态规划,英文:Dynamic Programming,简称DP,将问题分解为互相重叠的子问题,通过反复求解子问题来解决原问题就是动态规划,如果某一问题有很多重叠子问题,使用动态规划来解是比较有效的。
全栈潇晨
2021/11/22
4390
搞定大厂算法面试之leetcode精讲3.动态规划
【愚公系列】2023年12月 五大常用算法(三)-动态规划算法
动态规划算法的基本思想是将原问题分解为若干个子问题,并先求解子问题,再根据子问题的解得到原问题的解。这种方法的优点在于避免了重复计算,从而提高了算法的效率。
愚公搬代码
2023/12/14
3131
dp经典问题
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
Tim在路上
2020/08/04
4530
C++ 不知算法系列之深入动态规划算法思想
前面写过一篇博文,介绍了什么是动态规划算法。动态规划算法的最大特点,原始问题可以通过分解成规模更小的子问题来解决,子问题之间互成依赖关系,也就是先计算出来的子问题的结果会影响到后续子问题的结果。
一枚大果壳
2022/12/20
5300
C++ 不知算法系列之深入动态规划算法思想
TypeScript 实战算法系列(十):实现动态规划
前面的一系列文章跟大家分享了各种数据结构和算法的实现,本文将分享一些算法的设计技巧:分而治之、动态规划,使用这些技巧可以借算法来解决问题,提升自己解决问题的能力,欢迎各位感兴趣的开发者阅读本文。
一只图雀
2020/09/10
9470
L3-001 凑零钱(回溯和0-1背包)[通俗易懂]
韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有 10 ​4 ​​ 枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。
全栈程序员站长
2022/09/21
3950
推荐阅读
相关推荐
2024-03-23:用go语言,一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币, 每一次操作中,你可以从
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档