Problem Description

You are given an array piles where each piles[i] is a list of positive integers representing coins in the i-th pile, stacked from top to bottom. You can pick up to k coins in total from any of the piles, but you can only take coins from the top of each pile (i.e., you may not skip coins within a pile).

Your task is to maximize the total value of coins you pick by choosing at most k coins in total from all the piles. You cannot pick more than one coin at a time from a pile, and once you skip a coin in a pile, you cannot take any coin below it.

Constraints:

• Each pile's coins must be taken from the top down, in order.
• You may pick coins from any combination of piles, but the total number of coins picked across all piles must not exceed k.
• You cannot take more than one coin at a time from a pile, and you cannot revisit a pile after skipping a coin.

Thought Process

At first glance, this problem might seem to require checking all possible combinations of coins from the piles, but this quickly becomes infeasible as the number of piles and coins grows. The brute-force approach would involve considering every possible way to pick coins from each pile, which grows exponentially.

Instead, we can recognize this as a variant of the classic "Knapsack" problem, where each pile offers a set of choices (take 0, 1, ..., up to the pile's size coins), and we need to maximize the sum subject to the total number of coins not exceeding k.

This insight leads us to dynamic programming (DP): for each pile, and for each possible number of coins taken so far, we can compute the best total value. We build up solutions for smaller subproblems and use them to solve larger ones efficiently.

Solution Approach

We use dynamic programming to solve this problem efficiently. Here's how:

1. State Definition:
   • Let dp[i][j] represent the maximum value we can achieve using the first i piles and picking exactly j coins in total.
2. Initialization:
   • Set dp[0][0] = 0 (no piles, no coins, value zero).
   • All other dp[0][j] = -infinity for j > 0 (can't pick coins from zero piles).
3. Transition:
   • For each pile i, for each possible number of coins j (from 0 to k):
   • We consider taking x coins from the current pile, where x ranges from 0 up to min(len(piles[i]), j).
   • For each x, we calculate the sum of the top x coins in the pile (using prefix sums for efficiency), and update dp[i+1][j] as the maximum of its current value and dp[i][j-x] + sum of top x coins.
4. Result:
   • The answer is dp[n][k], where n is the number of piles.
5. Optimization:
   • Since we only ever look at the previous row, we can optimize space to a single 1D array.

This approach ensures we explore all valid ways to pick coins, but only once for each possible total, making it efficient.

Example Walkthrough

Input: piles = [[1,100,3],[7,8,9]], k = 2

Let's trace the steps:

• We have 2 piles: [1, 100, 3] and [7, 8, 9]. We can pick at most 2 coins in total.
• We compute prefix sums for each pile:
  • Pile 1: [0, 1, 101, 104] (0 coins, 1 coin, 2 coins, 3 coins)
  • Pile 2: [0, 7, 15, 24]
• We initialize dp = [0, 0, 0] (for 0, 1, 2 coins).
• For Pile 1:
  • Try taking 0, 1, or 2 coins:
    • 0 coins: dp[0]=0
    • 1 coin: dp[1]=1
    • 2 coins: dp[2]=101
• For Pile 2:
  • For each possible total coins (from 2 down to 0), try taking 0, 1, or 2 coins from this pile and update dp accordingly.
  • After considering all options, the best possible value is 101 (from taking 2 coins from pile 1), 15 (from taking 2 coins from pile 2), or 1+8=9 (1 from pile 1, 1 from pile 2), etc.
  • But the optimal is 1 from pile 1 (1) and 1 from pile 2 (7) = 8, or 100 from pile 1 and 0 from pile 2, etc.
  • But the true maximum is 101 (taking 2 from pile 1), or 100 (1 from pile 1, 1 from pile 2), or 1+9=10 (1 from pile 1, 1 from pile 2), but actually, the best is 100+9=109, but that's not possible because you can't take the second coin from pile 1 and the last from pile 2 at the same time.
  • By following the DP, we find that the answer is 101 (taking the first two from pile 1), or 100+7=107 (first from pile 1, first from pile 2), or 1+9=10 (first from both), etc.
  • But actually, the optimal is 101 (taking the first two from pile 1), or 100+7=107 (first from pile 1, first from pile 2). But you can't take 100 and 9 together. So, the DP helps us systematically try all valid combinations.
• Final answer: 101 (take 2 from pile 1), or 100+7=107 (take 1 from pile 1, 1 from pile 2), but the maximum is 101.

Time and Space Complexity

Brute-force:

• Time: Exponential, since for each pile you can make multiple choices, leading to O((max_pile_size+1)^num_piles).
• Space: Exponential for recursion stack and memoization.

• Time: O(n * k * m), where n = number of piles, k = max coins to pick, m = average pile size. This is because for each pile, we consider up to k coins, and for each, we try up to the size of the pile.
• Space: O(k), since we can optimize to a 1D DP array of size k+1.

The DP approach is efficient and feasible for the constraints given in the problem.

Summary

This problem is a variation of the knapsack problem, where each pile offers a set of choices for how many coins to take from its top. By using dynamic programming, we efficiently explore all valid ways to pick up to k coins across piles, always taking coins from the top down. The key insight is to use a DP table to store the best total value for each possible number of coins picked so far, updating it as we process each pile. This transforms an exponential brute-force problem into a polynomial-time solution, making it elegant and efficient.

Code Implementation

class Solution:
    def maxValueOfCoins(self, piles, k):
        n = len(piles)
        dp = [0] * (k + 1)
        for pile in piles:
            prefix = [0]
            for coin in pile:
                prefix.append(prefix[-1] + coin)
            for coins in range(k, 0, -1):
                for x in range(1, min(len(pile), coins) + 1):
                    dp[coins] = max(dp[coins], dp[coins - x] + prefix[x])
        return dp[k]
      

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        vector<int> dp(k + 1, 0);
        for (auto& pile : piles) {
            vector<int> prefix{0};
            for (int coin : pile)
                prefix.push_back(prefix.back() + coin);
            for (int coins = k; coins >= 1; --coins) {
                for (int x = 1; x <= min((int)pile.size(), coins); ++x) {
                    dp[coins] = max(dp[coins], dp[coins - x] + prefix[x]);
                }
            }
        }
        return dp[k];
    }
};
      

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int[] dp = new int[k + 1];
        for (List<Integer> pile : piles) {
            int[] prefix = new int[pile.size() + 1];
            for (int i = 0; i < pile.size(); ++i) {
                prefix[i + 1] = prefix[i] + pile.get(i);
            }
            for (int coins = k; coins >= 1; --coins) {
                for (int x = 1; x <= Math.min(pile.size(), coins); ++x) {
                    dp[coins] = Math.max(dp[coins], dp[coins - x] + prefix[x]);
                }
            }
        }
        return dp[k];
    }
}
      

var maxValueOfCoins = function(piles, k) {
    let dp = new Array(k + 1).fill(0);
    for (let pile of piles) {
        let prefix = [0];
        for (let coin of pile) {
            prefix.push(prefix[prefix.length - 1] + coin);
        }
        for (let coins = k; coins >= 1; --coins) {
            for (let x = 1; x <= Math.min(pile.length, coins); ++x) {
                dp[coins] = Math.max(dp[coins], dp[coins - x] + prefix[x]);
            }
        }
    }
    return dp[k];
};