2218. Maximum Value of K Coins From Piles LeetCode Solution
In this guide, you will get 2218. Maximum Value of K Coins From Piles LeetCode Solution with the best time and space complexity. The solution to Maximum Value of K Coins From Piles problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 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:
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.
n == piles.length
1 <= n <= 1000
1 <= piles[i][j] <= 105
1 <= k <= sum(piles[i].length) <= 2000
Complexity Analysis
Time Complexity: O(\Sigma |\texttt{piles[i]}| \cdot k)
Space Complexity: O(nk)
2218. Maximum Value of K Coins From Piles LeetCode Solution in C++
class Solution {
public:
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
vector<vector<int>> mem(piles.size(), vector<int>(k + 1));
return maxValueOfCoins(piles, 0, k, mem);
}
private:
// Returns the maximum value of picking k coins from piles[i..n)
int maxValueOfCoins(const vector<vector<int>>& piles, int i, size_t k,
vector<vector<int>>& mem) {
if (i == piles.size() || k == 0)
return 0;
if (mem[i][k])
return mem[i][k];
// Pick no coins from the current pile.
int res = maxValueOfCoins(piles, i + 1, k, mem);
int val = 0; // the coins picked from the current pile
// Try to pick 1, 2, ..., k coins from the current pile.
for (int j = 0; j < min(piles[i].size(), k); ++j) {
val += piles[i][j];
res = max(res, val + maxValueOfCoins(piles, i + 1, k - j - 1, mem));
}
return mem[i][k] = res;
}
}; /* code provided by PROGIEZ */
2218. Maximum Value of K Coins From Piles LeetCode Solution in Java
class Solution {
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
Integer[][] mem = new Integer[piles.size()][k + 1];
return maxValueOfCoins(piles, 0, k, mem);
}
// Returns the maximum value of picking k coins from piles[i..n)
private int maxValueOfCoins(List<List<Integer>> piles, int i, int k, Integer[][] mem) {
if (i == piles.size() || k == 0)
return 0;
if (mem[i][k] != null)
return mem[i][k];
// Pick no coins from the current pile.
int res = maxValueOfCoins(piles, i + 1, k, mem);
int val = 0; // the coins picked from the current pile
// Try to pick 1, 2, ..., k coins from the current pile.
for (int j = 0; j < Math.min(piles.get(i).size(), k); ++j) {
val += piles.get(i).get(j);
res = Math.max(res, val + maxValueOfCoins(piles, i + 1, k - j - 1, mem));
}
return mem[i][k] = res;
}
} // code provided by PROGIEZ
2218. Maximum Value of K Coins From Piles LeetCode Solution in Python
class Solution:
def maxValueOfCoins(self, piles: list[list[int]], k: int) -> int:
@functools.lru_cache(None)
def dp(i: int, k: int) -> int:
"""Returns the maximum value of picking k coins from piles[i..n)."""
if i == len(piles) or k == 0:
return 0
# Pick no coins from the current pile.
res = dp(i + 1, k)
val = 0 # the coins picked from the current pile
# Try to pick 1, 2, ..., k coins from the current pile.
for j in range(min(len(piles[i]), k)):
val += piles[i][j]
res = max(res, val + dp(i + 1, k - j - 1))
return res
return dp(0, k) # code by PROGIEZ
