2218. Maximum Value of K Coins From Piles

Problem Description

Given n piles of coins, where each pile piles[i] is a list of integers representing the coins' values from top to bottom, and a positive integer k, find the maximum total value of coins you can obtain by choosing exactly k coins optimally. In one move, you can choose any coin on top of any pile, remove it, and add its value to your wallet.

Solution: Dynamic Programming

This problem can be efficiently solved using dynamic programming. We can define a DP table dp[i][j] to represent the maximum value achievable by picking j coins from the first i piles.

Approach:

1. Initialization: dp[0][j] = 0 for all j, as no coins can be picked from zero piles. dp[i][0] = 0 for all i, as picking zero coins results in zero value.

2. Iteration: Iterate through the piles and coins. For each pile i and number of coins j, consider all possible numbers of coins (h) to pick from the current pile (0 to min(j, len(piles[i]))). The maximum value for dp[i][j] is the maximum of:

   • Not picking any coins from the current pile: dp[i-1][j]
   • Picking h coins from the current pile: dp[i-1][j-h] + sum_of_first_h_coins_in_pile_i

3. Prefix Sum Optimization: To efficiently calculate the sum of the first h coins in a pile, we precompute a prefix sum array for each pile. This reduces the time complexity of summing coins.

4. Result: The final result is dp[n][k], representing the maximum value achievable by picking k coins from all n piles.

Space Optimization:

The DP table can be optimized to use only a 1D array. Since we only need the previous row's values to calculate the current row's values, we can iterate backwards through the number of coins (j), overwriting the DP array in place.

Code Implementation (Python)

Solution 1 (2D DP):

from itertools import accumulate
 
class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        dp = [[0] * (k + 1) for _ in range(n + 1)]
 
        for i in range(1, n + 1):
            prefix_sums = list(accumulate(piles[i - 1], initial=0))
            for j in range(1, k + 1):
                dp[i][j] = dp[i - 1][j]  # Option: Don't pick from current pile
                for h in range(1, min(j, len(piles[i - 1])) + 1):
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - h] + prefix_sums[h])
 
        return dp[n][k]
 

Solution 2 (1D DP - Space Optimized):

from itertools import accumulate
 
class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        dp = [0] * (k + 1)
 
        for pile in piles:
            prefix_sums = list(accumulate(pile, initial=0))
            new_dp = dp[:] #create a copy to avoid overwriting during computation
            for j in range(k, -1, -1):
                for h in range(1, min(j, len(pile)) + 1):
                    new_dp[j] = max(new_dp[j], dp[j-h] + prefix_sums[h])
            dp = new_dp #update dp with new_dp
 
        return dp[k]

Time and Space Complexity Analysis

Solution 1 (2D DP):

• Time Complexity: O(n * k * m), where n is the number of piles, k is the number of coins to pick, and m is the maximum number of coins in a single pile. The nested loops iterate through piles, coins to pick, and coins within a pile.
• Space Complexity: O(n * k) to store the DP table.

Solution 2 (1D DP):

• Time Complexity: O(n * k * m) - Same as the 2D DP solution.
• Space Complexity: O(k) - Significantly reduced space complexity due to the 1D array.

The space-optimized solution is preferred because it uses significantly less memory, especially when n and k are large. Both solutions have the same time complexity. The prefix sum optimization is crucial in both solutions to avoid redundant calculations within each pile.