crm系统哪家好/河南平价的seo整站优化定制

110. 最小路径和

给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。

注意事项

你在同一时间只能向下或者向右移动一步

解题思路：

[[1, 3, 5, 7, 9],[5, 2,8,5,1],[4,4,7,2,3],[3,6,6,1,1],[2,8,5,0,4]]

1、假设上面为m*n的网格，因为只能向下或者向右，所以第一行和第一列只能由前一位移动来，记录路径和

2、从[1][1]开始计算，找到左边或者上面的最小值，即dp[i][j] = grid[i][j] +min(dp[i][j-1], dp[i-1][j])

3、当全部的网络记录完成后，右下角的值就是最小路径和。

class Solution:"""@param grid: a list of lists of integers@return: An integer, minimizes the sum of all numbers along its path"""def minPathSum(self, grid):# write your code here#定义一个相同形状的数组n = len(grid)m = len(grid[0])dp = grid#左上角的路径和为自身。# 因为只能向右或者向下移动，所以第一行和第一列只能由上一位移动来for i in range(1, m):dp[0][i] = dp[0][i-1] + grid[0][i]for i in range(1, n):dp[i][0] = dp[i-1][0] + grid[i][0]# 记录其他位置的最优路径和，只能从上或者右，所以选择最优for i in range(1, n):for j in range(1, m):dp[i][j] = grid[i][j] + min(dp[i][j-1], dp[i-1][j])return dp[n-1][m-1]