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