# LeetCode64. Minimum Path Sum（动态规划）

## LeetCode64. Minimum Path Sum（动态规划）

• Medium
• Accepted：215,048
• Submissions：468,498

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.

### 链接

https://leetcode.com/problems/minimum-path-sum

### 代码

• Runtime: 12 ms, faster than 99.16% of C++ online submissions for Minimum Path Sum.
• Memory Usage: 10.9 MB, less than 79.87% of C++ online submissions for Minimum Path Sum.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (i == 0 && j == 0)
grid[i][j] = grid[i][j];
else if (i == 0 && j != 0)
grid[i][j] = grid[i][j - 1] + grid[i][j];
else if (i != 0 && j == 0)
grid[i][j] = grid[i - 1][j] + grid[i][j];
else
grid[i][j] = min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
}
}
return grid[n - 1][m - 1];
}
};
• Runtime: 12 ms, faster than 99.16% of C++ online submissions for Minimum Path Sum.
• Memory Usage: 10.7 MB, less than 98.11% of C++ online submissions for Minimum Path Sum.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
for (int i = 1; i < n; ++i)
grid[i][0] = grid[i - 1][0] + grid[i][0];
for (int j = 1; j < m; ++j)
grid[0][j] = grid[0][j - 1] + grid[0][j];
for (int i = 1; i < n; ++i)
for (int j = 1; j < m; ++j)
grid[i][j] = min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
return grid[n - 1][m - 1];
}
};

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
• Runtime: 16 ms, faster than 23.50% of C++ online submissions for Minimum Path Sum.
• Memory Usage: 10.8 MB, less than 94.65% of C++ online submissions for Minimum Path Sum.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector <int> cur(m, grid[0][0]);
for (int i = 1; i < m; ++i)
cur[i] = cur[i - 1] + grid[0][i];
for (int i = 1; i < n; ++i)
{
cur[0] += grid[i][0];
for (int j = 1; j < m; ++j)
cur[j] = min(cur[j - 1], cur[j]) + grid[i][j];
}
return cur[m - 1];
}
};

The end.
2019年3月24日 星期日