Minimum Cost Path Dynamic Programming Explained with Code | Leetcode #64
Vložit
- čas přidán 30. 07. 2020
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the solution for the Minimum Cost Path problem where we are required to reach the bottom right corner from the top left corner with minimum cost. For a better understanding of the problem, click here: • Minimum Cost Path - Qu... . In this problem,
1. You are given a number n, representing the number of rows.
2. You are given a number m, representing the number of columns.
3. You are given n*m numbers, representing elements of 2d array a, which represents a maze.
4. You are standing in top-left cell and are required to move to bottom-right cell.
5. You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion.
6. Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom-right cell).
7. You are required to traverse through the matrix and print the cost of path which is least costly.
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
#dp #dynamicprogramming #mincostpath
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
![LeetCode 64. Minimum Path Sum [Algorithm + Code Explained ]](/img/n.gif)
Sir trying to learn dp from a long time , but not able to do it, but looks like this time I will be able to do it .. as your teaching skills were god level .Thank you so much for posting these resources :-)
We can think of the storage and meaning in a different way too . Like we can think for any (i,j) cell where 0
Most underrated channel of india
Beta, hamre desh ki janta ko dikhave vali cheeze zda aachi lgti h aur real content boring but with the love and support from you people Pepcoding will soon shine really bright.
Till then, keep learning and keep loving Pepcoding.
@@Pepcoding sahi baat hai sir ji wo how to earn in first year,falana thikana wale shortcuts wale videos hi log dekhte hai aur reality me jo dsa padhni hai wo nahi.
@@AbhishekJha-wm5oq sahi baat! I agree with you bro!! BTW from which college u r?
@@Pepcoding can you also upload top down solution. It is really important because it tell us how to optimize recursive solution.
Best Explanation so far , Thanks Sir
Sumeet sir, you are doing a thing of God for many students.
There ar people who can't join coaching due to fees. But they want to learn. This will surely help them get amazing jobs. Indeed you are god sir. Kitni acchi hoti duniya agar aaj jaise aur log hote. My idol after ms Dhoni.
sir the way u just start explaining the question with the intro of the channel is just incredible
amazing sir first year m hu phir bhi dp smooth lag rhi h aap ki vajah se.Thanks sir
Amazing Explanation sir!!!
Ye badhiya tha..... Maja aa gaya!!
Thanks sir ! 💯👏🏻👏🏻👏🏻
Thank you sir, I was having a hard time understanding this problem and do, u made it possible, thank you a looooott!!!
Glad it helped!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com
Thanks a lot for the brilliant explanation sir. u r amazing
You are most welcome
thanks for these videos
Ohhhh Man !! You made it such a smooth ride. Wonderful sir 🤠
Thanks ✌️ and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Memoized and tabulated (opposite direction) solution:
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] arr = new int[m][n];
for(int i=0; i= arr[0].length || arr[sr][sc] < 0){
return Integer.MAX_VALUE;
}
if(sr == arr.length - 1 && sc == arr[0].length - 1) return arr[sr][sc];
if(dp[sr][sc] != 0) return dp[sr][sc];
int val = arr[sr][sc];
arr[sr][sc] = -1;
int left = minCostMem(arr, sr + 1, sc, dp);
int right = minCostMem(arr, sr, sc + 1, dp);
arr[sr][sc] = val;
return dp[sr][sc] = val + Math.min(left, right);
}
private static int minCostTab(int[][] arr, int m, int n){
int[][] dp = new int[m][n];
for(int i=0; i
in the memorizing technique , maybe there is no need to mark a trace i.e arr[i][j] = -1 and remove after the call .? isn't
How to decide whether to fill dp matrix column wise or row wise and update it? Or will it not make any difference in result?
Sir, u did one mistake at 13:51 the value will be 18 instead of 16 in DP array (last column and third last row). Please tell me, if i am wrong :). You are a star sir, videos are awesome.
should be 18
God level explaination sir!!!
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
Hope every student find sumeet sir. U r the best sir . Ajkl tw sapno me bhi aap aake pda jaate ho....u r awesome sir. Huge respect for you. By making your course public u have earned a lot of respect from the community
I request you to checkout nados.pepcoding.com and the content section there, it also has doubt support and career opportunities available free of charge.
Best Explanation on internet.
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Awesome!!
Thank you! Cheers!
can we define the storage like,
dp[ i ][ j ] : minimum cost to reach arr[ i ][ j ] from arr[0][0] , sot he answer will be at dp[ n ][ m ]
Great explanation
Thankyou beta!
I am glad you liked it. If you like our efforts, will you like to review us here - g.page/Pepcoding/review?rc
Sir is meaning assign anywhere in array??
agr top se fill krein har cell ko as a target manke toh ?
Can we solve it using djikstra?
sir, this code is not working for some test cases
Great explanation ....
Glad you liked it!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
This is bottom Up approach right?
sir level 1 aur level 2 ko use kaise krna hai ,uska ek separate video bn skta hai kya?
Thnaks for the video at 8:36 value should be 18 (11+7) instead of 16
sir i started learning data structures which playlist to follow first
beta ye wali
czcams.com/video/F8xQ5joLlD0/video.html
Balki website se karo
www.pepcoding.com/resources/online-java-foundation
Please sir,if you could explain in English it would also be helpful for South Indians who are not well versed with Hindi.
You are one of the best teacher I have seen till now!!
We have english channel also watch these videos there
Tq,
Target is to watch 8 videos per day🔥
Good keep learning and keep loving Pepcoding😊
sir, can you please provide a recursive solution using the same approach (bottom-up )
import java.io.*;
import java.util.*;
public class Main {
static int[][] dp = new int[101][101];
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] arr = new int[n][m];
for(int i=0; i
Sir nice explanation of this question solution but in geeks for geeks this solution is not working for all the test cases it pass only 10test cases out of 90
sir, yahan pr n+1 and m+1 size ku ni liya?
Why are we going to left side from bottom right. Why not top?
Sir ye dp k ques memoization se kyu ni krre h ?
11+7 is 18 sir. U wrote it as 16 at 5th row last column
13:48 It's an error but still the algorithm is helpful 👍
Sir If we allow to move in 4 direction(up,down,left,right) then how we can solve this problem.
and why in this case DP is not applicable ??.
It is applicable it would take 4D array
sir isme agar greedy approach bhi lagate to ho jata na ? like every time we have choice of moving to horizontal or vertical so at every step starting from [0].. moves += min(hor,vert) krte jaate...2 + 6+0+4+3+4+0+4+1+2+0+8+2 = 36. In thatt case addtional storage n bnani pdti?Is this approach correct.
No, the greedy approach won't work here because, let us suppose that an immediate horizontal cell has a cost of 3 whereas the immediate vertical cell has 7, we select the horizontal cell by using the greedy approach, but what if the immediate next of horizontal's are 100 and 95 whereas vertical one has 95 and 3. In that case, the greedy approach fails. (I am also a beginner but I think this justification would do, tell me if I am the wrong one bro 😅😅.)
@@AshutoshKumar-oo3hc Yes, your explanation is correct
what if we could go in direction right left up and down ??
For better experience and curated content sign up on nados.io and post your queries on community tab of NADOS.
Sir, wecan start to fill matrix from first row and first col.?
Yes you can
Goldman sachs me mere se ye question and stringify wala another question puchha gaya tha.
stringify wala question kya hai ?
Sir, seems like in this video solution, you have taken the values in 'arr' array as cost of exiting that cell but on the website the question says "Each cell has a value that will have to be paid to enter that cell", which was confusing. please let me know if I am missing anything.
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
It's fine sir, I just wanted you to update the website to make things consistent.
Sir agar do paths ke values dp wali array Mai same hai toh kaise karenge??... Ham uss time kaise choose Krenge kaunsa path le??
Humei to sirf value deni hai, kisi bhi cell se uttha lo
Sir, I tried to solve it using memoization... And i used this condition for it:-
if(memoize[i][j] != null && sum > memoize[i][j]) return Integer.MAX_VALUE;
But it is telling TLE at last Test Case...
Question:- Which can be the better condition using the memoization technique?
did u solved it using memoization ??
dude, this ques must be solved using tabulation on online judge. memoisation logic gives TLE everywhere
I tried this and it worked for all on the platform -
int getLeastCostPath(vector maze, int row, int col, vector &dp1){
if (row == maze.size()-1 && col == maze[0].size()-1)
return dp1[row][col] = maze[row][col];
if (row >= maze.size() || col >= maze[0].size())
return INT_MAX;
if (dp1[row][col] != INT_MAX)
return dp1[row][col];
int hpathCost = getLeastCostPath(maze, row, col+1, dp1);
int vpathCost = getLeastCostPath(maze, row+1, col, dp1);
int res = maze[row][col] + min(hpathCost, vpathCost);
return dp1[row][col] = res;
}
is this top down approach? Since we are filling our table from bottom
beta i am not sure
@Ayush Girish Agrawal thanks.
sir please aapki site me doosre editor se submit karne ka option lagado.
How to solve this problem if we have to print the path as well.
Visit- nados.pepcoding.com
You can post your query on community tab.
Don't forget to follow us on Instagram
instagram.com/pepcoding/
sir please make videos on binary search when u will get time
it's there in the array section
Sir you could've simply started this solution with bottom up, from [0][0], woh mujhe intuitive laga, kyuki maine socha I do not know ki [n][m] ki cost kya hai. so shuru se start karo. Toh ye approach theek hai ya apke method ki habit dalun?
beta dono mei koi farak nahi hota. pehle cell ko meaning assign karo. firr choti problem dhundho kis taraf hai aur badi problem kis taraf. choti se badi problem ki taraf travel karo aur solve karo.
jaise agar cell ka meaning hota ki current cell se bottom-right tak ka best cost yahan stored hai to chotti problem bottom-right mei hogi aur upar ki taraf travel karke solve hoga.
agar cell ka meaning hota ki top-left se current cell tak ka best cost yahan stored hai to chotti problem top-left pe hoti aur upar se neeche ki taraf travel karke solva hota.
3 steps -> give meaning to cell, identify smaller problem and larger problem (you will get the direction), travel in the direction and solve.
@@Pepcoding Thank you Sumit sir ab ekdum badhiya se clear ho gaya hai, apki vidoes se mera DP ka dar dur ho raha hai, baaki sab tutorial ratte lagwa dete hai par aap ache time leke bata rahe ho ki humne jo step liya hai kyu liya hai, I hope me saari dekh kar confident ho jaaun par dp bahot bada topic lagta hai. Sir kuch dino me ek baar live aao na aise he random baate karne ke liye😀😅? waise sir aapke jaisa great teacher koi nahi dekha ab tak, aap har taraf se great ho ❤️❤️❤️
agar down and right ki jaga all 4 direction move kare to ?
if you will move all the four sides it means you are getting back to the point from where you come
Till here all going good with DP, hope this time my DP fear will go away...
thanks for putting so much effort to explain in so much detail
Your content is really 24 carat gold :)
I am making sure I like each video to do my bit at least.
Thanks
Glad it was helpful!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
can anyone tell me,can we solve this problem using recursion???
For better experience and well-organised content visit on nados.pepcoding.com. Also you can post your query on Community tab.
Don't forget to follow us on Instagram instagram.com/pepcoding/
sir best explanation sara samaj aagya
2 doubts hai bs...
1st is iss ques ko first time dekha hota to dp lagane ka kaise mind me aata ,, bcz jaise fib5 ko fib 4 , fib 3 ki jarurat padte hai and fib 4 ko 3 ki ..to vha to easily pta chlgya ...lekinn iss ques me repetetion nhi milpara ..
2nd is memoizaton se agar krne chahe to iska solution milsakta hai?
@pepcoding
when we are provide to choose any one out of all(in our case we have the choice to go either right or down ) use recurssion and when we have to find the optimal (i.e min ,max, largest,samaller etc) we use dp. and for every recursion problme with choice and to find the optial we use the dp
Sir, how to know that the question will be solved with dp.
Beta repeat question agar baar baar poocha jae to dp lagegi. Jaisa Fibonacci 5 ko fib4 air fib3 chaie. Aur fib4 ko fib3 aur fib2 chaie. Fib5 aur fib4 ko requirements mei fib3 common hai
The only teacher i love is sumeet sir.
Thank you.
For better experience and well-organised content visit nados.pepcoding.com
DSA 450 QUESTIONS BY LOVE BABBAR solve kradoo sir youtube pr miljayegaa aapko please
Sir Is que ko recursion sa kr skta hai.??
Hanji
Sir question to 50 percent khud se kiya but Time complexity kya hogi sir eska thoda sa roughly explain ker do yhi pe samjh lenge
N raise to power 2
free m jo apne seva ki hai, main ek din company m jane k bad apki seva karna chahta hu sir.
For the array {{1,1,20,10},{20,1,1,1},{1,1,20,20},{1,20,20,20},{1,20,20,20},{1,1,20,1}} The answer should be 30, but the output is different
47 nhi hona chahiye?
Sir memoization wala btaye please
beta sare questions ko memoization se redo karenge.
@@Pepcoding
Sir aapne to graph suru kr diya h
Memoization wala sir easy hota h recursion lgao aur array ya matrix me store kr do
You can do yourself you did recursion well
Why always start from tabulation 😭😭😭
Iss program ka sirf thoda sa hint liya, till timestamp 7:24, fir khud se kar liya :D
Bohot ache beta
Same bro but video met dekho codes dekha kero usme thoda sa code dekho uske bad age ka soho ager nhi ata to video solution dekho
11+7 = 16 Kaise hoga Sir 08:34 ??
Calculation mistake hai .
36 36 30 26 26 35 31
34 28 33 25 20 32 29
29 28 24 21 17 24 24
28 25 26 19 17 18 19
22 21 21 20 13 12 18
24 23 18 15 13 10 11
29 27 25 20 19 10 2
sir 11+7!=16
kis minute pe galti hui?
@@Pepcoding Sir, at this time 8:31
Python code for above problem
def minPathSum(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
dp = [[0] * m for i in range(n)]
for i in range(n-1, -1, -1):
for j in range(m-1, -1, -1):
if i == n - 1 and j == m - 1:
dp[i][j] = grid[i][j]
elif i == n - 1:
dp[i][j] = dp[i][j + 1] + grid[i][j]
elif j == m - 1:
dp[i][j] = dp[i + 1][j] + grid[i][j]
else:
dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) + grid[i][j]
return dp[0][0]
Note - Please see that extra space can be avoided and grid can also be modified to save space
Hope you could use english
English content is available on nados.io
Don't forget to follow us on Instagram instagram.com/pepcoding/
SUGGESTION: I think it will be much more convenient to solve this particular problem using recursion as it is not required to manually consider all the different cases for array traversal. Moreover, I felt that recursion is a bit more intuitive than tabulation for this particular problem.
bro pls give the soln of this ques by recursion
please describe in english
Refer to nados.pepcoding.com for english and better experience.
Pepcoding giving away such premium content for free but who cares. People would watch love babbar(so called software engineer at amazon who can never teach you programming) giving shitty advices but won't try to learn free of cost at pepcoding.