LeetCode:2218. 从栈中取出 K 个硬币的最大面值和(DP Java)
目录
2218. 从栈中取出 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
实现代码与解析:
分组背包
class Solution {
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
int[] f = new int[k + 1];
Arrays.fill(f, -1);
f[0] = 0;
for (List<Integer> list: piles) {
for (int i = k; i > 0; i--) {
int cur = 0;
for (int l = 1; l <= list.size() && i >= l; l++) {
cur += list.get(l - 1);
if (f[i - l] != -1) {
f[i] = Math.max(f[i], f[i - l] + cur);
}
}
}
}
return f[k];
}
}
原理思路:
可以转化为背包问题,这里每个栈取的个数就为体积(质量),而每个栈取不同体积值不同(相加)。那么很明显就是一个分组的背包问题。
f[i] 为 体积为 i 下,选取不同组和个数的最大价值。
我的背包详解,分组背包就是比普通背包多了一个循环计算和罢了。
动态规划:0-1背包、完全背包问题 | 详细原理解释 | 代码及优化(C++)_c++ 01背包问题时间优化-CSDN博客
原文地址:https://blog.csdn.net/Cosmoshhhyyy/article/details/145291363
免责声明:本站文章内容转载自网络资源,如侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!