leetcode-64 Minimum Path Sum

64. Minimum Path Sum

Description

Given a $m \times 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
2
3
4
5
6
7
8
Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Analyse

和 [LeetCode] 62. Unique Paths
有点像，给出一个方格，从左上方走到右下方，但本题是要找到加权最短路径

动态规划

  1. 定义dp[i][j]为从(0, 0)走到(i, j)的加权最短路径

  2. 找出递推公式

有两种情况到达(i, j):

  • 从(i-1, j)向下走了一步
  • 从(i, j-1)向右走了一步

dp[i][j] = min(dp[i-1][j], dp[i, j-1]) + grid[i][j]

  1. 给出一些初值

在这题里是x轴和y轴边界上的值，如

1
2
3
[1,3,1]             [1,4,5]
[1,5,1]     ->      [2, , ]
[4,2,1]             [6, , ]
1
2
3
dp[0][0] = grid[0][0]
dp[i][0] = dp[i-1][0] + grid[i][0]
dp[0][j] = dp[0][j-1] + grid[0][j]

最终代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int minPathSum(vector<vector<int>>& grid) {
    if (grid.empty()) return 0;

    int row = grid.size();
    int col = grid[0].size();

    vector<vector<int>> dp(row, vector<int>(col, 0));
    dp[0][0] = grid[0][0];
    for (int i = 1; i < row; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }

    for (int j = 1; j < col; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }

    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }

    return dp[row-1][col-1];
}