东莞长安营销型网站建设/磁力搜索神器

1.题目详情

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

2.解题思路

动态规划问题，本题不用建额外的dp二维数组浪费时间。
状态方程：grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
注意考虑边缘临界值

3.代码实现

class Solution:def minPathSum(self, grid: List[List[int]]) -> int:m = len(grid)n = len(grid[0])for i in range(m):for j in range(n):if i == j == 0:continueelif i == 0:grid[i][j] += grid[i][j-1] elif j == 0:grid[i][j] += grid[i-1][j] else:grid[i][j] += min(grid[i-1][j],grid[i][j-1]) return grid[-1][-1]

4.知识点

动态规划，注意临界值。