# 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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.