# LeetCode Minimum Path Sum: DP with Memory Optimization

## Overview

LeetCode Minimum Path Sum: Dynamic Programming is used to define the minimum path sum recursive formula, with Memory Optimization, it would be done in O(n) space.

## LeetCode 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.

## Solution and Precautions: DP with Memory Optimization

We use dynamic programming to solve it. Let F(m, n) denote the minimum path sum in the m * n grid, we then have F(m, n) = min(F(m-1, n), F(m, n-1) ) + grid[m][n], the boundary is that F(0, 0) = grid[0][0], and F(0, i) = F(0, i-1) + grid[0][i] for i >= 1 and F(j, 0) = F(j-1, 0) + grid[j][0] for j >= 1. The following code is the direct implementation with O(m * n) memory cost and it is accepted by LeetCode OJ to pass this Minimum Path Sum problem:

```class Solution {

public:
int minPathSum(vector<vector<int> > &grid) {
int m = grid.size();
if (m < 1)
return 0;
int n = grid[0].size();

vector<vector<int> > dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[0][1] = 0;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
return dp[m][n];
}

};
```

One further optimization could be done is reduce the memory cost from O(m * n) to O(n). Image we do the DP calculation row by row, the current value (dp[i][j]) only depending on dp[i-1][j] and dp[i][j-1], so there is no need to store all the previous values. The following code is even simpler and pass the OJ too:

```int minPathSum(vector<vector<int> > &grid) {
int m = grid.size();
if (m < 1)
return 0;
int n = grid[0].size();

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

return dp[n];
}
```

Pay special attention to this statement of “dp[1] = 0″ rather than “dp[0] = 0″ and the latter one will give a WA result. Think about why by yourself!?

## Summary

LeetCode Minimum Path Sum: Dynamic Programming is used to define the minimum path sum recursive formula, with Memory Optimization, it would be done in O(n) space.

Written on May 9, 2013