Cherry Pickup II | 3 Approaches | Super Detailed | Leetcode 1463
236Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 88th Video of our Playlist "Dynamic Programming : Popular Interview Problems".
In this video we will try to solve a very good 2D-DP problem - Cherry Pickup II | Leetcode 1463
Minimum Falling Path Sum - https://youtu.be/EQC0ckOyEGs?si=nDByrC8WMn-qns2C
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Cherry Pickup II | Leetcode 1463
Company Tags : Microsoft, Amazon, Google
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/Cherry%20Pickup%20II.cpp
Leetcode Link : https://leetcode.com/problems/cherry-pickup-ii/description/
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Approaches Summary :
Approach-1 (Using Recursion + Memoization):
Time Complexity: O(rowcolcol * 9), where 9 is from the double for loop for colDir.
Space Complexity: O(row * col * col).
Description: This approach utilizes recursion with memoization. It recursively explores all possible paths for both robots while picking cherries, memoizing the maximum cherries picked at each position. It returns the maximum cherries picked starting from the top row.
Approach-2 (Bottom Up - 3D Array):
Time Complexity: O(rowcolcol * 9).
Space Complexity: O(row * col * col).
Description: This approach uses dynamic programming with a 3D array to store the maximum cherries picked at each position for both robots. It iterates through each row and computes the maximum cherries that can be picked for each pair of positions for the two robots. It returns the maximum cherries picked from the last row.
Approach-3 (Bottom Up - 2D Array):
Time Complexity: O(rowcolcol * 9).
Space Complexity: O(col * col).
Description: Similar to Approach-2, this approach also uses dynamic programming, but it optimizes space usage by only storing the previous row's values. It iterates through each row, updating the maximum cherries picked for each pair of positions for the two robots. It returns the maximum cherries picked from the last row.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear