64. 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:

Since we can only go right or go down, the minimum sum at each point only depends on its top and its left value.

We use f[i][j] to denote the minimum sum from the origin to coordinate (i, j).



Code:

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    f[i][j] = j == 0 ? grid[0][0] : grid[i][j] + f[i][j - 1];
                    continue;
                }
                if (j == 0) {
                    f[i][j] = i == 0 ? grid[0][0] : grid[i][j] + f[i - 1][j];
                    continue;
                }
                f[i][j] = grid[i][j] + Math.min(f[i - 1][j], f[i][j - 1]);
            }
        }
        return f[m - 1][n - 1];
    }
}