Skip to content

2218. Maximum Value of K Coins From Piles 👍

  • Time: $O(\Sigma |\texttt{piles[i]}| \cdot k)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int maxValueOfCoins(vector<vector<int>>& piles, int k) {
    vector<vector<int>> mem(piles.size(), vector<int>(k + 1));
    return maxValueOfCoins(piles, 0, k, mem);
  }

 private:
  // Returns the maximum value of picking k coins from piles[i..n)
  int maxValueOfCoins(const vector<vector<int>>& piles, int i, size_t k,
                      vector<vector<int>>& mem) {
    if (i == piles.size() || k == 0)
      return 0;
    if (mem[i][k])
      return mem[i][k];

    // Pick no coins from the current pile.
    int res = maxValueOfCoins(piles, i + 1, k, mem);
    int val = 0;  // the coins picked from the current pile

    // Try to pick 1, 2, ..., k coins from the current pile.
    for (int j = 0; j < min(piles[i].size(), k); ++j) {
      val += piles[i][j];
      res = max(res, val + maxValueOfCoins(piles, i + 1, k - j - 1, mem));
    }

    return mem[i][k] = res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int maxValueOfCoins(List<List<Integer>> piles, int k) {
    Integer[][] mem = new Integer[piles.size()][k + 1];
    return maxValueOfCoins(piles, 0, k, mem);
  }

  // Returns the maximum value of picking k coins from piles[i..n)
  private int maxValueOfCoins(List<List<Integer>> piles, int i, int k, Integer[][] mem) {
    if (i == piles.size() || k == 0)
      return 0;
    if (mem[i][k] != null)
      return mem[i][k];

    // Pick no coins from the current pile.
    int res = maxValueOfCoins(piles, i + 1, k, mem);
    int val = 0; // the coins picked from the current pile

    // Try to pick 1, 2, ..., k coins from the current pile.
    for (int j = 0; j < Math.min(piles.get(i).size(), k); ++j) {
      val += piles.get(i).get(j);
      res = Math.max(res, val + maxValueOfCoins(piles, i + 1, k - j - 1, mem));
    }

    return mem[i][k] = res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def maxValueOfCoins(self, piles: list[list[int]], k: int) -> int:
    @functools.lru_cache(None)
    def dp(i: int, k: int) -> int:
      """Returns the maximum value of picking k coins from piles[i..n)."""
      if i == len(piles) or k == 0:
        return 0

      # Pick no coins from the current pile.
      res = dp(i + 1, k)
      val = 0  # the coins picked from the current pile

      # Try to pick 1, 2, ..., k coins from the current pile.
      for j in range(min(len(piles[i]), k)):
        val += piles[i][j]
        res = max(res, val + dp(i + 1, k - j - 1))

      return res

    return dp(0, k)