61. Minimum Path Sum

Since you can only arrive at a cell from above or from the left, the cheapest way to reach it is its own value plus the smaller of those two neighbours' best costs. Fill the dp grid top-left to bottom-right; the bottom-right cell holds the answer.

Idea

A path only moves right or down, so a cell (i,j) can only be entered from (i-1,j) (above) or (i,j-1) (left). The minimum cost to reach it is therefore its own value plus the cheaper of those two predecessors:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

The top row and left column have only one predecessor each, so their costs are just running prefix sums.

Algorithm

1. dp[0][0] = grid[0][0].
2. Fill in row-major order. For each cell (skipping the origin): up = dp[i-1][j] if i>0 else ∞; left = dp[i][j-1] if j>0 else ∞; dp[i][j] = grid[i][j] + min(up, left).
3. Return dp[m-1][n-1].

Worked example: [[1,3,1],[1,5,1],[4,2,1]]

Filling dp:

1  4  5
2  7  6
6  8  7

• Top row: 1, 1+3=4, 4+1=5. Left col: 1, 1+1=2, 2+4=6.
• (1,1)=5+min(4,2)=7; (1,2)=1+min(5,7)=6; (2,1)=2+min(7,6)=8; (2,2)=1+min(6,8)=7.

Answer dp[2][2] = 7 (path 1→3→1→1→1).

Complexity

• Time: O(m·n).
• Space: O(m·n) (reducible to O(n)).

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                int up = (i > 0) ? dp[i - 1][j] : Integer.MAX_VALUE;
                int left = (j > 0) ? dp[i][j - 1] : Integer.MAX_VALUE;
                dp[i][j] = grid[i][j] + Math.min(up, left);
            }
        }
        return dp[m - 1][n - 1];
    }
}