Minimum Path Sum - Dynamic Programming - Leetcode 64 - Python

[@abhisheksunkale6672]

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]

[@parvashah7887]

Honestly, this one was simpler and easy to understand, Thanks.

[@untrall6667]

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

[@MrACrazyHobo]

Great explanation! It's pretty similar to the unique paths leetcode problem

[@curesnow6493]

I’ve thought this was a graph problem 😢😢

[@supremoluminary]

“We don’t even have to do that brute force recursive way…” What brute force recursive way? You didn’t show anything!

[@milktea2755]

is it okay to solve this as a graph problem? I initially did it with the dijkstra's/min heap approach

[@tedtalks2144]

but bro the arguments in the min() is wrong right? it should be below and right of the element.

[@EddieCheng174]

see 8:43 it has been fixed

[@harshvardhanranvirsingh9473]

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

[@balachandar6206]

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]

[@chineshdoshi9272]

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.

[@mrditkovich2339]

I love how you say "Let's write some neetcode today !"

[@TheElementFive]

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.

[@NickDev-pd1fz]

which path needs to be chosen in case both the numbers are equal as we are comparing min of (up and left element) ?

[@raylin2527]

really nice!!

[@JohnIdlewood]

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

[@shivaprasad8919]

I think In for loop 4rth argument for range in unnecessary.

[@BullishBuddy]

why can't we solve this problem with negative numbers?

[@kuldeepchouhan8467]

Great logic!! great explanation!! Well done bro!!

[@kxf8608]

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]

[@kxf8608]

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

[@hailei]

Hey NeetCode, with your drawing, I think the third line should be res[rows][cols -1] = 0, right?

[@sagarpotnis1215]

it doesnt make a difference

[@suchitkumar2099]

grt video , i noticed you always start from reverse direction means last index instead of first

[@aayushgupta6914]

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.

[@untrall6667]

I think it works, the answer should be 6, right?

[@joydeeprony89]

it works, 6 is answer.

[@amitupadhyay6511]

I was using a bigger formula, but thanks for this small one, it is easy to implement

[@vaibhavdesai16]

Thanks. I was looking for it.

[@skalra8]

thank you so much!

[@nemesis_rc]

🔥🔥

[@kanyestan]

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?

[@dawidprokopek7651]

it's also possible to do it in place