[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

Release Overview — Unimus 2.1.0

A Guild to Beautiful Games

Developer Diaries E06

IndentationError: unindent does not match any outer indentation level

When Edge becomes the Center

How to Migrate Kafka Cluster with No Downtime

How to setup Airflow Sensor’s mode as Reschedule

CS 371P Spring 2021: Caroline Hatcher

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]#2114. Maximum Number of Words Found in Sentences

LeetCode Patterns Adventure 23 — Path Sum

Implementing Linked List Operations in Python

Introduction to LinkedList