LeetCode：2218. 从栈中取出 K 个硬币的最大面值和（DP Java）

目录

2218. 从栈中取出 K 个硬币的最大面值和

题目描述：

实现代码与解析：

分组背包

原理思路：

---

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博客