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

univerexplorer2025-01-212025-01-21

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
解释：
如果我们所有硬币都从最后一个栈中取，可以得到最大面值和。

代码一：递归

超出内存限制 77 / 123 个通过的测试用例

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        @cache
        def func1(count,pos,l):
            if l == 0:
                return count
            if pos > len(piles)-1:
                return 0
            ans = func1(count,pos+1,l)
            for i in range(min(len(piles[pos]), l)):
                count += piles[pos][i]
                l -= 1
                ans = max(ans,func1(count,pos+1,l))
            return ans
        return func1(0,0,k)

思路：

从左到右依次处理，考虑所有情况。当前栈取出 i 个数，0 <= i < min(len(piles[pos]), l) ，其中 pos 指当前数组第 pos 个栈， l 是指剩余要取多少个数。

代码二：代码一优化

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        @cache
        def func1(pos,l):
            if l == 0:
                return 0
            if pos > len(piles)-1:
                return 0
            ans = func1(pos+1,l)
            count = 0
            for i in range(min(len(piles[pos]), l)):
                count += piles[pos][i]
                l -= 1
                ans = max(ans,count + func1(pos+1,l))
            return ans
        return func1(0,k)

思路：

代码二相比代码一， count 计数不作为函数传递参数。

代码三：动态规划

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        f = [0] * (k + 1)
        sum_n = 0
        for pile in piles:
            n = len(pile)
            for i in range(1, n):
                pile[i] += pile[i - 1]  # 提前计算 pile 的前缀和
            sum_n = min(sum_n + n, k)
            for j in range(sum_n, 0, -1):  # 优化：j 从前 i 个栈的大小之和开始枚举
                # w 从 0 开始，物品体积为 w+1
                f[j] = max(f[j], max(f[j - w - 1] + pile[w] for w in range(min(n, j))))
        return f[k]