LeetCode 64 Minimum Path Sum

LeetCode 64

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.

Difficulty
Medium

Similar Problems
[LeetCode 63] Unique Paths II M
[LeetCode 174] Dungeon Game H

Problem: Minimum Cost Path (MCP)

Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns the minimum cost of path from (0, 0) to (m, n). Total cost of a path to (m, n) is sum of all the costs on that path (including both source and destination).

You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed.
You may assume that all costs are positive integers.

Extensions

(1) Maximum Path Sum

(2) Dual Min Path Sum (double line dp)
If two people starting out from the top-left corner at the same time, towarding to the right-bottom corner, if the paths of the people have walked through can not have intersection (the never walk through the same point in between), what would be the max distance the two path have?

(3) Same problem with the (2), one person take a round trip from top-left to bottom-right, and back from bottom-right to top-left, the max distance of this round trip?

Analysis

A classic dp problem. Let dp[i][j] represent the minimum total cost of path from top-left corner to grid[i][j]. then we have dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

Be careful with the boundary condition:

the first row and first column. e.g. dp[i-1][j].

• If we start the index from i = 0, then dp[i-1][j] will have negative index dp[-1][j], which is wrong.
  We can let dp[i][j] do represent the minimum cost of path from (0, 0) to grid[i-1][j-1]. Then we start index from i = 1, j = 1, thus dp[m][n] should be the answer. Since we need to use dp[m][n] we have to declare the 2-D array the size of m+1 and n+1. Also, grid[i-1][j-1] is the position we are processing.

• Inital value, since dp[0][j] and dp[i][0] does not any meaning in our case(we only to use it to avoid overflow.

Improvement

Since dp[i][j] has only thing to do with the previous dp[i-1][j] and dp[i][j-1],

we can reduce the 2-d array to 1-d array, using rolling array to reduce space usage.

Solutions

1. DP with 2D Array

class Solution {
public:
    int minPathSum(vector<vector<int>> &grid) {
        int row = grid.size(), col;
        if(row == 0) return 0;
        else col = grid[0].size();
        vector<vector<int>> dp(row + 1, vector<int>(col + 1, INT_MAX));
        dp[0][1] = 0;
        for(int i = 1; i <= row; i++)
            for(int j = 1; j <= col; j++)
                dp[i][j] = grid[i - 1][j - 1] + min(dp[i][j - 1], dp[i - 1][j]);
        return dp[row][col];
    }
};

1. DP with 1D Array

class Solution {
public:
    int minPathSum(vector<vector<int>> &grid) {
        int row = grid.size(), col;
        if(row == 0) return 0;
        else col = grid[0].size();
        vector<int> dp(col + 1, INT_MAX);
        dp[1] = 0;
        for(int i = 1; i <= row; i++)
            for(int j = 1; j <= col; j++)
                dp[j] = grid[i - 1][j - 1] + min(dp[j], dp[j - 1]);
        return dp[col];
    }
};

1. DP In Place

class Solution{
public:
    int miniPathSum(vector<vector<int>> &grid){
        int m = grid.size();
        int n = grid[0].size();
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(i == 0){
                    if(j == 0) grid[i][j] = grid[i][j];
                    else grid[i][j]= grid[i][j - 1] + grid[i][j];
                }
                else if(j == 0) grid[i][j] = grid[i][i-1][j] + grid[i][j];
                else grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
            }
        }
        return grid[m - 1][n -1];
    }
};

1. Golang Solution (1D Array)

func minPathSum(grid [][]int) int {
    m := len(grid)
    if m == 0 {
        return 0
    }

    n := len(grid[0])
    dp := make([]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = MaxInt
    }
    dp[1] = 0
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            dp[j] = grid[i-1][j-1] + min(dp[j], dp[j-1])
        }
        fmt.Println(dp)
    }

    return dp[n]
}

const MaxUint = ^uint(0)            // should be 1111-1111
const MaxInt = int(MaxUint >> 1)    // should be 0111-1111

func min(a, b int) int {
    if a <= b {
        return a
    }
    return b
}

Reference