Minimum Path Sum ---------How can I reduce the memory.

• Here is the idea:

1. f[m][n] is a matrix store the min value of every location we can
get.
2. f[0][0] =grid[0][0], f[i][0]=f[i-1][0]+grid[i][0],
f[0][j]=f[0][j-1]+grid[0][j]
3. f[i][j]=min(f[i-1][j],f[i][j-1])+grid[i][j].
4. at last return the f[m-1][n-1]

``````class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int m=grid.size();
int n=grid[0].size();
int** f;
f=new int*[m];
for(int i=0;i<m;i){
f[i]=new int[n];
}
f[0][0]=grid[0][0];
for(int i=1;i<m;i++){
f[i][0]=f[i-1][0]+grid[i][0];
}
for(int i=1;i<n;i++){
f[0][i]=f[0][i-1]+grid[0][i];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++)
f[i][j]=min(f[i-1][j],f[i][j-1])+grid[i][j];
}
return f[m-1][n-1];
}
int min(int a,int b){
if(a>b)
return b;
else
return a;
}
};``````

• Welcome Joey! Please format your code properly by selecting your code, and clicking on the `{}` button. Also please read the FAQ for tips on asking a question.

• OK,it's fine now.

• Given the dynamic programming formula `f[i][j]=min(f[i-1][j],f[i][j-1])+grid[i][j]`:

Assume that you are populating the table row by row, the current value (`f[i][j]`) will be used immediately in the calculation of `f[i][j+1]`, so there is no need to store all the previous column values.

Therefore, you can do it in linear space complexity. Below is a sample code courtesy of Linfuzki@.

``````class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size();

vector<int> dp(n + 1, INT_MAX);
dp[1] = 0;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
dp[j + 1] = min(dp[j + 1], dp[j]) + grid[i][j];

return dp.back();
}
};``````

• You can reduce memory to O(n), if you visited i & i - 1 by i % 2, (i + 1) % 2

• Just do it in place.

``````class Solution:
# @param grid, a list of lists of integers
# @return an integer
def minPathSum(self, grid):
m = len(grid)
n = len(grid[0])
for i in range(m):
for j in range(n):
if i == j == 0:
pass
elif i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[-1][-1]``````

• The space can be O(mn), O(m), O(n) or O(min(m, n)) depending on how you do the DP. The last is achieved by progress anti-diagonally.

• Here is a O(n) solution:

``````class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
map<int,int> result;
//DP
for(int j =0 ; j < grid.back().size(); j ++)
{
result[j] = INT_MAX;
}
result[-1]=0;
for(int i = 0 ; i < grid.size() ; i ++)
{
for(int j =0 ; j < grid.back().size(); j ++)
{
if(result[j] < result[j-1])
{
result[j]+= grid[i][j];
}
else
{
result[j]= result[j-1]+grid[i][j];
}
result[-1]= INT_MAX;
}
}
return result[grid.back().size()-1];
}
};``````

• Hi! Thank you for your neat code! Could you explain it?

• This is a java version of answer. The initial value assignment is key point.

``````public class Solution {
public int minPathSum(int[][] grid) {
//Deal with boundary condition
if (grid.length==0||grid[0].length==0) return 0;
//Declare
int row=0;
int column=0;
int sum[]=new int[grid[0].length+1];
//Initiate values
for(column=0;column<=grid[0].length;column++)
sum[column]=Integer.MAX_VALUE;
//Cycle
sum[1]=0;
for (row=0;row<grid.length;row++)
for (column=0;column<grid[0].length;column++)
sum[column+1]=Math.min(sum[column+1],sum[column])+grid[row][column];

return sum[column];
}
}``````

• Hi, 1337c0d3r, What do you think that we just use the in-place-calculation algorithm written below by geekan? In that way, we do not need any extra space.

• actually,we can do it in place by triping through the grid only once.in order to reduce the code,i specially handle the first row and the first column.This is a c++ version of answer.

``````class Solution {
public:

int minPathSum(vector<vector<int> > &grid) {

int row,col,rowNum=grid.size(),colNum=grid[0].size();
for(col=1;col<colNum;++col)
grid[0][col]+=grid[0][col-1];
for(row=1;row<rowNum;++row)
grid[row][0]+=grid[row-1][0];
for(row=1;row<rowNum;++row)
for(col=1;col<colNum;++col)
grid[row][col]+=grid[row-1][col]>grid[row][col-1]?grid[row][col-1]:grid[row-1][col];
return grid[rowNum-1][colNum-1];
}
};
``````

• pretty straight forward DP problem

``````public class Solution {
public int minPathSum(int[][] grid) {
int m = grid[0].length;
int n = grid.length;
for(int i=1; i<n ; i++) grid[i][0]+=grid[i-1][0];
for(int j=1; j<m ; j++) grid[0][j]+=grid[0][j-1];

for(int i=1; i<n ; i++){
for(int j=1; j<m ; j++){
grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
}
}

return grid[n-1][m-1];
}
}``````

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• nice solution, row by row is keywords, just calculate it in mind, and will get the answer, nice work. thanks.

• This post is deleted!

• Its not the most efficient one. You can still reduce space complexity to O(n).

• That was a badass answer 1337c0d3r !

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