# 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.
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
Approach 1: DP (can optimize to O(N) space).
# Code (Python)
Approach 1:
def minPathSum(self, grid):
# O(N) space
min_paths = [grid[0][0]]
for j in range(1, len(grid[0])):
min_paths.append(min_paths[-1] + grid[0][j])
for i in range(1, len(grid)):
for j in range(len(grid[0])):
if j == 0:
min_paths[j] += grid[i][j]
else:
min_paths[j] = min(min_paths[j], min_paths[j-1]) + grid[i][j]
return min_paths[-1]
# Code (C++)
Approach 1:
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int rowSize = grid.size();
if (rowSize == 0)
return 0;
int colSize = grid[0].size();
int minSum[rowSize][colSize];
for (int i = rowSize - 1; i >= 0; --i)
{
for (int j = colSize - 1; j >= 0; --j)
{
minSum[i][j] = grid[i][j];
if (i < rowSize - 1 && j < colSize - 1)
minSum[i][j] += std::min(minSum[i+1][j], minSum[i][j+1]);
else if (i < rowSize - 1)
minSum[i][j] += minSum[i+1][j];
else if (j < colSize - 1)
minSum[i][j] += minSum[i][j+1];
}
}
return minSum[0][0];
}
};