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 :)

[@CostaKazistov]

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

[@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

[@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 😊

[@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!

[@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

[@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 😊

[@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 :)

[@anushreegupta5830]

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

[@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 🤣

[@HimanshuKumar-sl6ud]

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

[@techdose4u]

Sure :)

[@peter-eh2oq]

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

[@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.

[@Dizzydizzydizzy7]

Literally best explaination on youtube

[@programmingstuff5741]

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

[@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 😊

[@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 :)

[@prathamkesarkar]

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

[@wilfredomartel7781]

Great!

[@HariPrasad-ox5ri]

Thank you for the simple and elegant explanation!

[@techdose4u]

Welcome :)

[@utkarsh5165]

Wonderful Explanation BY Tech Dost.. (Dosh)

[@ayoubdkhissi]

this explanation couldn't be better!! thanks

[@techdose4u]

Welcome :)

[@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.

[@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.

[@AltafHussain-on2oe]

I am falling in love with your Explanation 💖

[@techdose4u]

😀

[@PriyanshuKumar-om8np]

The best explanation I have ever seen.

[@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

[@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 😅

[@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.

[@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

[@UJJWALGIRIRA]

bhai op zeher explaination🔥🔥🔥🔥🔥🔥🔥

[@prashantagrawal1140]

Brilliant Explaintion techdose

[@techdose4u]

Thanks

[@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!

[@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]

👍🏼

[@shivanij3725]

nice explanation about dp table.Thanks

[@techdose4u]

Welcome :)

[@kumaraakash25]

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

[@viralmehta2542]

Nice video. Covered various approaches here.

[@techdose4u]

Thanks

[@sarathgovind.k.k7951]

very good explanation

[@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 😅

[@shapedsilver3689]

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

[@techdose4u]

:)

[@OP-yw3ws]

Amazing you solved all my doubts

[@Safar_Ayushi_Ka]

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

[@techdose4u]

Thanks. Yes I will

[@jeromealve6321]

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

[@techdose4u]

:)

[@rahulbhangale4656]

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

[@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.

[@neharikakhera6411]

Thank you so much for great explanation!!

[@techdose4u]

Welcome :)

[@pradeepvdeepu4768]

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

[@techdose4u]

Welcome :)

[@AnshumanSharmadev]

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

[@techdose4u]

Thanks :)

[@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

[@shaileshhegde9205]

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

[@ABHISHEK-fy1in]

Very well explained. 👌

[@nabidhasan9548]

Great explanation brother

[@techdose4u]

Thanks 🙂

[@InsightWeaver]

Amazing video mate! explained thoroughly. Cheers

[@openworld7585]

Thank you for awesome explanations of dp table

[@techdose4u]

Welcome :)

[@miltonrodrigues8417]

Good Explanation!

[@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.

[@shreelakshmi6890]

Great Explanation!

[@lemax2980]

Great sir, as usual😋

[@techdose4u]

Thanks :D

[@Somethingsomethinglol]

Excellent!

[@techdose4u]

Thanks :)

[@chelseaip759]

THE BEST TUTORIAL

[@techdose4u]

Thanks 😊

[@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.

[@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,

[@programmingstuff5741]

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

[@techdose4u]

Already done. Search in videos.

[@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 😂

[@anandakrishnan2685]

Nice explanation, thanks!

[@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

[@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; }

[@lashalezhava2313]

Thanks, you explain very well :)

[@techdose4u]

Welcome :)

[@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.

[@jameskurakula8560]

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

[@veereshr]

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

[@techdose4u]

Yes if the array is mutable

[@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

[@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

[@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?

[@harifrahman8054]

Nice Explanation

[@techdose4u]

Thanks :)

[@rushabhlegion2560]

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

[@vedant9887626061]

What will be the boundary conditions for recursive approach

[@techdose4u]

Out of bounds case.

[@blume0f]

awesome sir

[@techdose4u]

Thanks :)

[@mahipalsingh-yo4jt]

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

[@techdose4u]

Thanks

[@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 :)

[@subratarudra2745]

Nice explanation sir

[@techdose4u]

Thanks :)

[@jeevanr5814]

Dp approach is not working for some testcase can you please check it

[@prathameshmahankal4180]

Could someone please help me understand how the time complexity for the last solution is O(N^2)?

[@praveennandham2933]

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

[@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 } }

[@bigbird0617]

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

[@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).

[@jaredmomanyi8178]

works like magic

[@techdose4u]

Nice :)

[@mohammedsadiq1567]

Awesome bro!!

[@techdose4u]

Thanks :)

[@LovelyMountainGoat-rd7qy]

Thank you😇

[@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?

[@lifestoriesfromearth6271]

which tool are you using for whiteboard

[@vikashverma9]

how to calculate time complexity when we solve by bottom up dp approach.

[@techdose4u]

TIME will be same either you do Top down or Bottom up because you will be doing same number of operations using the same algo and the same logic path. If you are getting confused then just rotate the matrix by 180 degrees them bottom up approach will become top down.

[@vikashverma9]

@@techdose4u Thanks for your quick reply. I am using recursive approach. Please see code. ide.geeksforgeeks.org/BYt1SFzNms

[@alnaifmilon5420]

Thank you

[@techdose4u]

Welcome :)

[@mohitsoni3446]

awesome

[@techdose4u]

Thanks :)