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

难度: Hard

一张桌子上总共有 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] <= 10⁵
1 <= k <= sum(piles[i].length) <= 2000

Submission

运行时间: 224 ms

内存: 34.8 MB

import numpy as np

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        dp = np.zeros(k+1)
        for pile in piles:
            temp = dp.copy()
            for used, value in enumerate(accumulate(pile), 1):
                if used > k: break
                dp = np.maximum(dp, np.concatenate((np.zeros(used), temp[:-used] + value)))
        return int(dp[-1])

Explain

这个题解使用了动态规划的方法，其中dp数组用来存储取出不同数量的硬币所能得到的最大面值和。对每一个硬币堆，通过累加每个硬币的面值来更新dp数组。对于每个堆中的硬币，我们计算取出从1个到全部硬币的情形，并更新dp数组以保持最大值。具体来说，对于每个硬币堆中取出的硬币数目`used`和它的累积面值`value`，我们尝试将这个累积值添加到之前的dp数组中，通过比较不同取法下的dp值，来决定是否更新dp数组的对应位置。

时间复杂度: O(n*k*k)

空间复杂度: O(k)

import numpy as np

from itertools import accumulate

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        # 初始化dp数组，长度为k+1，全部为0
        dp = np.zeros(k+1)
        # 遍历每一个硬币堆
        for pile in piles:
            # 复制当前的dp数组到临时数组temp
            temp = dp.copy()
            # 遍历每个硬币堆，计算累积的硬币面值
            for used, value in enumerate(accumulate(pile), 1):
                # 如果取的硬币数大于k，就停止当前堆的处理
                if used > k: break
                # 更新dp数组，将取used个硬币的情况与之前的结果进行比较
                dp = np.maximum(dp, np.concatenate((np.zeros(used), temp[:-used] + value)))
        # 返回取k个硬币时的最大面值和
        return int(dp[-1])

Explore

动态规划方法被选择用于解决这个问题是因为它能够考虑到所有可能的选择组合来得出最优解。这个问题涉及多个选择（从不同的硬币堆中选择不同数量的硬币），且每个选择会影响最终的结果，这是动态规划擅长处理的类型的问题。与贪心算法相比，动态规划的优势在于它通过考虑所有可能的组合，保证了得到全局最优解。而贪心算法则是在每一步都做出当下看起来最好的选择，这可能导致最终未能达到全局最优。不过，动态规划的缺点在于它通常需要较大的时间和空间复杂度，特别是当问题的规模较大时，而贪心算法则通常更快且使用的空间更少。

题解中的dp数组用于记录达到每个可能的硬币数目（从0到k）的最大面值和。在处理每个硬币堆时，该代码片段用于更新dp数组。具体来说，`np.maximum`函数用于比较两个数组，并逐项选择两者中的最大值。这里的两个数组是原始的dp数组和一个经过修改的temp数组。`temp`是dp数组的一个拷贝，用于暂存之前的状态。`np.concatenate((np.zeros(used), temp[:-used] + value))`这个表达式创建了一个新数组：它首先添加`used`个0值，然后加上从`temp`数组中去除了后`used`个元素之后剩余元素与`value`的和。这样做的目的是模拟从当前堆中取出`used`个硬币的情况，`np.zeros(used)`代表在取出这些硬币之前，相应位置的最大值应为0（无法取出更多硬币）。`temp[:-used] + value`则表示在现有的最大和基础上加上当前堆中`used`个硬币的总值。最终，`np.maximum`确保了dp数组在每个位置都保持了最大可能的硬币面值和。

在处理每个硬币堆时，如果取的硬币数大于k，程序便停止当前堆的处理，因为从一个单独的硬币堆中取出超过k个硬币是无效的。这是因为我们的目标是寻找取出总共k个硬带的最大面值和，取出超过k个硬币会导致无法满足问题的条件。这种处理方式是基于问题本身的限制，不会错过最优解，因为即使某个硬币堆中的硬币非常有价值，超过k个的取法也超出了题目的要求。