Description

Minimum Path Sum

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:

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.


Solution

似曾相识

$$f(x, y) = cost_{(x,y)} + min(f(x-1, y), f(x, y-1))$$

Code Here

  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 33 34 35 36 37 38 39 40 41 42 43 44  func minPathSum(grid [][]int) int { row := len(grid) if row == 0 { return 0 } col := len(grid[0]) if col == 0 { return 0 } var left, up, minCost, upCost int // 从第二个格子开始 j := 1 for i := 0; i < row; i++ { for ; j < col; j++ { minCost = -1 left = j - 1 if left >= 0 { // 左边消耗 minCost = grid[i][left] } up = i - 1 if up >= 0 { // 上边消耗 upCost = grid[up][j] if upCost < minCost || minCost == -1 { minCost = upCost } } // 选择较少消耗的路径并加上自身消耗 // 保存当前格子消耗 grid[i][j] += minCost } j = 0 } // 返回最后一个格子消耗 return grid[row-1][col-1] }