< Back





2218. Maximum Value of K Coins From Piles

This can be solved using knapsack, but I'll show the recursive dynamic programming solution because
it's easier to understand. With dynamic programming, we know we need to use memoization to avoid
recalculating solutions for states we've already visited. We learn that states in this problem are
defined by the current pile of coins we're visiting, and the number of coins we've already selected.

During our recursion, we'll check to see if we've memoized the current state - if so we return the
answer. Otherwise, starting from the last pile, we keep a current sum to track the value of the coins
we've taken. We start from 0, and take as many coins as possible from the pile or from the number of
coins we're still allowed to take.

We recursively call this function on the next pile of coins, keeping track of the number of coins
we've already selected.

The solution is as follows:


  class Solution:
      def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
          n = len(piles)
          lengths = [len(pile) for pile in piles]
          memo = [[-1 for _ in range(k + 1)] for _ in range(n + 1)]

          def dp(i: int, c: int) -> int:
              if not i:
                  return 0

              if memo[i][c] != -1:
                  return memo[i][c]

              curr_sum = 0

              for curr_coins in range(0, min(lengths[i - 1], c) + 1):
                  if curr_coins > 0:
                      curr_sum += piles[i - 1][curr_coins - 1]

                  memo[i][c] = max(memo[i][c], curr_sum + dp(i - 1, c - curr_coins))

              return memo[i][c]

          return dp(n, k)


_ Time Complexity:

  O(n * k) - Where n is the number of piles and k is the number of coins we're allowed to take.

_ Space Complexity:

  O(n * k) - Our recursive call stack can grow to a maximum of n * k.