What is the core strategy for solving Maximum Value of K Coins From Piles?

Use state transition dynamic programming combined with prefix sums to compute the optimal total value when choosing exactly k coins.

How do prefix sums help in this problem?

Prefix sums allow quick computation of the total value of taking the first j coins from a pile, reducing redundant summations during DP transitions.

Can we optimize space in the DP solution?

Yes, a rolling array can reduce space from O(n * k) to O(k) while maintaining correct state transitions.

What happens if a pile has fewer coins than remaining selections?

DP updates should only consider taking up to the available coins in a pile to avoid invalid states.

Is this problem only solvable with dynamic programming?

Yes, because choosing the optimal combination of k coins across multiple piles requires tracking cumulative states, which DP efficiently handles.

#2218

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

一张桌子上总共有 n 个硬币栈。每个栈有正整数个带面值的硬币。每一次操作中，你可以从任意一个栈的顶部取出 1 个硬币，从栈中移除它，并放入你的钱包里。给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里从顶到底的硬币面值。同时给你一个正整数 …

数组动态规划前缀和

题目描述

一张桌子上总共有 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

lightbulb

解题思路

方法一：动态规划（分组背包）

我们定义 $f[i][j]$ 表示从前 $i$ 组中取出 $j$ 个硬币的最大面值和，那么答案为 $f[n][k]$ ，其中 $n$ 为栈的数量。

对于第 $i$ 组，我们可以选择取前 $0$ , $1$ , $2$ , $\cdots$ , $k$ 个硬币。我们可以通过前缀和数组 $s$ 来快速计算出取前 $h$ 个硬币的面值和。

状态转移方程为：

f[i][j] = \max(f[i][j], f[i - 1][j - h] + s[h])

其中 $0 \leq h \leq j$ ，而 $s[h]$ 表示第 $i$ 组中取前 $h$ 个硬币的面值和。

时间复杂度 $O(k \times L)$ ，空间复杂度 $O(n \times k)$ 。其中 $L$ 为所有硬币的数量，而 $n$ 为栈的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        f = [[0] * (k + 1) for _ in range(n + 1)]
        for i, nums in enumerate(piles, 1):
            s = list(accumulate(nums, initial=0))
            for j in range(k + 1):
                for h, w in enumerate(s):
                    if j < h:
                        break
                    f[i][j] = max(f[i][j], f[i - 1][j - h] + w)
        return f[n][k]

speed

复杂度分析

指标	值
时间	complexity is O(n * k^2) if iterating over all possible coins per pile, but using prefix sums can optimize constant factors. Space complexity is O(n * k) for the DP table, reducible to O(k) with rolling arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They may ask about handling piles with different lengths in DP transitions.
question_mark
Expect questions on how prefix sums improve efficiency over brute-force accumulation.
question_mark
They often test understanding of state definition and iterative DP updates for exact k selections.

warning

常见陷阱

外企场景

error
Forgetting to consider piles with fewer than the remaining coins in DP updates.
error
Mixing up top-to-bottom order when computing prefix sums, which breaks correctness.
error
Not initializing the DP table correctly for zero coins or zero piles cases.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximize total coins from exactly k piles instead of coins per pile.
arrow_right_alt
Minimize the total coin value for k coins using similar DP structure.
arrow_right_alt
Allow removing multiple top coins in one move and recompute DP accordingly.

help

常见问题

外企场景

继续练习

#2100 适合野炊的日子 #2420 找到所有好下标 #2439 最小化数组中的最大值