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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4
5
6

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.

Solution

Method 1 – Top Down DP with Memoization

Intuition

We use recursion with memoization to explore all ways to pick coins from piles, keeping track of the best sum for each state. At each pile, we can skip it or take coins from the top, and recursively solve for the remaining piles and coins.

Approach

  1. Define a recursive function with parameters: current pile index and remaining coins to pick.
  2. If no coins left or all piles considered, return 0.
  3. For each pile, try all possible numbers of coins to take (from 0 up to min(k, pile size)).
  4. For each choice, add the sum of selected coins and recursively solve for the next pile and remaining coins.
  5. Use memoization to avoid recomputation.
Recurrence Relation

Let f(idx, k) be the maximum value from piles starting at index idx with k coins left to pick.

1
2
3
4

f(idx, k) = max(
	f(idx + 1, k),
	max(sum of first j coins from piles[idx] + f(idx + 1, k - j)) for j = 1 to min(k, len(piles[idx]))
)
Base Case
  • if k == 0, i.e. you can’t pick any coin then ans = 0
  • If idx == len(piles), you don’t have any piles then ans = 0

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
	int maxValueOfCoins(vector<vector<int>>& piles, int k) {
		int n = piles.size();
		vector<vector<int>> dp(n + 1, vector<int>(k + 1, -1));
		return helper(piles, dp, 0, k);
	}
private:
	int helper(const vector<vector<int>>& piles, vector<vector<int>>& dp, int idx, int k) {
		if (idx == piles.size() || k == 0) return 0;
		if (dp[idx][k] != -1) return dp[idx][k];
		int ans = helper(piles, dp, idx + 1, k);
		int sum = 0;
		for (int i = 0; i < min((int)piles[idx].size(), k); ++i) {
			sum += piles[idx][i];
			ans = max(ans, sum + helper(piles, dp, idx + 1, k - i - 1));
		}
		return dp[idx][k] = ans;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func maxValueOfCoins(piles [][]int, k int) int {
	n := len(piles)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, k+1)
		for j := range dp[i] {
			dp[i][j] = -1
		}
	}
	var helper func(idx, rem int) int
	helper = func(idx, rem int) int {
		if idx == n || rem == 0 {
			return 0
		}
		if dp[idx][rem] != -1 {
			return dp[idx][rem]
		}
		ans, sum := helper(idx+1, rem), 0
		for i := 0; i < len(piles[idx]) && i < rem; i++ {
			sum += piles[idx][i]
			ans = max(ans, sum+helper(idx+1, rem-i-1))
		}
		dp[idx][rem] = ans
		return ans
	}
	return helper(0, k)
}
func max(a, b int) int { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
	public int maxValueOfCoins(List<List<Integer>> piles, int k) {
		int n = piles.size();
		Integer[][] dp = new Integer[n + 1][k + 1];
		return helper(piles, dp, 0, k);
	}
	private int helper(List<List<Integer>> piles, Integer[][] dp, int idx, int k) {
		if (idx == piles.size() || k == 0) return 0;
		if (dp[idx][k] != null) return dp[idx][k];
		int ans = helper(piles, dp, idx + 1, k);
		int sum = 0;
		for (int i = 0; i < Math.min(piles.get(idx).size(), k); i++) {
			sum += piles.get(idx).get(i);
			ans = Math.max(ans, sum + helper(piles, dp, idx + 1, k - i - 1));
		}
		return dp[idx][k] = ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
	fun maxValueOfCoins(piles: List<List<Int>>, k: Int): Int {
		val n = piles.size
		val dp = Array(n + 1) { Array(k + 1) { -1 } }
		fun helper(idx: Int, rem: Int): Int {
			if (idx == n || rem == 0) return 0
			if (dp[idx][rem] != -1) return dp[idx][rem]
			var ans = helper(idx + 1, rem)
			var sum = 0
			for (i in 0 until minOf(piles[idx].size, rem)) {
				sum += piles[idx][i]
				ans = maxOf(ans, sum + helper(idx + 1, rem - i - 1))
			}
			dp[idx][rem] = ans
			return ans
		}
		return helper(0, k)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from typing import List
class Solution:
	def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
		n = len(piles)
		dp = [[-1] * (k + 1) for _ in range(n + 1)]
		def helper(idx: int, rem: int) -> int:
			if idx == n or rem == 0:
				return 0
			if dp[idx][rem] != -1:
				return dp[idx][rem]
			ans = helper(idx + 1, rem)
			s = 0
			for i in range(min(len(piles[idx]), rem)):
				s += piles[idx][i]
				ans = max(ans, s + helper(idx + 1, rem - i - 1))
			dp[idx][rem] = ans
			return ans
		return helper(0, k)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
	pub fn max_value_of_coins(piles: Vec<Vec<i32>>, k: i32) -> i32 {
		let n = piles.len();
		let mut dp = vec![vec![-1; (k + 1) as usize]; n + 1];
		fn helper(piles: &Vec<Vec<i32>>, dp: &mut Vec<Vec<i32>>, idx: usize, rem: i32) -> i32 {
			if idx == piles.len() || rem == 0 { return 0; }
			if dp[idx][rem as usize] != -1 { return dp[idx][rem as usize]; }
			let mut ans = helper(piles, dp, idx + 1, rem);
			let mut sum = 0;
			for i in 0..std::cmp::min(piles[idx].len(), rem as usize) {
				sum += piles[idx][i];
				ans = std::cmp::max(ans, sum + helper(piles, dp, idx + 1, rem - (i as i32) - 1));
			}
			dp[idx][rem as usize] = ans;
			ans
		}
		helper(&piles, &mut dp, 0, k)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
	maxValueOfCoins(piles: number[][], k: number): number {
		const n = piles.length;
		const dp: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(-1));
		function helper(idx: number, rem: number): number {
			if (idx === n || rem === 0) return 0;
			if (dp[idx][rem] !== -1) return dp[idx][rem];
			let ans = helper(idx + 1, rem);
			let sum = 0;
			for (let i = 0; i < Math.min(piles[idx].length, rem); i++) {
				sum += piles[idx][i];
				ans = Math.max(ans, sum + helper(idx + 1, rem - i - 1));
			}
			dp[idx][rem] = ans;
			return ans;
		}
		return helper(0, k);
	}
}

Complexity

  • ⏰ Time complexity: O(n * k * m) — n = number of piles, k = coins to pick, m = max coins in a pile. For each pile and coin count, we try all possible coins from the pile.
  • 🧺 Space complexity: O(n * k) — DP table stores results for each pile and coin count.

Method 2 – Bottom Up DP

Intuition

We use dynamic programming to build up the answer iteratively. For each pile and each possible number of coins to pick, we compute the best value by considering all ways to take coins from the current pile and combine with previous results.

Approach

  1. Create a DP table dp[i][j] where i is the number of piles considered and j is the number of coins picked.
  2. Initialize dp[0][*] = 0 (no piles, no coins).
  3. For each pile, for each possible number of coins to pick, try all ways to take coins from the current pile (from 0 up to min(j, pile size)).
  4. Update dp[i][j] as the maximum of not taking any coins from the current pile or taking some coins and adding their sum to the best result from previous piles.

Recurrence Relation:

Let dp[i][j] be the max value using first i piles and picking j coins.

1
2
3
4

dp[i][j] = max(
	dp[i-1][j],
	max(sum of first l coins from piles[i-1] + dp[i-1][j-l]) for l = 1 to min(j, len(piles[i-1]))
)

Base Case:

  • dp[0][*] = 0 (no piles, no coins)
  • dp[*][0] = 0 (no coins to pick)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
	int maxValueOfCoins(vector<vector<int>>& piles, int k) {
		int n = piles.size();
		vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
		for (int i = 1; i <= n; ++i) {
			for (int j = 0; j <= k; ++j) {
				int sum = 0;
				dp[i][j] = dp[i-1][j];
				for (int l = 1; l <= min(j, (int)piles[i-1].size()); ++l) {
					sum += piles[i-1][l-1];
					dp[i][j] = max(dp[i][j], sum + dp[i-1][j-l]);
				}
			}
		}
		return dp[n][k];
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func maxValueOfCoins(piles [][]int, k int) int {
	n := len(piles)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, k+1)
	}
	for i := 1; i <= n; i++ {
		for j := 0; j <= k; j++ {
			sum := 0
			dp[i][j] = dp[i-1][j]
			for l := 1; l <= j && l <= len(piles[i-1]); l++ {
				sum += piles[i-1][l-1]
				if val := sum + dp[i-1][j-l]; val > dp[i][j] {
					dp[i][j] = val
				}
			}
		}
	}
	return dp[n][k]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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++) {
			for (int j = 0; j <= k; j++) {
				int sum = 0;
				dp[i][j] = dp[i-1][j];
				for (int l = 1; l <= Math.min(j, piles.get(i-1).size()); l++) {
					sum += piles.get(i-1).get(l-1);
					dp[i][j] = Math.max(dp[i][j], sum + dp[i-1][j-l]);
				}
			}
		}
		return dp[n][k];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	fun maxValueOfCoins(piles: List<List<Int>>, k: Int): Int {
		val n = piles.size
		val dp = Array(n + 1) { IntArray(k + 1) }
		for (i in 1..n) {
			for (j in 0..k) {
				var sum = 0
				dp[i][j] = dp[i-1][j]
				for (l in 1..minOf(j, piles[i-1].size)) {
					sum += piles[i-1][l-1]
					dp[i][j] = maxOf(dp[i][j], sum + dp[i-1][j-l])
				}
			}
		}
		return dp[n][k]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from typing import List
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):
			for j in range(k + 1):
				s = 0
				dp[i][j] = dp[i-1][j]
				for l in range(1, min(j, len(piles[i-1])) + 1):
					s += piles[i-1][l-1]
					dp[i][j] = max(dp[i][j], s + dp[i-1][j-l])
		return dp[n][k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
	pub fn max_value_of_coins(piles: Vec<Vec<i32>>, k: i32) -> i32 {
		let n = piles.len();
		let k = k as usize;
		let mut dp = vec![vec![0; k + 1]; n + 1];
		for i in 1..=n {
			for j in 0..=k {
				let mut sum = 0;
				dp[i][j] = dp[i-1][j];
				for l in 1..=std::cmp::min(j, piles[i-1].len()) {
					sum += piles[i-1][l-1];
					dp[i][j] = std::cmp::max(dp[i][j], sum + dp[i-1][j-l]);
				}
			}
		}
		dp[n][k]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	maxValueOfCoins(piles: number[][], k: number): number {
		const n = piles.length;
		const dp: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
		for (let i = 1; i <= n; i++) {
			for (let j = 0; j <= k; j++) {
				let sum = 0;
				dp[i][j] = dp[i-1][j];
				for (let l = 1; l <= Math.min(j, piles[i-1].length); l++) {
					sum += piles[i-1][l-1];
					dp[i][j] = Math.max(dp[i][j], sum + dp[i-1][j-l]);
				}
			}
		}
		return dp[n][k];
	}
}

Complexity

  • ⏰ Time complexity: O(n * k * m) — n = number of piles, k = coins to pick, m = max coins in a pile. For each pile and coin count, we try all possible coins from the pile.
  • 🧺 Space complexity: O(n * k) — DP table stores results for each pile and coin count.