64. Minimum Path Sum
從最後一個位置向原點出發，每次都往總和比較小的路徑前進，直到原點為止，找出最小的總和。
遞迴
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
def helper(row, col):
if row < 0 or col < 0:
return float('inf')
if row == 0 and col == 0:
return grid[row][col]
return min(
dp(row-1, col),
dp(row, col-1)
) + grid[row][col]
return helper(rows-1, cols-1)自頂向下
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
memo = [[-1] * cols for _ in range(rows)]
memo[0][0] = grid[0][0]
def dp(row, col):
if row < 0 or col < 0:
return float('inf')
if memo[row][col] != -1:
return memo[row][col]
memo[row][col] = min(
dp(row-1, col),
dp(row, col-1)
) + grid[row][col]
return memo[row][col]
return dp(rows-1, cols-1)class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
memo = {}
memo[(0, 0)] = grid[0][0]
def dp(row, col):
if row < 0 or col < 0:
return float('inf')
if (row, col) not in memo:
memo[(row, col)] = min(dp(row-1, col), dp(row, col-1)) + grid[row][col]
return memo[(row, col)]
return dp(rows-1, cols-1)自底向上
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
memo = [[-1] * cols for _ in range(rows)]
memo[rows-1][cols-1] = grid[rows-1][cols-1]
for row in reversed(range(rows-1)):
memo[row][cols-1] = memo[row+1][cols-1] + grid[row][cols-1]
for col in reversed(range(cols-1)):
memo[rows-1][col] = memo[rows-1][col+1] + grid[rows-1][col]
print(memo)
for row in reversed(range(rows-1)):
for col in reversed(range(cols-1)):
memo[row][col] = min(memo[row+1][col], memo[row][col+1]) + grid[row][col]
return memo[0][0]從原點向終點出發
遞迴
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
def dp(row, col):
if row == rows - 1 and col == cols - 1:
return grid[row][col]
if row >= rows or col >= cols:
return float('inf')
return grid[row][col] + min(dp(row+1, col), dp(row, col+1))
return dp(0, 0)自頂向下
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
memo = {}
memo[(rows-1,cols-1)] = grid[rows-1][cols-1]
def dp(row, col):
if row >= rows or col >= cols:
return float('inf')
if (row, col) not in memo:
memo[(row, col)] = grid[row][col] + min(dp(row+1, col), dp(row, col+1))
return memo[(row, col)]
return dp(0, 0)自底向上
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
memo = [[-1] * cols for _ in range(rows)]
memo[0][0] = grid[0][0]
for row in range(1, rows):
memo[row][0] = memo[row-1][0] + grid[row][0]
for col in range(1, cols):
memo[0][col] = memo[0][col-1] + grid[0][col]
for row in range(1, rows):
for col in range(1, cols):
memo[row][col] = min(memo[row-1][col], memo[row][col-1]) + grid[row][col]
return memo[rows-1][cols-1]