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

似曾相识

本题与《63. Unique Paths II》 使用相同的方法：

要到达右下角，需要经过左边或者上边的格子，而最少消耗自然是从这两个格子中选择到达它们所需消耗（非它们自身消耗）较少的一个：

$$ 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]
}

Similar Problem