0%

[Leetcode]64. Minimum Path Sum(C++)

题目描述

题目链接:64. 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.

例子

例子 1

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.

例子 2

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Note

You can only move either down or right at any point in time.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

解题思路

这道题可以用动态规划来思路来做,最简单的思路是创建一个相等大小的二维数组 minSum[m][n], 其中 minSum[i][j] 表示从左上角到对应位置的最小路径和,由题目得知路径只能往下或往右走,因此状态转移方程为: minSum[i][j] = grid[i][j] + min(minSum[i][j-1], minSum[i-1][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
25
26
27
28
29
30
31
32
33
#include <vector>

class Solution {
public:
int minPathSum(std::vector<std::vector<int>>& grid) {
std::vector<int> current_row = grid[0];
for (int i = 0; i < grid.size(); ++i) {
// iteratively update min sum for each row, we only need the result of the last row
calMinSum(grid, current_row, i);
}
return current_row.back();
}

private:
void calMinSum(const std::vector<std::vector<int>>& grid, std::vector<int>& current_row, int next_row_idx) {

for (int i = 0; i < current_row.size(); ++i) {

if (next_row_idx == 0) {
// #1: if the first row, simply add min sum from left side
current_row[i] += (i == 0? 0 : current_row[i - 1]);
}
else if (i == 0) {
// #2: if the first element, simply add min sum from upper grid
current_row[i] += grid[next_row_idx][i];
}
else {
// #3: general case: choose min sum between left and upper side
current_row[i] = std::min(current_row[i], current_row[i - 1]) + grid[next_row_idx][i];
}
}
}
};
  • 时间复杂度: O(mn)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 64.MinimumPathSum.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions