[LeetCode][python3]Day18. Minimum Path Sum (30-Day LeetCoding Challenge)

  1. My Solution
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
maxrow=len(grid)
maxcol=len(grid[-1])
check={(0,0)}
pathsum=[[0]*maxcol for i in range(maxrow)]
pathsum[0][0]=grid[0][0]
while check:
row,col=check.pop()
cursum=pathsum[row][col]
if maxrow>row+1>=0:
if pathsum[row+1][col]==0 or pathsum[row+1][col]>cursum+grid[row+1][col]:
pathsum[row+1][col]=cursum+grid[row+1][col]
check.add((row+1,col))
if maxcol>col+1>=0:
if pathsum[row][col+1]==0 or pathsum[row][col+1]>cursum+grid[row][col+1]:
pathsum[row][col+1]=cursum+grid[row][col+1]
check.add((row,col+1))
return pathsum[-1][-1]
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
for i in range(1, len(grid[0])):
grid[0][i] += grid[0][i-1]
for i in range(1, len(grid)):
grid[i][0] += grid[i-1][0]
for i in range(1, len(grid)):
for j in range(1, len(grid[0])):
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[-1][-1]

--

--

--

HI I’m N2I. Now a SWE in Taiwan. Check out more about me in https://nzi2020.blogspot.com/ or contact via email: nayzi9999@gmail.com

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

The Lean and #NoEstimates Experience

5 simple steps for code refactoring

Consumer Project with RabbitMQ

3XPL017/Reversing-Challenges/level01

Getting started with Azure DevOps — CI/CD Pipelines

Efficient parallel data processing from Cloud Datastore on Google App Engine

Horizontal Stack 2: Peppermills

Samana Smart city Advance details

samana smart city developments

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
N2I

N2I

HI I’m N2I. Now a SWE in Taiwan. Check out more about me in https://nzi2020.blogspot.com/ or contact via email: nayzi9999@gmail.com

More from Medium

LeetCode Patterns Adventure 26 — Merge Two Binary Trees

[LeetCode]#2053. Kth Distinct String in an Array

Remove Null, None, and Empty Strings from an n-sub level dictionary

5 good programming habits that will change the way you code forever