# 10 lines recursive with O(1) space O(n) time solution.

• Here is the code:

``````    int minPathSum(vector<vector<int>> & grid, int r, int c) {
if (r >= grid.size() || c >= grid[0].size()) return INT_MAX;
if (grid[r][c] >= 0) {
int v = min(minPathSum(grid, r, c+1), minPathSum(grid, r+1, c));
grid[r][c] = -(grid[r][c] + ((v == INT_MAX) ? 0 : v));
}
return -grid[r][c];
}
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
return minPathSum(grid, 0, 0);
}
``````

It is actually the same idea as following recursive plus memorization solution, just reuse grid itself as cache. Since grid contains only non-negative numbers, we change it to -minPathSum after we figure it out.

``````    int minPathSum(vector<vector<int>> & grid, int r, int c, vector<vector<int>> & cache) {
if (r == grid.size() - 1 && c == grid[0].size() - 1) return grid[r][c];
if (cache[r][c] != -1) return cache[r][c];
int v = INT_MAX;
if (r < grid.size() - 1) v = min(v, minPathSum(grid, r+1, c, cache));
if (c < grid[0].size() - 1) v = min(v, minPathSum(grid, r, c+1, cache));
cache[r][c] = grid[r][c] + v;
return grid[r][c] + v;

}
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
vector<vector<int>> cache(grid.size(), vector<int>(grid[0].size(), -1));
return minPathSum(grid, 0, 0, cache);
}
``````

And we can re-write the code in DP iterative way use same idea:

``````    int minPathSum(vector<vector<int> > &grid) {
if (grid.empty() || grid[0].empty()) return 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (j > 0 && i > 0) {
grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
} else if (j > 0) {
grid[i][j] += grid[i][j-1];
} else if (i > 0) {
grid[i][j] += grid[i-1][j];
}
}
}
return grid.back().back();
}
``````

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