Maximum Value of K Coins From Piles

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 i^th 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: piles = [[1,100,3],[7,8,9]], k = 2. Output: 101. Example 2: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7. Output: 706.

# Dynamic Programming Solution for Coin Collection

This problem is a classic example of dynamic programming where we aim to maximize the total value of coins collected from different piles given a constraint on the number of coins we can pick.

## 1. Naive Approach (Brute Force)

A brute-force approach would involve exploring all possible combinations of coins from each pile to find the combination that yields the maximum total value while respecting the coin limit `k`. However, this is highly inefficient as the number of combinations grows exponentially with the number of piles and the size of each pile. This approach has a time complexity of O(N^K), where N is the number of piles and K is the number of coins to pick, which makes it impractical for larger inputs.

## 2. Optimal Solution: Dynamic Programming

We can solve this problem efficiently using dynamic programming. We'll define a DP table `dp[i][j]` where `dp[i][j]` represents the maximum total value we can obtain by considering the first `i` piles and picking `j` coins.

### Algorithm

1.  Initialize a 2D array `dp` of size `(n + 1) x (k + 1)` with all values set to 0. `dp[i][j]` will store the maximum value achievable using the first `i` piles and picking `j` coins.
2.  Iterate through the piles from `1` to `n` (inclusive).
3.  For each pile `i`, iterate through the number of coins to pick from `0` to `k` (inclusive).
4.  For each number of coins `j`, iterate through the number of coins to pick from the current pile `x` from `0` to `min(j, size of current pile)`.
5.  Update `dp[i][j]` as `max(dp[i][j], dp[i-1][j-x] + sum of first x coins from pile i)`.
6.  Return `dp[n][k]`, which will contain the maximum value achievable using all `n` piles and picking `k` coins.

### Code Sample (Python)

```python
def max_value_of_coins(piles, k):
    n = len(piles)
    dp = [[0] * (k + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(k + 1):
            current_pile = piles[i - 1]
            m = len(current_pile)
            prefix_sum = [0] * (m + 1)
            for x in range(1, m + 1):
                prefix_sum[x] = prefix_sum[x - 1] + current_pile[x - 1]

            for x in range(min(j, m) + 1):
                dp[i][j] = max(dp[i][j], dp[i - 1][j - x] + prefix_sum[x])

    return dp[n][k]

# Example usage:
piles = [[1, 100, 3], [7, 8, 9]]
k = 2
print(max_value_of_coins(piles, k))  # Output: 101

piles = [[100], [100], [100], [100], [100], [100], [1, 1, 1, 1, 1, 1, 700]]
k = 7
print(max_value_of_coins(piles, k))  # Output: 706

3. Big(O) Run-time Analysis

• The outer loop runs n times (number of piles).
• The second loop runs k times (number of coins).
• The inner loop runs up to min(j, m) times, where m is the size of the current pile. In the worst case, this loop can run up to k times.
• Therefore, the time complexity is O(n * k * k) which simplifies to O(n * k^2).

4. Big(O) Space Usage Analysis

• We use a 2D DP table of size (n + 1) x (k + 1) to store the intermediate results.
• Therefore, the space complexity is O(n * k).

5. Edge Cases

• Empty piles: If any of the piles are empty, the algorithm should still work correctly as the inner loop will simply not iterate for that pile.
• k = 0: If k is 0, the algorithm should return 0, as no coins can be picked.
• k > total number of coins: If k is greater than the total number of coins available, the algorithm will still find the maximum possible value, which will be the sum of all coins.
• Large coin values: The coin values can be large (up to 10^5), so the DP table may store large values, but this does not affect the complexity of the algorithm.

By using dynamic programming, we can efficiently find the maximum total value of coins that can be obtained by picking exactly k coins from the given piles.