题目描述
题目链接: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])
(注意边界条件)。但注意到我们从头到尾只会同时使用两行数据,因此我们可以将其简化为使用一维数组进行更新可以,具体参考以下代码:
#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