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.
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!
I'm a year late, but for anyone else wondering: In this example, caching stores values when we calculate them because we may use them again soon. And in short, it is faster to read from the cache than it is to calculate the value again. The Depth-First Search approach explores all possibilities in all ordered, which can lead to revisiting the same subproblems multiple times. For instance, if you have 3 piles, |1| |4| |3| |5| |2| |6| and you took one coin from pile 1, and then 2 coins from pile 3, you know that taking 2 coins from pile 3 will get you +9 to your total. Well now what if you took 1 coin from pile 2 and then took 2 coins from pile 3? Pile 3 will still get you +9 to your current total. Since we already found this out earlier, it makes more sense to store this info in the cache. This is a very simple example though, imagine if the piles were much larger and you had already calculated the amount you'd get for pulling 25 coins from pile 12. It is much fast to just check "what happens when I have this many coins at pile 3?" than it is to calculate that amount multiple times. With caching, the time complexity is O(n*k). Without caching, the time complexity is O(k^n), an exponential time complexity which is always best to avoid if possible. Caching (memoization) is very helpful in dynamic programming problems and you might have used it before without realizing it. It is a small space complexity tradeoff for a big time complexity pay off.
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])
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.
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
I always find the top-down approach much more understandable than bottom-up.
btw 3d dp is giving mle , thanks for the solution though!
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?
Thank you for this explanation!
Great explanation as always
Thank you so much
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 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!
I'm a year late, but for anyone else wondering:
In this example, caching stores values when we calculate them because we may use them again soon. And in short, it is faster to read from the cache than it is to calculate the value again.
The Depth-First Search approach explores all possibilities in all ordered, which can lead to revisiting the same subproblems multiple times. For instance, if you have 3 piles,
|1| |4| |3|
|5| |2| |6|
and you took one coin from pile 1, and then 2 coins from pile 3, you know that taking 2 coins from pile 3 will get you +9 to your total.
Well now what if you took 1 coin from pile 2 and then took 2 coins from pile 3? Pile 3 will still get you +9 to your current total. Since we already found this out earlier, it makes more sense to store this info in the cache.
This is a very simple example though, imagine if the piles were much larger and you had already calculated the amount you'd get for pulling 25 coins from pile 12. It is much fast to just check "what happens when I have this many coins at pile 3?" than it is to calculate that amount multiple times.
With caching, the time complexity is O(n*k).
Without caching, the time complexity is O(k^n), an exponential time complexity which is always best to avoid if possible.
Caching (memoization) is very helpful in dynamic programming problems and you might have used it before without realizing it. It is a small space complexity tradeoff for a big time complexity pay off.
thanks bro
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 even understand what the problem is asking >.
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
Nice explanation! keep posting coding solutions vineet!
who is vineet
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.