DP 13. Cherry Pickup II | 3D DP Made Easy | DP On Grids
ฝัง
- เผยแพร่เมื่อ 4 ก.ค. 2024
- Lecture Notes/C++/Java Codes: takeuforward.org/data-structu...
Problem Link:bit.ly/3KQELfy
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the problem cherry pickup question where we have two people moving from first row to the last row and this problem teaches us how to solve 3D DP.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.
Keeping a like target of 500 ❤✌🏼
sir, you are a gem. This playlist is flawless. Everything is perfect 😭.Wowwww.
target 5000 guyz
we're with you bhaiya :)
could someone find the bug in my code, 8/11 test cases are only passing, 3 of them are failing, please I am stuck unable to find the mistake, It would be a very great help if someone can find error in my code.
this is my code-
int maximumChocolates(int n, int m, vector &grid) {
// Write your code here.
int dp[n][m][m];
memset(dp, 0, sizeof(dp));
int dj[3] = {-1,0,1};
for (int i = 0; i < n; i++) {
for (int j1 = 0; j1 < m; j1++) {
for(int j2 = 0; j2 < m; j2++) {
if(i == 0 && (j1 != 0 || j2 != m-1)) continue;
int tmp = 0;
for(int dj1 = 0; dj1 < 3; dj1++) {
for(int dj2 = 0; dj2 < 3; dj2++) {
int jj1 = j1 + dj[dj1];
int jj2 = j2 + dj[dj2];
if (i-1 >= 0 && jj1 >= 0 && jj1 < m && jj2 >= 0 && jj2 < m) {
tmp = max(tmp, dp[i-1][jj1][jj2]);
}
}
}
dp[i][j1][j2] = grid[i][j1] + tmp;
if (j1 != j2) dp[i][j1][j2] += grid[i][j2];
}
}
}
int ans = 0;
for (int j1 = 0; j1 < m; j1++) {
for(int j2 = 0; j2 < m; j2++) {
ans = max(ans, dp[n-1][j1][j2]);
}
}
return ans;
}
Thanks In Advance
understood
Understood Sir !!!!
I was just thinking that We get that much of knowledge just free of cost!. Even if we enrolled any paid courses to learn dynamic programming, we didn't gain that ammount of knowledge seriously....
An Educator like you! Is bless 🙏..
At 0:57 i can see that it's 1 'O clock in the morning, really man you are putting lots of efforts in teaching.
This video is 24 carat pure gold 💛. I love the way you broke down the base case by explaining in what and all combinations Alice and Bob can end and easily made me understand the tabulation part. Hats off bro 🙇♂️🙇♂️
Bhai ye gold thora jada bhari nhi h ?
nhi @@scripter7676 😆
Hey Striver, huge thanks. I was following your dp series from the start and honestly your teaching is so good, the only problem of grid dp I couldn't solve myself is this one among those 6 grid problems. Rest I did it without watching anything, just by reading the question. Huge thanks. Your support means a lot! I hope you get all the things you deserve in life. God bless you, Sir.
The breakdown of question and writing the pseudocode was next level 🔥🔥. Pure gold!
No words man!!
The way you were space optimizing it...hats off!!
It seems to be a piece of cake for you..Great Content..and finally ...Understood
You point out the right way to think about DP problems that's why these problems becomes easy to solve.
Thank you so much sir, this is the best DP series out there. Literally no one teaches the way you do, 3 solutions to a single problem helps us to think in various dimensions very clearly, hats off sir!!!
okayyy😂
UNDERSTOOD!!!! Was mind blown after watching this video. Thanks for clearing all the concepts.
Dramatic striver....with a touch of humor n drama..... Teaching complex topics so easily..... I love you
i always struggle to make bottom up approach but your explanation is very easy to understand 🙏.keep it up and cover more hard problems.Thank you🤗
Really helpful...... Initially, I was more afraid of DP. By watching this playlist I am seeing my growth in thinking for these kinds of questions..Thank you a lot striver for guiding many of us.
Your way of teaching is amazing! Thanks For the entire Playlist.
You are great striver. I solved this problem myself (both recursion and tabulation ) by just getting idea to not to take i1 and i2 separately. Never got better teacher like you man. Awesome!! ❤❤
Small optimisation :
since all the values are +ve numbers.
We can choose to prune the call where j1 == j2 because that is anyway not counted in the final answer. Example code:
class Solution {
public:
int find(int x1, int y1, int y2, vector&dp, vector&g,
vector&mov) {
if(y1= g[0].size() || y2=g[0].size()) {
return -1e8;
}
if(x1==g.size()-1) {
if(y1 == y2) {
return g[x1][y1];
}
return g[x1][y1] + g[x1][y2];
}
if(dp[x1][y1][y2]!=-1)
return dp[x1][y1][y2];
int ans;
if(y1==y2) {
return -1e8; // prune the branch.
}
else
ans = g[x1][y1] + g[x1][y2];
int res = -1;
for(int i=0;i> dp(n, vector < vector < int >> (m, vector < int > (m, -1)));
vectormov = {-1,0,1};
return find(0,0,m-1,dp,grid,mov);
}
};
Wonderful solution and way of explaining. It makes the concept crystal clear with dynamics of the approach.
Legendary playlist for dynamic programming !!! And this video is 24 Carat pure gold.🏅
Left with no words to express appreciation to you man. An incredible playlist you have made. Just great
Series is very good, I solved this problem using memoization and tabulation both (but not space optimization) by myself as I watched all the previous videos(till 13)
Out of world explanation, i bow down to you striver!
i love the way you teach. in every lecture new concept will be introduced and the way you explain it is amazing. the problems that seems to difficult previosly now it seems to be very easy with help of you we are able to solve it in diffrent ways and with the advanced method.
Thank you man, I've failed to understand DP for a very long time. I was running out of motivation to start all over again but I did it anyway. I was able to solve this problem after recursion till space optimization by myself. Really happy about it. Thanks again♥
Raj bhaiya you are too good. Haven't seen anybody explaining so good on whole YT. Thank you so much.
wrote memoisation , tabulation and space optimisation on my own , really great Series , learning a lot 💚
bhai ye sab mat llikha krro , jo phale baar attempt karta h ,, half video dekhke ,, uske upper extra pressure aa jata h ki uss se bhi kudh solve ho jana chahiye
Understood well and clear, title describes lecture perfectly-> 3D DP made easy :)
Hey Striver, I think the base condition for i == row -1 in recursion is not necessary , as we are only considering the current block we are in, that is already taken care of in for loop, so simply we can make i out of bound as i == row_size and return 0, it works perfectly. Regardless, you are kind of a true teacher, big brother, Sir, mentor to me.. excellent explanation... already learned a lot from you and will learn from you more and more. Words can't describe my gratitude . Thanks. I solved all the grid problems myself in your dp series except this one. Thanks for giving me the confidence.
Great series so far, will mcm type of problems be covered in this series?
yes
Can't thank you enough! Amazing series.
Clearly understood💯💯. Thank you so much for this wonderful series.
Understood sir !! Wow , you are sooo good at explaining such complex topics!
you are just a game changer, hats off to you brother, no words to thank you
The breakDown was sooo good and we guys will never be afraid of any Dimentional Dp problem after this.
Amazing series!! Hats off to your efforts🙇♀️🙇♀️🙇♀️...Thank you so much for such valuable contents Bhaiya!!!
God Bless you, Striver! Your content is pure gold!
Striver these videos are truly worthy and amazing. Thank you very much
Sir,I have tried almost all stuffs of dp on yt,but the way you make understand is amazing
Simply awesome!! Explained a complex problem in a very simple manner :)
UNDERSTOOD.....Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
One Optimization we can do to make it easier: *If both alexa and bob reach the same column we won't consider that path, return 0*
Reason: *We will get less chocolates in this path as only one of them will pickup the chocolate and we won't get max chocolates*
Awesome series!!
not necessary as the one getting no chocolate right now may get more no. of chocolates ahead through this path.
@@arunainarunain8938 no, that path will be automatically covered in other traversals.
I've tried the above intuition, this is giving correct solution.
nice ! instead of returning just use j1!=j2 condition
How will you know if they are getting maximum chocolate on other path if they are not sharing same path..?
May be , other path includes many zeroes
Or
May be the path they are sharing at one point may lead to max for Alice and bob further, Hence maximum sum.
solved the problem by just watching upto 6:00. Thanks striver for the hard work you are putting to uplift the community.
thankyou sir, the problem when I read was very complicated but you made it smooth like butter
US !! Bhai Kya Soch Hya Apki ! Itna precise or to the point kaise soch lete ho? Purai Fatafati🔥
Tabulation code at 39:40
Space optimization at 42:30
Understood. Very well taught, crisp and clear
Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
I usually don't comment on TH-cam videos but, u are just awesome bro!! I wish I could approach problems step by step as like u do.
understood in one go and i cant believe it
thank you striver
The way he teaches... great ! Even a dumb fellow can understand!
Hats off striver!
As the series moves forward the concept become more and more clear.
I was asked a modified version of the same question (after reaching the bottom row, again move both to the top row) in my Samsung R&D online test, and I couldn't solve it. I wish I would have seen this video earlier. Thanks striver, your explanation was super clear. :)
is the modified problem available anywhere else?
@@ssc_-kn6os Search for "cherry pickup leetcode".
mai mnn ni skta ki koi itna acha dp padata hai not possible vrooo!!!!!!!!! hatss offf to uh mann👊👊👊👊
Conceptof base case 1. Destination and 2. Out of bound, is breathtaking
Understood after failing a lot and giving up for more than 6 times. Striver is the Greatest Ever.
741 is still one of the Hardest LC problems I have came accross infact Top 3.
This is cherry pick 2 ie Leetcode 1463
Watch the video/title of the video before commenting
@@raj2523 Well I already know that no need to tell.
Bastard this is not that problem, he can't solve that
So how's 1096 ??
What are two other problems ?
This explanation was seriously good, great work!
what an incredible explanation striver!!
Hey Striver, thanks for explaining so nicely. I was stuck on the thought that how to move both of them together so that I don't miss any combination.
Wow, I am solving hard questions now. Thank you Striver. "Understood". ♥
Understood sir!!
Your way of explanation is very good and i am easily able to grasp the concepts.
amazing series!
able to solve every question
dayummm the way of explanation like its LC easy....thanks n understood!!!!
Absolute gold, God Bless You Striver!
I got same type of question in my recent flipkart sde internship online round.
Thanks Striver for such quality content
Understood it very clearly. Thank you so much.
understood Sir .From DP Video 1 I was watching video in that mean time
You are just awesome! You inspire me! Thank you!
I don't believe it. Really man, really???
How can you teach so well that the person(Myself) who has been running away from DP like anything was able to do this question on my own? Freaking GOD level you have. Orz
Understood! You are the BEST!! Thank you sooooooo much!!!
The best thing is you teach how to approach the ques which many don't
Is cherry pickup and this question of same concept cause in that you only traverse the matrix by one person only?
Understood In a very good Manner Thanx to you bro!!!
best series so far and i am able to dp problems so fast
Great explanation, thank you.
understood sir!!
i just love you..better than any paid courses
UNDERSTOOD... !
Thanks striver for the video... :)
Guys, your can complete most of the Dp questions in O(1) space complexity, by storing the results in the input matrix itseld, start iterating the 2D matrix from the 2 row, and then keep storing the answers.
thanx bro!!
It isn't preferred if you are doing it for interviews. It's fine for CP. Because interviewers don't like to mutating the given data. consider it as user's data ( you don't want to change it right )
It will be still O(n) tho
The input takes O(n) space, if we use another matrix O(n) - it will be O(2n) which is still O(n)
If we don't use another matrix it will be O(n) (just some constant optimization)
@@ajml_hnter Dude, trust me there is nothing like that. Another thing for about users data, the reality the data structures and algorithms are rarely ever used in real life, once you get a job, you would never see people use DSA in their life.
I hope I answered your question.
Or did you mean something else?
@@maverick5056 yup you are right but since we are giving interviews trying to enter the industry we may have to follow the usual norm atleast for the interviewer's staisfaction
Great explanation as always,
really an interesting question, loved it and "understood" it.
Understood!! Hard Question Made Easy ...Thank you so much Striver Bhaiya...
i m here and i have never been interetsed in dp before
thank u striver
Thank you so much, but I so curios about the 3D matrix look like when you fill them all. If you can make another the video to visualize how it work with 3D matrix like this
Rubix cube with different or same edge sizes
Thankyou so much striver for great solution
scene thanne chetta... ith pwoli aarntto
U are blessing for us who can afford paid course hat's of to you🥰🥰🥰🥰
Understood. Thanks for creating the playlist.
Amazing Lecture
thanks for ur explanation vaiya.i could solve the recursion and memoization technique by myself.as the 3d pattern wasnt known well to me thats why i couldnt solve the tabulation technique.by the way thanks again for ur explanation
Outstanding work, understood well!!
Understood bhaiya ❤
But this question indeed was a tough one but u made it so easy need to watch it again for better understanding ❤❤❤
hey @striver pls take cherry pickup 1 in next video. Its really good example of dp with modifying grid status at each state!!!!!!!!
Striver is doing great work..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
for Striver:
for(in every video) {
respect = Math.pow(respect, respect);
}
Thanks a ton Striver Bhaiya...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
22% done .....Understood... feeling confident
The Best DP ❤❤❤ around the world.
Loving the series
Understood bhaiya
You are a great teacher. Loving the series
Bhaiya aap jab samajhte ho it's very easy to understand any questions thanku so much bhaiya😀
Superb explanation striver
Understood. Thankyou sir