描述
Given a m x n
grid
filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example 1:
1 2 3
| Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
|
Example 2:
1 2
| Input: grid = [[1,2,3],[4,5,6]] Output: 12
|
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
分析
动态规划。推导公式是:grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
, 注意处理边界情况即可。
解决方案1(Python3)
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution: def minPathSum(self, grid: List[List[int]]) -> int: for i in range(len(grid)): for j in range(len(grid[0])): if i == j == 0: continue elif i == 0: grid[i][j] = grid[i][j-1] + grid[i][j] elif j == 0: grid[i][j] = grid[i-1][j] + grid[i][j] else: grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j] return grid[-1][-1]
|
解决方案2(Golang)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| func minPathSum(grid [][]int) int { if len(grid) == 0 || len(grid[0]) == 0 { return 0 } rows, columns := len(grid), len(grid[0]) dp := make([][]int, rows) for i := 0; i < len(dp); i++ { dp[i] = make([]int, columns) } dp[0][0] = grid[0][0] for i := 1; i < rows; i++ { dp[i][0] = dp[i-1][0] + grid[i][0] } for j := 1; j < columns; j++ { dp[0][j] = dp[0][j-1] + grid[0][j] } for i := 1; i < rows; i++ { for j := 1; j < columns; j++ { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] } } return dp[rows-1][columns-1] }
func min(x, y int) int { if x < y { return x } return y }
|
相关问题