Minimum Path Sum - Dynamic Programming - Leetcode 64 - Python
Vložit
- čas přidán 28. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: leetcode.com/problems/minimum...
0:00 - Read the problem
1:40 - Drawing Explanation
6:46 - Coding Explanation
leetcode 64
This question was identified as a google interview question from here: github.com/xizhengszhang/Leet...
#dynamic #programming #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Great explanation! It's pretty similar to the unique paths leetcode problem
I was using a bigger formula, but thanks for this small one, it is easy to implement
i dont know why i feel more comfortable doing from top left downwards and it is accpeted with O(n) space and constant time as we use same array with edge case handling:
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
for row in range(len(grid)):
for col in range(len(grid[0])):
if row == 0 and col == 0:
continue
if row == 0 or col == 0:
if row == 0:
grid[row][col] +=grid[row][col-1]
if col == 0:
grid[row][col] +=grid[row-1][col]
else:
grid[row][col] += min(grid[row][col-1],grid[row-1][col])
return grid[-1][-1]
Honestly, this one was simpler and easy to understand, Thanks.
I love how you say "Let's write some neetcode today !"
Thanks. I was looking for it.
Great logic!! great explanation!! Well done bro!!
is it okay to solve this as a graph problem? I initially did it with the dijkstra's/min heap approach
grt video , i noticed you always start from reverse direction means last index instead of first
which path needs to be chosen in case both the numbers are equal as we are comparing min of (up and left element) ?
It took me a while to figure out that "how many subproblems do we have" - is really MxN and "how many paths are from top-left to bottom-right" is a different thing :D
I think in the video you make the [-1,-2] point to be 0, but in the code you make the [-2,-1] point to be 0. However, both are ok :)
Hey NeetCode, with your drawing, I think the third line should be res[rows][cols -1] = 0, right?
it doesnt make a difference
thank you so much!
Great Explanation , but there is one bug in the code if you are specifically referring to the diagram you drawn while explaining the code. 0 position you mentioned in the code does not match the code you have written. Though it work out.
Do you think it would be ok if in a machine learning engineer interview I insisted on solving this using numpy arrays? It makes shaping the grid much cleaner.
really nice!!
Instead using memory modifying the same array
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
for row in range(m-1, -1, -1):
for col in range(n-1, -1, -1):
if row == m-1 and col == n-1:
continue
right = inf if col+1 == n else grid[row][col+1]
bottom = inf if row+1 == m else grid[row+1][col]
grid[row][col] = grid[row][col] + min(right, bottom)
return grid[0][0]
but bro the arguments in the min() is wrong right? it should be below and right of the element.
see 8:43
it has been fixed
it's also possible to do it in place
why can't we solve this problem with negative numbers?
Hey Neet. It's tagged as an Amazon question in the github link, just wonder where do you get the info that it's also a Google question?
I think In for loop 4rth argument for range in unnecessary.
I’ve thought this was a graph problem 😢😢
I did a solution but suppose the walk can be FOUR-directional
class Solution:
def minPathSum(self, grid) -> int:
R,C = len(grid), len(grid[0])
queue = []
queue.append((R-1,C-1, grid[R-1][C-1]))
cache = [[float('inf')] * C for _ in range(R)]
cache[R-1][C-1] = grid[R-1][C-1]
while queue:
for _ in range(len(queue)):
i,j,cost = queue.pop(0)
if i-1 >= 0 and cost + grid[i-1][j] < cache[i-1][j]:
cache[i-1][j] = cost + grid[i-1][j]
queue.append((i-1,j,cost + grid[i-1][j]))
if i+1 < R and cost + grid[i+1][j] < cache[i+1][j]:
cache[i+1][j] = cost + grid[i+1][j]
queue.append((i+1,j,cost + grid[i+1][j]))
if j-1 >= 0 and cost + grid[i][j-1] < cache[i][j-1]:
cache[i][j-1] = cost + grid[i][j-1]
queue.append((i,j-1,cost + grid[i][j-1]))
if j+1 < C and cost + grid[i][j+1] < cache[i][j+1]:
cache[i][j+1] = cost + grid[i][j+1]
queue.append((i,j+1,cost + grid[i][j+1]))
return cache[0][0]
tested on [[1,1000,1,1,1],[10,10,2,1000,1],[1,1,1000,2,1],[1000,1,1,1000,1]] DP gives 1007 while BFS above gives 29
🔥🔥
While I totally appreciate this video, but the problem must be approached first with the recursion and then the problem must be further optimized with the use of this matrix table approach. This would have helped us to clearly understand the problem
I don't think your code will work out for this input [ [ 1, 1, 1 ] , [ 10, 10, 2 ] , [ 10, 1, 1 ] ]. As choosing the minimum paths here can not work out well. One would have to calculate all the possible values for this case to be true.
I think it works, the answer should be 6, right?
it works, 6 is answer.
“We don’t even have to do that brute force recursive way…” What brute force recursive way? You didn’t show anything!