从栈中取出 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.length1 <= n <= 10001 <= piles[i][j] <= 1051 <= k <= sum(piles[i].length) <= 2000
代码结果
运行时间: 224 ms, 内存: 34.8 MB
/* 思路：
* 1. 计算每个栈中前缀和并存储在前缀和数组中。
* 2. 使用动态规划（DP）来求解最大面值和。
* 3. 使用Java Stream来简化前缀和的计算和动态规划的更新。
*/
import java.util.*;
import java.util.stream.*;
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
int n = piles.size();
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) {
List<Integer> pile = piles.get(i - 1);
int[] prefixSum = new int[pile.size() + 1];
IntStream.range(0, pile.size()).forEach(j -> prefixSum[j + 1] = prefixSum[j] + pile.get(j));
IntStream.rangeClosed(0, k).forEach(j ->
IntStream.rangeClosed(0, Math.min(j, pile.size())).forEach(x ->
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - x] + prefixSum[x])
)
);
}
return dp[n][k];
}解释
方法:
这个题解使用了动态规划的方法，其中dp数组用来存储取出不同数量的硬币所能得到的最大面值和。对每一个硬币堆，通过累加每个硬币的面值来更新dp数组。对于每个堆中的硬币，我们计算取出从1个到全部硬币的情形，并更新dp数组以保持最大值。具体来说，对于每个硬币堆中取出的硬币数目`used`和它的累积面值`value`，我们尝试将这个累积值添加到之前的dp数组中，通过比较不同取法下的dp值，来决定是否更新dp数组的对应位置。
时间复杂度:
O(n*k*k)
空间复杂度:
O(k)
代码细节讲解
🦆
算法为什么选择使用动态规划方法解决这个问题？它与贪心算法相比有什么优势和缺点？
▷🦆
题解中提到的dp数组具体是如何更新的？请详细解释`np.maximum(dp, np.concatenate((np.zeros(used), temp[:-used] + value)))`这一行代码的逻辑。
▷🦆
为什么在处理每个硬币堆时，如果取的硬币数大于k就停止处理？这样做有可能错过最优解吗？
▷