# Maximum Value of K Coins From Piles
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-value-of-k-coins-from-piles)
Canonical: https://scaleengineer.com/dsa/problems/maximum-value-of-k-coins-from-piles
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
There are `n` **piles** of coins on a table. Each pile consists of a **positive number** of coins of assorted denominations.

In one move, you can choose any coin on **top** of any pile, remove it, and add it to your wallet.

Given a list `piles`, where `piles[i]` is a list of integers denoting the composition of the `ith` pile from **top to bottom**, and a positive integer `k`, return _the **maximum total value** of coins you can have in your wallet if you choose **exactly**_ `k` _coins optimally_.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-value-of-k-coins-from-piles/image0.png) 

**Input:** piles = [[1,100,3],[7,8,9]], k = 2
**Output:** 101
**Explanation:**
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.

**Example 2:**

**Input:** piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
**Output:** 706
**Explanation:**
The maximum total can be obtained if we choose all coins from the last pile.

**Constraints:**

* `n == piles.length`
* `1 <= n <= 1000`
* `1 <= piles[i][j] <= 105`
* `1 <= k <= sum(piles[i].length) <= 2000`

# Approaches
## Top-Down Dynamic Programming with Memoization
This problem can be modeled as a variation of the knapsack problem. We need to make a sequence of choices: for each pile, how many coins to take? The goal is to maximize the total value for exactly `k` coins. This structure is perfect for dynamic programming. A natural way to approach this is using recursion with memoization (a top-down DP approach). We can define a recursive function `solve(i, k)` that computes the maximum value we can get by picking `k` coins from piles `i` to `n-1`.
**Time:** O(k * sum(piles[i].length)). There are `n * k` possible states for `(i, k)`. For each state, we iterate up to `piles[i].size()` times. The total complexity is the sum of `k * piles[i].size()` over all `i`, which simplifies to `O(k * sum(piles[i].length))`. Given the constraints, this is feasible. · **Space:** O(n * k) for the memoization table `memo`. The recursion depth can go up to `n`, so there's also O(n) space for the call stack.
**Pros:** Intuitive to derive from the problem's recursive nature.; Directly translates the problem's logic into code.
**Cons:** Can be slightly slower than iterative solutions due to function call overhead.; Space complexity of O(n*k) is not optimal for this problem.
### Explanation
The state of our recursion is `(i, k)`, where `i` is the index of the current pile we are considering, and `k` is the number of coins we still need to pick. The function `solve(i, k)` will return the maximum value obtainable from piles `i` onwards, given we need to pick `k` more coins. To avoid recomputing the same subproblems, we use a 2D array `memo[i][k]` for memoization. To efficiently get the sum of the top `x` coins, we can calculate it iteratively within the recursive function.

```java
import java.util.List;
import java.util.Arrays;

class Solution {
    private List<List<Integer>> piles;
    private int[][] memo;
    private int n;

    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        this.n = piles.size();
        this.piles = piles;
        this.memo = new int[n][k + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return solve(0, k);
    }

    private int solve(int i, int k) {
        if (i == n || k == 0) {
            return 0;
        }
        if (memo[i][k] != -1) {
            return memo[i][k];
        }

        // Option 1: Take 0 coins from the current pile
        int res = solve(i + 1, k);

        // Option 2: Take 1, 2, ... coins from the current pile
        int currentSum = 0;
        for (int j = 0; j < Math.min(piles.get(i).size(), k); j++) {
            currentSum += piles.get(i).get(j);
            res = Math.max(res, currentSum + solve(i + 1, k - (j + 1)));
        }

        return memo[i][k] = res;
    }
}
```
### Algorithm
1.  Define a recursive function, let's call it `solve(i, k)`, which will compute the maximum value obtainable from piles `i` to `n-1` given that we still need to pick `k` coins.
2.  **Base Cases:**
    *   If `i` reaches `n` (all piles considered) or `k` becomes 0 (no more coins can be picked), we can't gain any more value, so we return 0.
3.  **Memoization:** To avoid recomputing results for the same state `(i, k)`, we use a 2D array `memo[n][k+1]`. Before any computation, we check if `memo[i][k]` has already been computed. If so, we return the stored value.
4.  **Recursive Step:** For the current pile `i`, we explore all possibilities of how many coins to take from it.
    *   First, consider taking 0 coins from pile `i`. The value would be `solve(i + 1, k)`.
    *   Then, iterate through taking `x` coins from pile `i`, where `x` goes from 1 up to `min(k, piles.get(i).size())`.
    *   For each `x`, calculate the sum of the top `x` coins. The total value for this choice is `(sum of top x coins) + solve(i + 1, k - x)`.
    *   The result for `solve(i, k)` is the maximum value among all these possibilities.
5.  Store the computed result in `memo[i][k]` before returning.

## Bottom-Up Dynamic Programming (Tabulation)
This approach is an iterative version of the recursive solution, often called tabulation. It systematically builds up the solution from the smallest subproblems, which can be more efficient and avoids recursion limits. We use a 2D DP table, `dp[i][j]`, to store the maximum value obtainable by picking exactly `j` coins from the first `i` piles.
**Time:** O(k * sum(piles[i].length)). We have three nested loops. The outer loop runs `n` times, the middle loop `k` times, and the inner loop `piles[i-1].size()` times. The total complexity is `sum_{i=1 to n} (k * piles[i-1].size())`, which is `O(k * sum(piles[i].length))`. · **Space:** O(n * k) to store the DP table.
**Pros:** Avoids recursion overhead and potential stack overflow issues.; Often slightly faster in practice than the memoized version due to better memory locality.
**Cons:** The space complexity of O(n*k) can be large and is not optimal for this problem.
### Explanation
We define `dp[i][j]` as the maximum value using `j` coins from piles `0` to `i-1`. The table size will be `(n+1) x (k+1)`. We iterate through each pile and each possible number of total coins, and for each `(i, j)` pair, we decide how many coins `x` to take from the current pile `i-1`. The value is the sum of top `x` coins plus the value we got from previous `i-1` piles with `j-x` coins, which is `dp[i-1][j-x]`.

```java
import java.util.List;

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int n = piles.size();
        int[][] dp = new int[n + 1][k + 1];

        for (int i = 1; i <= n; i++) {
            List<Integer> currentPile = piles.get(i - 1);
            for (int j = 0; j <= k; j++) {
                // Option 1: Take 0 coins from the current pile
                dp[i][j] = dp[i - 1][j];
                
                int currentSum = 0;
                // Option 2: Take x > 0 coins from the current pile
                for (int x = 1; x <= Math.min(currentPile.size(), j); x++) {
                    currentSum += currentPile.get(x - 1);
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - x] + currentSum);
                }
            }
        }
        return dp[n][k];
    }
}
```
### Algorithm
1.  Define a 2D DP table `dp[n+1][k+1]`, where `dp[i][j]` stores the maximum value obtainable by picking exactly `j` coins from the first `i` piles.
2.  Initialize the table with zeros. `dp[0][j] = 0` and `dp[i][0] = 0` are the base cases, meaning 0 value if we have no piles or need to pick 0 coins.
3.  Iterate through each pile `i` from 1 to `n`.
4.  For each pile, iterate through the number of coins `j` from 1 to `k`.
5.  To calculate `dp[i][j]`, we consider the `(i-1)`-th pile. We can take `x` coins from this pile and `j-x` coins from the previous `i-1` piles. The value from the previous `i-1` piles is already computed as `dp[i-1][j-x]`.
6.  The transition formula is: `dp[i][j] = max(dp[i-1][j-x] + sum_of_top_x_coins_from_pile_(i-1))` where `x` ranges from 0 to `min(j, piles[i-1].size())`.
7.  The `x=0` case (taking no coins from the current pile) means `dp[i][j]` can be initialized to `dp[i-1][j]`. Then we iterate `x` from 1 upwards to consider taking coins.
8.  The final answer is the value in `dp[n][k]`.

## Space-Optimized Bottom-Up Dynamic Programming
We can optimize the space complexity of the bottom-up DP approach. Notice that to compute the values for the current pile `i` (i.e., `dp[i][...]`), we only need the values from the immediately preceding pile `i-1` (i.e., `dp[i-1][...]`). This dependency allows us to reduce the space complexity from `O(n*k)` to `O(k)`. We can use a single 1D array `dp[j]` to represent the maximum value achievable with `j` coins using the piles considered so far.
**Time:** O(k * sum(piles[i].length)). The time complexity remains the same as the previous approaches because the loop structure is fundamentally the same. · **Space:** O(k). We only need a 1D array of size `k+1`. This is a significant improvement over the previous approaches.
**Pros:** Optimal space complexity of O(k).; Maintains the same time efficiency as less space-efficient methods.
**Cons:** The logic of iterating backwards can be less intuitive for beginners compared to the 2D DP approach.
### Explanation
Let `dp[j]` be the maximum value we can obtain by picking `j` coins from the piles considered so far. We iterate through each pile and update this `dp` array. When considering a new pile, we update `dp[j]` by potentially taking `x` coins from this new pile. This requires the value for `j-x` coins from the previous piles, which is `dp[j-x]` (from the previous state). By iterating `j` from `k` down to 1, we ensure `dp[j-x]` holds the value from the previous iteration (before processing the current pile), thus correctly modeling the choice.

```java
import java.util.List;

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int[] dp = new int[k + 1];

        for (List<Integer> pile : piles) {
            // Iterate downwards to use dp values from the previous state (before this pile)
            for (int j = k; j >= 1; j--) {
                int currentSum = 0;
                for (int x = 1; x <= Math.min(pile.size(), j); x++) {
                    currentSum += pile.get(x - 1);
                    dp[j] = Math.max(dp[j], dp[j - x] + currentSum);
                }
            }
        }
        return dp[k];
    }
}
```
### Algorithm
1.  Initialize a 1D DP array `dp` of size `k+1` with all zeros. `dp[j]` will store the maximum value achievable with `j` coins.
2.  Iterate through each `pile` in the input `piles`.
3.  For each pile, we want to update the `dp` array. To do this correctly, we iterate the number of coins `j` from `k` down to 1. This backward iteration is crucial to ensure that when we calculate a new `dp[j]`, we are using `dp` values from the state *before* considering the current pile.
4.  Inside this loop, we iterate through the number of coins `x` to take from the current pile, from 1 up to `min(j, pile.size())`.
5.  Calculate the `currentSum` of the top `x` coins from the current pile.
6.  Update `dp[j]` with the maximum of its current value and the value from taking `x` coins from this pile: `dp[j] = max(dp[j], dp[j-x] + currentSum)`.
7.  After iterating through all piles, `dp[k]` will hold the maximum value for exactly `k` coins.

# Solutions
### Java

```java
class Solution {
public
  int maxValueOfCoins(List<List<Integer>> piles, int k) {
    int n = piles.size();
    List<int[]> presum = new ArrayList<>();
    for (List<Integer> p : piles) {
      int m = p.size();
      int[] s = new int[m + 1];
      for (int i = 0; i < m; ++i) {
        s[i + 1] = s[i] + p.get(i);
      }
      presum.add(s);
    }
    int[] dp = new int[k + 1];
    for (int[] s : presum) {
      for (int j = k; j >= 0; --j) {
        for (int idx = 0; idx < s.length; ++idx) {
          if (j >= idx) {
            dp[j] = Math.max(dp[j], dp[j - idx] + s[idx]);
          }
        }
      }
    }
    return dp[k];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxValueOfCoins(vector<vector<int>> &piles, int k) {
    vector<vector<int>> presum;
    for (auto &p : piles) {
      int m = p.size();
      vector<int> s(m + 1);
      for (int i = 0; i < m; ++i)
        s[i + 1] = s[i] + p[i];
      presum.push_back(s);
    }
    vector<int> dp(k + 1);
    for (auto &s : presum) {
      for (int j = k; ~j; --j) {
        for (int idx = 0; idx < s.size(); ++idx) {
          if (j >= idx)
            dp[j] = max(dp[j], dp[j - idx] + s[idx]);
        }
      }
    }
    return dp[k];
  }
};

```

### Python

```python
class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int: presum = [list(accumulate(p, initial=0)) for p in piles] n = len(piles) dp = [[0] * (k + 1) for _ in range(n + 1)] for i, s in enumerate(presum, 1): for j in range(k + 1): for idx, v in enumerate(s): if j >= idx: dp[i][j] = max(dp[i][j], dp[i - 1][j - idx] + v) return dp[- 1][- 1]

```