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

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:

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