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
30
class Solution {
 public:
  int maxValueOfCoins(vector<vector<int>>& piles, int k) {
    // dp[i][k] := max value of picking k coins from piles[i:]
    dp.resize(piles.size(), vector<int>(k + 1));
    return maxValueOfCoins(piles, 0, k);
  }

 private:
  vector<vector<int>> dp;

  int maxValueOfCoins(const vector<vector<int>>& piles, int i, size_t k) {
    if (i == piles.size() || k == 0)
      return 0;
    if (dp[i][k])
      return dp[i][k];

    int ans =
        maxValueOfCoins(piles, i + 1, k);  // Pick 0 coins from current pile
    int val = 0;                           // Coins picked from current pile

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

    return dp[i][k] = ans;
  }
};

 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
class Solution {
  public int maxValueOfCoins(List<List<Integer>> piles, int k) {
    // dp[i][k] := max value of picking k coins from piles[i:]
    dp = new Integer[piles.size()][k + 1];
    return maxValueOfCoins(piles, 0, k);
  }

  private Integer[][] dp;

  private int maxValueOfCoins(List<List<Integer>> piles, int i, int k) {
    if (i == piles.size() || k == 0)
      return 0;
    if (dp[i][k] != null)
      return dp[i][k];

    int ans = maxValueOfCoins(piles, i + 1, k); // Pick 0 coins from current pile
    int val = 0;                                // Coins picked from current pile

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

    return dp[i][k] = ans;
  }
}

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

      ans = dp(i + 1, k)  # Pick 0 coins from current pile
      val = 0  # Coins picked from current pile

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

      return ans

    return dp(0, k)