題目來源:
https://leetcode.com/problems/minimum-path-sum/
題意分析:
給定一個m×n的非負矩陣,找到一條路使得從(0,0)到(m - 1,n - 1)經過的所有數字的和最小(類似上兩題,隻能向下和向上)。
題目思路:
和上一題類似,用一個二維矩陣a[i][j]代表從(0,0)到(i,j)的最小和。那麼a[i][j] = min(a[i-1][j],a[i][j -1]) + nums[i][j]。那麼這題也是一個動态規劃問題,隻需要把a的整個表打出來就可以了。時間複雜度是O(m×n)。
代碼(Python):
1 class Solution(object):
2 def minPathSum(self, grid):
3 """
4 :type grid: List[List[int]]
5 :rtype: int
6 """
7 m,n = len(grid),len(grid[0])
8 ans = [[0 for i in range(n)] for j in range(m)]
9 ans[0][0] = grid[0][0]
10 for i in range(m):
11 for j in range(n):
12 if i !=0 and j == 0:
13 ans[i][j] = ans[i-1][j] + grid[i][j]
14 elif i == 0 and j != 0:
15 ans[i][j] = ans[i][j - 1] + grid[i][j]
16 elif i != 0 and j != 0:
17 ans[i][j] = min(ans[i - 1][j],ans[i][j - 1]) + grid[i][j]
18 return ans[m - 1][n - 1]
View Code
轉載請注明出處:http://www.cnblogs.com/chruny/p/5008373.html