给定一个包含非负整数的mxn网格grid,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小
时间: 2024-01-19 09:03:59 浏览: 38
使用动态规划可以解决该问题。我们定义dp[i][j]为从左上角到(i,j)的最小路径和。则有状态转移方程:
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
其中,grid[i][j]表示网格(i,j)上的数字。由于从左上角到第一行和第一列的任何位置只有一条路径可走,因此可以先将dp数组的第一行和第一列初始化为从左上角到对应位置的路径和。最终答案为dp[m-1][n-1]。
以下是Python代码实现:
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
# 初始化第一行和第一列
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
# 状态转移
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]