# DP Solution, Linear space

• You can only reach a cell by going from its left or top neighbor.

``````class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
if(!grid.size())return 0;
const int rows=grid.size(),cols=grid[0].size();
// r[i] == min path sum to previous row's column i.
vector<int> r(cols,0);
int i,j;
r[0]=grid[0][0];
for(j=1;j<cols;j++){
r[j]=grid[0][j]+r[j-1];
}
for(i=1;i<rows;i++){
r[0]+=grid[i][0];
for(j=1;j<cols;j++){
r[j]=min(r[j-1],r[j])+grid[i][j];
}
}
return r[cols-1];
}
};``````

• Python version:

``````def minPathSum(self, grid):
if not grid:
return None
m, n = len(grid), len(grid[0])
table = [[float('inf')] * (n + 1) for _ in range(m + 1)]
table[0][1] = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
table[i][j] = min(table[i - 1][j], table[i][j - 1]) + grid[i - 1][j - 1]
return table[-1][-1]``````

• Yeah, saving much space.

• ``````public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0) return 0;
int[][] dp = new int[grid.length][grid[0].length];

for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (i == 0 && j == 0) dp[i][j] = grid[i][j];
else if (i == 0) dp[i][j] = grid[i][j] + dp[i][j - 1];
else if (j == 0) dp[i][j] = grid[i][j] + dp[i - 1][j];
else dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[grid.length - 1][grid[0].length - 1];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.