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

题目描述： 

一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币。

每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里。

给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k ，请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 。

代码思路：

1. 定义状态：
   • dp[i][j] 表示在考虑前 i 堆硬币，且进行了 j 次操作后，可以得到的最大硬币价值。
2. 初始化：
   • 创建一个 (n+1) x (k+1) 的二维数组 dp，其中 n 是硬币堆的数量，k 是最大操作次数。
   • 初始化 dp 数组的所有元素为 0，因为在没有堆或没有操作次数的情况下，最大价值为 0。
3. 状态转移：
   • 对于每一堆硬币 pile（即 piles[i-1]），计算其前缀和 prefix_sum，以便快速计算从该堆中取任意数量硬币的价值。
   • 对于每个操作次数 j，有两种选择：
     • 不选当前堆（pile[i-1]），即保持 dp[i][j] 与 dp[i-1][j] 相同。
     • 选择当前堆，并枚举从该堆中取 w 个硬币（1 <= w <= min(j, len(pile[i-1]))），更新 dp[i][j] 为 dp[i-1][j-w] + prefix_sum[w] 的最大值。这里 dp[i-1][j-w] 表示在选择当前堆之前的状态（即前 i-1 堆，且进行了 j-w 次操作），prefix_sum[w] 表示从当前堆中取 w 个硬币的总价值。
4. 结果：
   • 最终答案即为 dp[n][k]，表示在考虑所有 n 堆硬币，且进行了 k 次操作后，可以得到的最大硬币价值。

代码实现：

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        # 初始化 DP 表
        n = len(piles)
        dp = [[0] * (k + 1) for _ in range(n + 1)]

        # 遍历每个栈
        for i in range(1, n + 1):
            pile = piles[i - 1]
            prefix_sum = [0] + list(accumulate(pile))  # 前缀和
            
            # 遍历操作次数
            for j in range(k + 1):
                # 不选当前栈
                dp[i][j] = dp[i - 1][j]
                
                # 枚举从当前栈中取的硬币数
                for w in range(1, min(j, len(pile)) + 1):
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + prefix_sum[w])

        return dp[n][k]