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.

[@MrACrazyHobo]

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

[@mrditkovich2339]

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

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

[@techandmore12]

Alternatively in for loop: if c + 1 < COLS and r + 1 < ROWS: grid[r][c] += min(grid[r][c + 1], grid[r + 1][c]) elif c + 1 < COLS: grid[r][c] += grid[r][c + 1] elif r + 1 < ROWS: grid[r][c] += grid[r + 1][c]

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

[@milktea2755]

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

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

[@seenumadhavan4451]

class Solution: def minPathSum(self, grid): lrow, lcol = len(grid), len(grid[0]) for i in range(lrow - 1, -1, -1): for j in range(lcol - 1, -1, -1): if i == lrow - 1 and j == lcol - 1: continue a, b = float("inf"), float("inf") if 0

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

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

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

[@kuldeepchouhan8467]

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

[@amitupadhyay6511]

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

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

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

[@vaibhavdesai16]

Thanks. I was looking for it.

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

[@curesnow6493]

I’ve thought this was a graph problem 😢😢

[@BullishBuddy]

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

[@shivaprasad8919]

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

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

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

[@supremoluminary]

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

[@raylin2527]

really nice!!

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

[@dawidprokopek7651]

it's also possible to do it in place

[@nemesis_rc]

🔥🔥