难度:中等 关键词:动态规划
⭐️⭐️⭐️
1
题目描述
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小,每次移动只能向下或者向右一步。
2
题解
思路:动态规划
在LeetCode刷题DAY 2:最长回文子串中我们介绍了动态规划的含义,本次不再赘述,直接进入逻辑阐述。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
if not grid:
return 0
m = len(grid)
n = len(grid[0])
dp = [ [0] * n for i in range(m)]
for i in range(m):
for j in range(n):
if j == 0 and i == 0:
dp[i][j] = grid[0][0]
elif j == 0 and i!=0:
dp[i][j]=dp[i-1][0]+grid[i][j]
elif j!=0 and i==0:
dp[i][j]=dp[0][j-1]+grid[i][j]
else:
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
return dp[-1][-1]