描述

給定一個只含非負(fù)整數(shù)的m*n網(wǎng)格，找到一條從左上角到右下角的可以使數(shù)字和最小的路徑。
你在同一時間只能向下或者向右移動一步

樣例
樣例 1:
輸入: [[1,3,1],[1,5,1],[4,2,1]]
輸出: 7

樣例解釋： 路線為： 1 -> 3 -> 1 -> 1 -> 1。

樣例 2:
輸入: [[1,3,2]]
輸出: 6

解釋: 路線是： 1 -> 3 -> 2

思路

題目要求只能往下或者向右走。

則單元格dp(i,j）題解應(yīng)該是單元格dp（i-1,j）單元格dp（i，j-1）的較小值+單元格（i,j）的值。
考慮特殊情況邊界問題：
（1）左邊為邊界，即i=0情況下，單元格dp(i,j）題解只能從上面來
解為單元格dp（i，j-1）+單元格（i,j）的值。
(2)上邊為邊界,即j=0情況下。解只能從左邊來。解為單元格dp（i-1，j）+單元格（i,j）的值。
（3）上下都是邊界，即處于起點位置，直接返回坐標(biāo)（i,j）。

代碼

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 hereif (not grid):return 0m = len(grid)#行數(shù)n = len(grid[0])#列數(shù)for i in range(1, n):#左邊為邊界時，解只能從上班來grid[0][i] += grid[0][i - 1]for j in range(1, m):#上邊為邊界時，解只能從左邊來grid[j][0] += grid[j - 1][0]for x in range(1, m):#無邊界時for y in range(1, n):grid[x][y] += min(grid[x - 1][y], grid[x][y - 1])return grid[-1][-1] #包含了左邊和上都是邊界的情況 c=Solution() grid=[[1,3,1],[1,5,1],[4,2,1]]d=c.minPathSum(grid) print(d)

答案：

半路出家的小白，寫博文不容易。如果你覺得本文對你有用，請點個贊支持下。

總結(jié)

以上是生活随笔為你收集整理的leetcode最小路径和 （动态规划）python的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。