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