Maximum Value of K Coins from Piles - Leetcode 2218 - Python
Vložit
- čas přidán 27. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Solving Leetcode 2218 - Maximum Values of Coins from Piles, today's daily leetcode problem on april 14th.
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/maximum...
0:00 - Read the problem
0:30 - Drawing Explanation
9:40 - Coding Explanation
leetcode 2218
#neetcode #leetcode #python
Even if it's not the most impressive accomplishment, I made it into Uber's Career Prep program due to your vides neetcode, and I continue to prep for my official internship interview with them through your videos too, so wish me luck with my LC journey.
Congratulations and best of luck! Your hard work will pay off!!
I love you neetcode
Thank you for this explanation!
btw 3d dp is giving mle , thanks for the solution though!
Great explanation as always
Thank you for the explanation, helped a lot! I was just wondering why the caching is needed as this is my first time encountering a caching problem. Could anyone explain to me? Thanks in advance!
Thank you so much
thanks bro
In the decision tree, once we select 1 from first pile, and we move to second pile, and select 7 the parameters should be 1,0 isn’t it?
Nice explanation! keep posting coding solutions vineet!
who is vineet
was able to come up with a memoized solution but TLE after passing 77 test cases :(... Converting memoized code to tabulated code is certainly tricky... Any advice on the same from folks here?
int maxValueOfCoins(vector& piles, int k) {
int n = piles.size();
vector dp(k + 1, 0);
vector temp(k + 1, 0);
for (int i = n - 1; i >= 0; i--) {
vector &pile = piles[i];
int size = pile.size();
for (int coins = 1; coins
Once you got the recursive, memoized version written down clearly, it ain't that bad.
First, let's look at the parameters we got: i, coins. Start by filling in all the base cases in your dp array. In this problem, the only base case is for i == n, thus we can set dp[n][k] = 0 for all possible values of k.
Next, simply follow the places where you update your memo array/hashmap. On line 15, we have "dp[i][coins] = dfs(i + 1, coins)" which would translate into "dp[i][coins] = dp[i + 1][coins]". This might already give the hint that we need to fill the dp-array in decreasing order of parameter i (since dp[i][k] depends on dp[i + 1][k]).
On line 19, we have "dp[i][coins] = max(dp[i][coins], curPile + dfs(i + 1, coins - j - 1)" which translates into
"dp[i][coins] = max(dp[i][coins], curPile + dp[i + 1][coins - j - 1]". Again, we can see that dp[i][coins] depends on dp[i + 1][coins - j - 1], where coins - j - 1 < coins. So it seems like the second parameter, coins, needs to be filled in increasing order!
So, if we ensure that we always compute dp[i + 1][k] before dp[i][k], then we're good. Likewise, we need to make sure that we first compute the result for 0 coins, then 1 coin, 2 coins, etc.
The hard thing about tabulation is that we need to carefully think about the parameters dependencies, while in the recursive version it is "hidden" behind the more intuitive recursive calls.
It might look something like this:
n = len(piles)
dp = [[-1] * (k + 1) for _ in range(n)]
# base cases
for k in range(k + 1):
dp[n][k] = 0
for i in range(n - 1, 0, -1):
for k in range(k + 1):
dp[i][k] = dp[i + 1][k]
curPile = 0
for j in range(min(coins, len(piles[i]))):
curPile += piles[i][j]
dp[i][k] = max(dp[i][k], curPile + dp[i + 1][k - j - 1])
Why can't we use a heap to greedily pick up the max value ? In that case klog(n) right?
I think the first example shows that a heap solution won't work (proof by contradiction)
We shouldn't add all the elements from a pile. Just the topmost element of every pile. In the heap, we can store the (value, index of pile) as the entry
@@lakshmanvengadesan9096 It will not return the correct answer. Like if you consider the given example, It will compare 1 and 7 and picks 7, and then it will compare 1 and 8, it will pick 8. so it return 15 which is wrong. We have to consider all the combinations.
@@tanish5662 cool, i see the point now
I don't think anyone could come up with this solution during a 30 min interview, or its just me ?
I understood what I need to do but no way on earth would I be able to code it lol
@@annoyingorange90 you can do it man!only if you hve seen this problem atleast once before it appears in interview...
Competitive programming peeps probably could, keeping in mind that they practiced such problems for years.
thank you :orz:
if I write this inside loop
take = Math.max(sum+helper(i+1,k-j-1,piles,dp),take);
why I have to take max with take itself..
because you are taking max till now will choosing till now coins inside piles and and moving next piles selecting their coins or not both
I don't even understand what the problem is asking >.
hey man I hope everything is alright with you , your keystrokes are concerning. Take care man. Probably my assumption is wrong
Not too sure why we we had right node of parent 0 to be 0. Why can’t it be 7 from second pile?
Aliens 👽 👽 attendance taken by here ⊂(◉‿◉)つ
Did you figure it out by yourself or saw the solution?
He is not god of LeetCode.