Question

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

English Version

题目描述

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

解法

方法一：动态规划

对每个栈求前缀和 $s$，$s_i$ 视为一个体积为 $i$ 且价值为 $s_i$ 的物品。

问题转化为求从 $n$ 个物品组中取物品体积为 $k$，且每组最多取一个物品时的最大价值和。

定义 $dp[i][j]$ 表示从前 $i$ 个组中取体积之和为 $j$ 的物品时的最大价值和。

枚举第 $i$ 组所有物品，设当前物品体积为 $w$，价值为 $v$，则有 $f[i][j]=max(f[i][j],f[i-1][j-w]+v)$。

class Solution:
  def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
    presum = [list(accumulate(p, initial=0)) for p in piles]
    n = len(piles)
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    for i, s in enumerate(presum, 1):
      for j in range(k + 1):
        for idx, v in enumerate(s):
          if j >= idx:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - idx] + v)
    return dp[-1][-1]

class Solution {
  public int maxValueOfCoins(List<List<Integer>> piles, int k) {
    int n = piles.size();
    List<int[]> presum = new ArrayList<>();
    for (List<Integer> p : piles) {
      int m = p.size();
      int[] s = new int[m + 1];
      for (int i = 0; i < m; ++i) {
        s[i + 1] = s[i] + p.get(i);
      }
      presum.add(s);
    }
    int[] dp = new int[k + 1];
    for (int[] s : presum) {
      for (int j = k; j >= 0; --j) {
        for (int idx = 0; idx < s.length; ++idx) {
          if (j >= idx) {
            dp[j] = Math.max(dp[j], dp[j - idx] + s[idx]);
          }
        }
      }
    }
    return dp[k];
  }
}

class Solution {
public:
  int maxValueOfCoins(vector<vector<int>>& piles, int k) {
    vector<vector<int>> presum;
    for (auto& p : piles) {
      int m = p.size();
      vector<int> s(m + 1);
      for (int i = 0; i < m; ++i) s[i + 1] = s[i] + p[i];
      presum.push_back(s);
    }
    vector<int> dp(k + 1);
    for (auto& s : presum) {
      for (int j = k; ~j; --j) {
        for (int idx = 0; idx < s.size(); ++idx) {
          if (j >= idx) dp[j] = max(dp[j], dp[j - idx] + s[idx]);
        }
      }
    }
    return dp[k];
  }
};

func maxValueOfCoins(piles [][]int, k int) int {
  var presum [][]int
  for _, p := range piles {
    m := len(p)
    s := make([]int, m+1)
    for i, v := range p {
      s[i+1] = s[i] + v
    }
    presum = append(presum, s)
  }
  dp := make([]int, k+1)
  for _, s := range presum {
    for j := k; j >= 0; j-- {
      for idx, v := range s {
        if j >= idx {
          dp[j] = max(dp[j], dp[j-idx]+v)
        }
      }
    }
  }
  return dp[k]
}

方法二

class Solution:
  def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
    presum = [list(accumulate(p, initial=0)) for p in piles]
    dp = [0] * (k + 1)
    for s in presum:
      for j in range(k, -1, -1):
        for idx, v in enumerate(s):
          if j >= idx:
            dp[j] = max(dp[j], dp[j - idx] + v)
    return dp[-1]