Cherry Pickup II - Leetcode 1463 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/cherry-...
0:00 - Read the problem
0:25 - Memoization Explanation
5:39 - Coding Memoization
11:01 - Memory Optimized DP Explanation
17:56 - Coding Memory Optimized DP
leetcode 1463
#neetcode #leetcode #python

[@lPABLO_GAMING]

This is a certified Neetcode classic. thanks for continuing my streak 💯

[@byduhlusional]

I'm trying to learn DP and every time I come across a daily problem with DP I watch your videos. I just want to say I appreciate you showing us the top down approach instead of going straight into using tabulation. It's more effort but it is appreciated.

[@chrisnieves3881]

Amazon intern interview thursday pray for me mr neetcode please

[@NeetCodeIO]

You got this!!! 💪

[@miaowcat1]

In dfs, doing min, max(c1,c2) to check boundary is neat. Could probably apply in different problems like number of islands for boundary checks.

[@BlunderArmour]

Neato! I like your recursion to DP approach a lot. I got stuck at the DP solution when I tried to do it myself. But your video helps me understand how to develop the right way of thinking. Thank you!

[@trihoang2863]

What a difficult problem. Thank you!

[@jiteshpahwa266]

Great explanation !! Thankyou :)

[@pastori2672]

lost my sanity trying to get the dp solution

[@peachpink2831]

Since we have a symmetric matrix we can optimize the final approach even more by operating on just top right and bottom left triangle matrix alternatively. This will reduce the memory by half but will take longer to write.

[@lPABLO_GAMING]

neato btw, the hint leetcode gave scared me. also i can see why you consider this problem to be easier than cherry pickup 1, looks like a nightmare

[@ishanpadalkar9072]

Gave up trying to understand the code for the second approach lol. Will return with a fresher mind.

[@karthikb547]

Thanks man :)

[@krateskim4169]

Thank you neato

[@KnightMirkoYo]

The memo approach fails with TLE in Java on the last test case, so I have to do DP and it's Sunday 😪
Thank you so much, couldn't do it without you.

[@user-xz5iw1wf9w]

Nope it passes

[@KnightMirkoYo]

@@user-xz5iw1wf9w yeah, I had a bug which caused my memo array to do nothing. Now it's alright :)

[@user-xz5iw1wf9w]

Can you please post video solutions of weekly contests it will be really helpful to understand those problems which we aren't able to solve .By seeing your videos we can easly upsolve the problem using initial hints during first half of the video

[@aazzrwadrf]

this was the first hard i solved

[@VijaySharma-nu5lz]

In the memoization approach(1st approach), can anyone tell me how to print the path of individual robots as well along with returning the results? Thanks.

[@user-gs7xf6qt4l]

keeping a prev[][] matrix may help

[@dingus2332]

ah man , this was solvable , I just jumped to seeing the solution

[@user-vu8jp3si2r]

Why it should return 0 if c1 and c2 is same, instead of return maximum values from dfs(r+1, all possible column)
?

[@NeetCodeIO]

We dont need to ever consider the case where c1 and c2 are the same, because it will never lead to the maximal result. I gave a short summary of why, it's basically a proof by contradiction.

[@sdemji]

would it work to take the maximum cost route, remove it, then take the new maximum route again ? short answer : nope

[@Pegasus02Kr]

me seeing Neetcode's recursive solutions: "I can pretty much do it alone!"
me seeing Neetcode's tabulation solution: "Forget it, I can't"

[@user-vu8jp3si2r]

Why it should return 0 if c1 and c2 is same, instead of return arr[r][c1] + 0 + maximum values from dfs(r+1, all possible column)
?

[@clouds_304]

I was wondering the same. But then i remembered he said in the beginning, the case where both robots land on zhe same grid will not be part of the best solution. So if it happens we just give up and return 0

[@andrewqian9029]

Neetcode if you can here me, please save me. I have interview tmrw morning, please lend me ur strength

[@parikxit]

neat

[@kirillzlobin7135]

Leetcode 2267 Would be interesting to solve. Please please please

[@deathbombs]

I got this in first submission lol

[@HuyLe-tu4pj]

Is this a subchannel of Neetcode?

[@NeetCodeIO]

yeah

[@nikolaspische9378]

​@@NeetCodeIOHey what if i calculate the optional sum for robot 1 and marked the place which i have picked for optimal sum as visited and for the same calculate for robot2 but don't visit the already visited places and try finding out optimal sum for robot 2. at the end we can return Robot1 sum+ robot 2 sum . Is it goin to work???

[@NeetCodeIO]

No, proof by contradiction:
1 1 1
10 1 1
10 1 100
Your robot 1 will take (1 + 1 + 100).
Your robot 2 will take (1 + 1 + 1).
But the answer is (1 + 10 + 10) + (1 + 1 + 100)

[@furkanozbay]

@@nikolaspische9378 I had the same idea, thought run dfs for each robot (total 2) and spent much time to work it out but as NeetCode replied it will not lead to correct answer.

[@akins4christ]

@@NeetCodeIO def cherryPickUp(self, grid: List[List[int]]) -> int:
NameError: name 'List' is not defined
using vim editor