golang 刷leetcode:从栈中取出 K 个硬币的最大面值和
golang 刷leetcode:从栈中取出 K 个硬币的最大面值和
一张桌子上总共有 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， 迭代完所有的栈，就得到最大值。
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 }
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！