Hard

题目描述

桌子上有 n 堆硬币。每堆由若干个面额不同的硬币组成。

在一次操作中，你可以从任意一堆的 顶部 取一枚硬币，将其移入你的钱包。

给你一个列表 piles，其中 piles[i] 是一个整数数组，表示第 i 堆中各个硬币的面额。从上到下排列。同时给你一个正整数 k，请你返回在 恰好进行 k 次取硬币操作 的前提下，你钱包中硬币的 最大总价值。

示例 1：

输入：piles = [[1,100,3],[7,8,9]], k = 2
输出：101
解释：
上面的图片展示了几种可能的取硬币方案。
可以获得的最大价值为 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^5
  • 1 <= k <= sum(piles[i].length) <= 2000

解题思路

这是一个经典的动态规划问题，本质上是多维背包问题的变种。

思路分析

关键观察：从每一堆只能从顶部开始连续取硬币，这意味着如果要从第 i 堆取 j 个硬币，必须取前 j 个硬币。

解法：二维动态规划

  1. 状态定义：dp[i][j] 表示考虑前 i 堆硬币，总共取 j 个硬币能获得的最大价值
  2. 预处理：对每堆硬币计算前缀和，prefixSum[i][j] 表示第 i 堆前 j 个硬币的总和
  3. 状态转移：对于第 i 堆，我们可以选择取 0, 1, 2, ..., min(piles[i].length, j) 个硬币
    dp[i][j] = max(dp[i-1][j-t] + prefixSum[i][t])  // t ∈ [0, min(piles[i].length, j)]
  4. 边界条件：dp[0][0] = 0，其他初始值为 0
  5. 答案：dp[n][k]

时间复杂度优化：可以使用滚动数组将空间复杂度从 O(n×k) 优化到 O(k)。

这个解法的核心在于理解每堆硬币的约束：只能从顶部连续取，这样就能将复杂的选择问题转化为枚举每堆取多少个硬币的问题。

代码实现

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        int n = piles.size();
        
        // 预处理：计算每堆的前缀和
        vector<vector<int>> prefixSum(n);
        for (int i = 0; i < n; i++) {
            prefixSum[i].resize(piles[i].size() + 1);
            for (int j = 0; j < piles[i].size(); j++) {
                prefixSum[i][j + 1] = prefixSum[i][j] + piles[i][j];
            }
        }
        
        // dp[i][j] 表示考虑前i堆，取j个硬币的最大价值
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                // 从第i堆取t个硬币 (0 <= t <= min(piles[i-1].size(), j))
                for (int t = 0; t <= min((int)piles[i-1].size(), j); t++) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-t] + prefixSum[i-1][t]);
                }
            }
        }
        
        return dp[n][k];
    }
};

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        
        # 预处理：计算每堆的前缀和
        prefix_sum = []
        for pile in piles:
            curr_sum = [0]
            for coin in pile:
                curr_sum.append(curr_sum[-1] + coin)
            prefix_sum.append(curr_sum)
        
        # dp[i][j] 表示考虑前i堆，取j个硬币的最大价值
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        
        for i in range(1, n + 1):
            for j in range(k + 1):
                # 从第i堆取t个硬币 (0 <= t <= min(len(piles[i-1]), j))
                for t in range(min(len(piles[i-1]), j) + 1):
                    dp[i][j] = max(dp[i][j], dp[i-1][j-t] + prefix_sum[i-1][t])
        
        return dp[n][k]

public class Solution {
    public int MaxValueOfCoins(IList<IList<int>> piles, int k) {
        int n = piles.Count;
        
        // 预处理：计算每堆的前缀和
        int[][] prefixSum = new int[n][];
        for (int i = 0; i < n; i++) {
            prefixSum[i] = new int[piles[i].Count + 1];
            for (int j = 0; j < piles[i].Count; j++) {
                prefixSum[i][j + 1] = prefixSum[i][j] + piles[i][j];
            }
        }
        
        // dp[i][j] 表示考虑前i堆，取j个硬币的最大价值
        int[,] dp = new int[n + 1, k + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                // 从第i堆取t个硬币 (0 <= t <= min(piles[i-1].Count, j))
                for (int t = 0; t <= Math.Min(piles[i-1].Count, j); t++) {
                    dp[i, j] = Math.Max(dp[i, j], dp[i-1, j-t] + prefixSum[i-1][t]);
                }
            }
        }
        
        return dp[n, k];
    }
}

/**
 * @param {number[][]} piles
 * @param {number} k
 * @return {number}
 */
var maxValueOfCoins = function(piles, k) {
    const n = piles.length;
    
    // 预处理：计算每堆的前缀和
    const prefixSum = [];
    for (let i = 0; i < n; i++) {
        const currSum = [0];
        for (const coin of piles[i]) {
            currSum.push(currSum[currSum.length - 1] + coin);
        }
        prefixSum.push(currSum);
    }
    
    // dp[i][j] 表示考虑前i堆，取j个硬币的最大价值
    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(0));
    
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= k; j++) {
            // 从第i堆取t个硬币 (0 <= t <= min(piles[i-1].length, j))
            for (let t = 0; t <= Math.min(piles[i-1].length, j); t++) {
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j-t] + prefixSum[i-1][t]);
            }
        }
    }
    
    return dp[n][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × k × m)，其中 n 是堆数，k 是要取的硬币数，m 是每堆的平均长度
空间复杂度O(n × k + n × m)，dp 数组和前缀和数组的空间

相关题目