Minimum path sum | Min cost Path | Dynamic programming | Leetcode #64

This video explains a very important programming interview question which is to find minimum cost path or minimum path sum. I have shown backtracking method along with memoization optimization and finally explained the most optimal dynamic programming solution using proper example. Finally, i have explained the DP code and CODE LINK is present below. This is the 64th number question from LEETCODE. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...

[@codestorywithMIK]

Explaining things like "Why won't Greedy work here", then going from "recursive" approach to optimized DP approach. This is how everyone wants to see a problem and this is how everyone should look at a problem. Start from worst and make improvements step by step. This makes your teaching style special. Thanks

[@techdose4u]

Welcome :)

[@junelcjun]

i agree. this is one of the best videos.

[@ismail8973]

That's makes sense

[@debaratighatak2211]

well said! I agree

[@GodOfFaith]

Just in 14 mins

[@ronaldabellano5643]

The best. I like the use of colors that made it easy to follow.

[@techdose4u]

Thanks :)

[@genvalencia1740]

I come here whenever I start to feel anxious about my solution not panning out, and I'm solving in Python. :) Thanks again for these walk-throughs, they really help. =D

[@techdose4u]

Welcome :)

[@alfredomora5555]

I just had an assessment wish I saw this video earlier. The question was very similar. I appreciate your content thank you!

[@techdose4u]

Thanks 😊

[@CostaKazistov]

Clearest explanation of 3 different approaches to solving Minimum Path Sum problem 💯

[@PiyushKumar-ey7qw]

memoization approach did work like a charm, instead of a 2D array, I have used unordered_map where key was a pair of i,j value.
It got accepted.

[@techdose4u]

Share your code bro :)

[@Safar_Ayushi_Ka]

Hey Piyush Share your code

[@divanshuagarwal8236]

Can you please share your code?

[@Amitkumar-nw5mt]

using map insted to 2-d arr wont work

[@sunyulhossen]

@@Amitkumar-nw5mt It will definitely work

[@Noizept]

The best video i found so far to explain this problem.

[@techdose4u]

Thanks bro

[@zelo_s6707]

Thanks for this approach! Using the greedy and recursive approaches helped me understand why one would use the DP method. Nothing else made sense up until now. Keep it up!

[@indsonusharma]

i did by marking technique (iterative) like if you have not encountered then add that state and mark it but if you have encountered that (check by using mark 2d array )state before then take minimum of previous and current state(bit mathematical) that also lead me to AC but thanks for this beautiful approach bro! today the base case could'nt stop us in the first go lol!!

[@techdose4u]

This concept is same as memoization. Today I already wrote the base case 🤣

[@anushreegupta5830]

Hats off to your teaching style! Legit the best explaination.

[@ismail8973]

Explanation for Why greedy algorithm doesn't work was top notch. people usually doesn't try to think or explain in that angle. Thanks

[@dileepkumar-nd1fo]

You are mastered in explaining the things man.
Such a neat explanation with clear voice and the colour combination will make us remember easy.

[@techdose4u]

Great :)

[@techwithlord]

This is a best ever video I have ever seen from this only one video I clearly understand the GREEDY, RECURSION AND BACKTRACKING also hats off dude to your work

[@techdose4u]

Thanks 😊

[@HimanshuKumar-sl6ud]

the way you explain complex things in easy way is awesome. please make more problems solution of leetcode .

[@techdose4u]

Sure :)

[@khan.mansoor]

You explain both problem and solutions very well. Commenting for expressing gratitude as well to offer support. Please keep up the good work.

[@simon7671]

you help me a lot! I am a beginnner and this question is just too hard for me. After watching your video, i am able to finish a similar question by myself!

[@techdose4u]

Great :)

[@debaratighatak2211]

Another amazing explanation, I can't really thank you enough sir! I :) The bright colours in the video really helps a lot too

[@techdose4u]

Thanks 😊

[@HariPrasad-ox5ri]

Thank you for the simple and elegant explanation!

[@techdose4u]

Welcome :)

[@ayoubdkhissi]

this explanation couldn't be better!! thanks

[@techdose4u]

Welcome :)

[@peter-eh2oq]

Thanks! Please keep going!!! Thanks soooooooooo much!!! I saw a lot of vedio about this question, you have the best explination.

[@prathamkesarkar]

As usual sir I was able to solve this within minutes with your explanation.

[@prafulparashar9849]

Great explanation !!
The steps which we followed were the exact steps and approaches which came to my mind while looking at this problem for the very first time.
I was able to go till recursion(backtracking) approach but could not figure out the last one.
Thanks !! This was helpful.

[@AltafHussain-on2oe]

I am falling in love with your Explanation 💖

[@techdose4u]

😀

[@programmingstuff5741]

Can you post the solutions of Google kickstart Round A and Round B
These are the such good problems to practice

[@Dizzydizzydizzy7]

Literally best explaination on youtube

[@utkarsh5165]

Wonderful Explanation BY Tech Dost.. (Dosh)

[@alancabrera7116]

iiuc, the space complexity is O(n). One only needs one vector for the running minimums.

[@techdose4u]

True. 2 maintaining 2 rows is sufficient. This is true for most table type DP programs.

[@Rasheed21]

That's incorrect at 7:18; memoization significantly improves time. For a 15x16 grid I was able to reduce recursive calls from 445,962,869 to 479 where there were 209 cache hits. The time dropped from 1347 ms to 1ms. That's a 1347 times improvement on time and nearly 100,000 times improvement on recursive calls. This was with Java using a 2D array for the cache (i.e. memoization) instead of HashMap. The time spent filling the array with -1's had little impact. Using HashMap also had good time of 7 ms with the same improved numbers for recursive calls and cache hits.

[@fussycat2798]

Nicely explained the concept. Really like it. I was able to solve the similar problems in less time. Thanks a lot for the detailed explanation

[@DrJavyMartinez]

Dude! Your accent is tough, but after watching your video, I feel EXTREMELY comfortable applying minimum and maximum cost sum traversal algorithms through graphs!!

[@techdose4u]

Great :) Sorry for this accent though 😅

[@amansarma417]

i did without the dp vector. Since we could just perform modifications on the same given grid matrix.
Space Complexity O(1) :) . I submitted that way

[@techdose4u]

Pleas share your code.

[@paragroy5359]

Nice explanation sir....but instead of taking an additional dp vector if we do changes in the given grid vector only then it will be o(1) space solution

[@techdose4u]

👍🏼

[@rishabhgoyal8110]

I hope this channel reaches 1m soon!

[@techdose4u]

Thanks for your support 😀

[@Daniel_WR_Hart]

LeetCode only has a bit over 200K users with a contest ranking, so that might take a while

[@PriyanshuKumar-om8np]

The best explanation I have ever seen.

[@kercat89]

It's so easy to understand and I loved the break down from the simple to sophisticated approach!
I have a question re the recursive solution - why is the complexity O(2^n) and not O(2^(m*n))? if it means that there's 2 options to about each cell..? Thank you

[@techdose4u]

Thanks. Actually our number of steps will always be (m+n) from top left to bottom right. So, you can say time will be 2^(m+n).

[@kercat89]

@@techdose4u That makes sense. Thank you!

[@prashantagrawal1140]

Brilliant Explaintion techdose

[@techdose4u]

Thanks

[@ambujverma9287]

the way you explain things is phenomenal...
thanks a lot

[@techdose4u]

Welcome :)

[@ambujverma9287]

@@techdose4u bhai you work in any MNC or u study in college(iit?)

[@techdose4u]

MNC....

[@ambujverma9287]

@@techdose4u which one.. if you don't mind brother 😅

[@Safar_Ayushi_Ka]

Your videos are amazing plz do make more videos on DP ,it would be grateful Thanks

[@techdose4u]

Thanks. Yes I will

[@UJJWALGIRIRA]

bhai op zeher explaination🔥🔥🔥🔥🔥🔥🔥

[@neharikakhera6411]

Thank you so much for great explanation!!

[@techdose4u]

Welcome :)

[@viralmehta2542]

Nice video. Covered various approaches here.

[@techdose4u]

Thanks

[@shivanij3725]

nice explanation about dp table.Thanks

[@techdose4u]

Welcome :)

[@shapedsilver3689]

When he started getting into why greedy algorithms won't work I knew this was legit

[@techdose4u]

:)

[@AnshumanSharmadev]

Amazing!! You made it look so simple! Liked and Subscribed!

[@techdose4u]

Thanks :)

[@InsightWeaver]

Amazing video mate! explained thoroughly. Cheers

[@kumaraakash25]

Amazing explanation but why would anyone go with the DP approach if complexity is the same in both recursion and DP both

[@pradeepvdeepu4768]

awesome explanation and smooth ..... ! thanks a lot

[@techdose4u]

Welcome :)

[@sarathgovind.k.k7951]

very good explanation

[@techdose4u]

Thanks :)

[@rahulbhangale4656]

greedy works if you properly define dp table. dp[i][j] denotes minimum path sum from (1,1) to (i,j)

[@OP-yw3ws]

Amazing you solved all my doubts

[@jeromealve6321]

I wish this video came out 3 years ago when I took my algorithms class lol

[@techdose4u]

:)

[@wilfredomartel7781]

Great!

[@sarvagyaiitmadras8727]

if all 4 direction mvement would be allowed then what would be changes, will changes work in it, or completenew approach would be needed ???

[@techdose4u]

Apply Dijkstra.

[@openworld7585]

Thank you for awesome explanations of dp table

[@techdose4u]

Welcome :)

[@shivanggupta5421]

def findPath(x:int,y:int):
if(x= len(grid) or y=len(grid[0])):
return
right = findPath(x,y+1)
down = findPath(x+1,y)
return min(right,down)+grid[x][y]
I used this method. I know you said recursive method won't work but I tried for my satisfaction. But when compiling it gives error because it isn't able to compare right and left when the boundary check returns null. Can you tell me where am I wrong

[@ABHISHEK-fy1in]

Very well explained. 👌

[@nabidhasan9548]

Great explanation brother

[@techdose4u]

Thanks 🙂

[@programmingstuff5741]

Can you post videos on segment tree??
Which is very useful for the purpose of comptetive programming

[@techdose4u]

Already done. Search in videos.

[@amitavamozumder73]

we can also do dijksta here right? the value in each cell can be the edge weight, which is pretty close to the dp solution.

[@techdose4u]

You can

[@amitavamozumder73]

@@techdose4u can you please make a video on myers diff algorithm, (the one used in github file diff), it's not anywhere in youtube,

[@shaileshhegde9205]

The recursive way is DFS right with directions of right and below

[@lemax2980]

Great sir, as usual😋

[@techdose4u]

Thanks :D

[@tekbssync5727]

What a color combination and style of *Leet code* in the thumbnail ? !!!! 😂

[@techdose4u]

😅

[@marvellouschandan]

It was a clickbait actually :D

[@techdose4u]

@@marvellouschandan it wasn't 😂

[@lashalezhava2313]

Thanks, you explain very well :)

[@techdose4u]

Welcome :)

[@shreelakshmi6890]

Great Explanation!

[@miltonrodrigues8417]

Good Explanation!

[@techdose4u]

Thanks

[@anandakrishnan2685]

Nice explanation, thanks!

[@chetanpatteparapu7600]

Top Down approach using backtracking and memoization:
private int[][] memo;
public int minPathSum(int[][] grid) {
if (grid.length < 1)
return 0;
this.memo = new int[grid.length][grid[0].length];
for (int[] row : memo)
Arrays.fill(row, Integer.MAX_VALUE);
return getMinPathSum(grid, 0, 0);
}
private int getMinPathSum(int[][] grid, int row, int column) {
int currentValue = grid[row][column];
if (memo[row][column] != Integer.MAX_VALUE)
return memo[row][column];
else if (row == grid.length - 1 && column == grid[row].length -1)
return currentValue;
else if (row == grid.length - 1)
currentValue += getMinPathSum(grid, row, column + 1);
else if (column == grid[row].length - 1)
currentValue += getMinPathSum(grid, row + 1, column);
else
currentValue += Math.min(getMinPathSum(grid, row, column + 1), getMinPathSum(grid, row + 1, column));
memo[row][column] = currentValue;
return currentValue;
}

[@chelseaip759]

THE BEST TUTORIAL

[@techdose4u]

Thanks 😊

[@jameskurakula8560]

@7:38
grid[I][j]+ min( dp[ i-1][j], dp[I][j-1]) , there it was j-2.

[@ritikgandhi3605]

In line 11 of the code ,why did we initialize cols as
int cols=grid[0].size() and not just as grid.size()?

[@techdose4u]

Because the number of cols are same in each row and grid[O] means no of cols. Grid.size means no of rows because it is a 2D matrix.

[@Somethingsomethinglol]

Excellent!

[@techdose4u]

Thanks :)

[@veereshr]

if we can change the input matrix, we can use the same right? memory optimisation?

[@techdose4u]

Yes if the array is mutable

[@blume0f]

awesome sir

[@techdose4u]

Thanks :)

[@akanshagautam9815]

If we can move up, down, left, and right then what changes do we have to make in the code?

[@techdose4u]

Maybe try with Dijkstra graph algorithm.

[@harshitchoukse2602]

Then you need track the path with visited array in order to bypass the cycle.

[@mahipalsingh-yo4jt]

great video sir...........:)

[@techdose4u]

Thanks

[@moonbrush5]

I am stuck with a similar problem which is finding shortest path in 2D matrix from source to target which given in the problem and I have to return all i,j coordinates of the shortest path only. Please help.

[@shyamprakashm6325]

How do we print the minimum path index in the given input matrix?
Ex:(0,0)--->(0,1)--->. Some what like this...
The same problem I have been facing when ever I use the dp concept example print the subset which has the sum=k here I could find the sum but I don't know how to find the subset...
Please help sir

[@aneeshmv8201]

Memoization of recursive code to remove overlapping sub problem calls, will give O(N*N ) right?

[@techdose4u]

It will depend on no of repeating subproblems. Actually 2^N is a much larger upper bound due to the constraint in movement. But yes, memoization should give approx N^2. But since we are still doing recursion, actual runtime can go much higher than table method if you get large matrix. So, table method is best for larger cases. I hope you got it :)

[@harifrahman8054]

Nice Explanation

[@techdose4u]

Thanks :)

[@pallabghosh3840]

can i say the time will be in recursive approach 2^(m*n) in worst case? so we use dp for n^2 time

[@vedant9887626061]

What will be the boundary conditions for recursive approach

[@techdose4u]

Out of bounds case.

[@subratarudra2745]

Nice explanation sir

[@techdose4u]

Thanks :)

[@jaredmomanyi8178]

works like magic

[@techdose4u]

Nice :)

[@LovelyMountainGoat-rd7qy]

Thank you😇

[@dhruvgoel25]

Can you please explain me why we initialize dp like dis
dp(row, vector(cols,0))
The first parameter is clear bt second I couldn't get

[@jigarmav335]

dp(row , vector(cols,0)) .Here 1st parameter indicates that we want a vector of size row. Second parameter indicates that each element in our vector is a vector of size cols and is initialized to zero.
for dp(2,vector(2,0)) it would look like this.
{
{ 0, 0 },
{ 0 , 0 }
}

[@mohammedsadiq1567]

Awesome bro!!

[@techdose4u]

Thanks :)

[@jatinshrivastava4231]

What should I do if i also have to count the number of paths through which We can reach the minimum cost as there can be more than one such paths?

[@raj.saurabhh]

Can we not use the extra space and use the given table for dp? I mean my testcase is ok but when i submit one solution is wrong

[@rushabhlegion2560]

What is that Fast I/O in C++ line at the top? Is it necessary?

[@praveennandham2933]

can we change the same logic ass required
when soure and destination or given??

[@lifestoriesfromearth6271]

which tool are you using for whiteboard

[@alnaifmilon5420]

Thank you

[@techdose4u]

Welcome :)

[@bigbird0617]

the time complexity should be O(n*m) not O(n2) ?

[@kbhargavi4400]

TQ bro!😃

[@techdose4u]

Welcome :)

[@alexsparrow8614]

can you tell boundary check condition in recursive Method.....

[@techdose4u]

Out of bounds. Reaching the desired cell. Reject higher cost path (if using memoization).

[@RahulKumar-qu1if]

Thank you!🔥

[@techdose4u]

Welcome :)

[@mohitsoni3446]

awesome

[@techdose4u]

Thanks :)

[@abdelrhmansayed340]

thanks

[@techdose4u]

Welcome :)

[@InsightWeaver]

@tech dose what if add diagonal movement to it? how would we solve it then?

[@InsightWeaver]

also in python 3 verson please

[@yashgoswami5374]

What will be the solution if we allow to move in all 4 directions?