64. Minimum Path Sum

Problem Statement

Medium

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:

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

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

Java — bottomUp

Source file

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; j--)
                grid[i][j] += i == m - 1 && j == n - 1 ? 0
                        : i == m - 1 ? grid[i][j + 1]
                                : j == n - 1 ? grid[i + 1][j]
                                        : Math.min(grid[i + 1][j], grid[i][j + 1]);
        // for (int i = 0; i < m; i++)
        //     System.out.println(Arrays.toString(grid[i]));
        return grid[0][0];
    }
}

Java — topDown

Source file

class Solution {
    int INF = Integer.MAX_VALUE, m, n;

    public int minPathSum(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int[][] minCost = new int[m][n];
        for (int i = 0; i < m; i++)
            Arrays.fill(minCost[i], INF);
        minCost[m - 1][n - 1] = grid[m - 1][n - 1];
        dfs(grid, 0, 0, minCost);
        return minCost[0][0];
    }

    private int dfs(int[][] grid, int i, int j, int[][] minCost) {
        if (i >= m || j >= n)
            return Integer.MAX_VALUE;
        if (minCost[i][j] != INF)
            return minCost[i][j];
        return minCost[i][j] = grid[i][j] +
                Math.min(dfs(grid, i + 1, j, minCost), dfs(grid, i, j + 1, minCost));
    }
}

Java

Source file

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; j--)
                grid[i][j] += i == m - 1 && j == n - 1 ? 0
                        : i == m - 1 ? grid[i][j + 1]
                                : j == n - 1 ? grid[i + 1][j]
                                        : Math.min(grid[i + 1][j], grid[i][j + 1]);
        // for (int i = 0; i < m; i++)
        //     System.out.println(Arrays.toString(grid[i]));
        return grid[0][0];
    }
}