[LeetCode] 64. Minimum Path Sum

Posted on | In

Problem

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.

Example:

1
2
3
4
5
6
7
8
Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Explanation 1

  1. Similar to 62. Unique Paths, we can create a dp[][] and use dynamic programming to solve this problem.

  2. The base case is dp[0][0] has the same value as grid[0][0]. The top row element will be its current value plus its left value, dp[0][col] = grid[0][col] + dp[0][col-1]. The left most column element will be its current value plus its top value, dp[row][0] = grid[row][0] + dp[row-1][0].

  3. Now, we need to find the function. The function to calculate dp[row][col] will be its current value plus the minimum between its top value and its left value. In other word, dp[row][col] = grid[row][col] + min(dp[row-1][col], dp[row][col-1]).

  4. The result will be the bottom right element of dp, which is dp[row-1][col-1].

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        if (grid == null || grid.length == 0) return 0;

        dp[0][0] = grid[0][0];
        // left most column
        for (int row = 1; row < dp.length; row++) {
            dp[row][0] = grid[row][0] + dp[row-1][0];
        }

        // top row
        for (int col = 1; col < dp[0].length; col++) {
            dp[0][col] = grid[0][col] + dp[0][col-1];
        }

        for (int row = 1; row < dp.length; row++) {
            for (int col = 1; col < dp[0].length; col++) {
                dp[row][col] = grid[row][col] + Math.min(dp[row][col-1], dp[row-1][col]);
            }
        }

        return dp[dp.length-1][dp[0].length-1];
    }
}

Explanation 2

  1. We can save by space by using a 1 dimensional array dp[] that has size col. Initialize all its elements as INT_MAX except dp[0] = 0. The reason we can use the 1 dimensional array is the current element’s min sum is only depends on its left and top element’s min sum.

  2. We don’t need to calculate the min sum of the first row and first column. Instead, when we iterate, if c == 0 that means its first column, so we can update dp[c] = grid[r][c] + dp[c]. Else, we need to compare the left element’s dp[c-1] and top element’s dp[c] and choose the minimum one. If the current element is on the first row, dp[c] is the INT_MAX, so we will choose the minimum dp[c-1] which is on the left side, then plus the current element grid[r][c], so dp[c] = grid[r][c] + min(dp[c], dp[c-1]).

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[] dp = new int[col];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (c == 0) {
                    dp[c] = grid[r][c] + dp[c];
                } else {
                    dp[c] = grid[r][c] + Math.min(dp[c], dp[c-1]);
                }
            }
        }

        return dp[col-1];
    }
}

Explanation 3

  1. We can also save space by replacing the grid element. We need to iterate every element. If the current element is grid[0][0], then we continue. Else if r == 0, then we update the current element plus its left element. Else if c == 0, then we update the current element plus its top element. Else, we update the current element plus the minimum of its left and top element.

Solution 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (r == 0 && c == 0) continue;
                else if (r == 0) grid[r][c] += grid[r][c-1];
                else if (c == 0) grid[r][c] += grid[r-1][c];
                else grid[r][c] += Math.min(grid[r][c-1], grid[r-1][c]);
            }
        }

        return grid[row-1][col-1];
    }
}