Minimum Path Sum

Created on: Jan 15, 2025

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

public class Solution {

    public static int optimalPath(Integer[][] grid) {
        return null;
    }

    public static boolean doTestsPass() {
        boolean result = true;

        result &= optimalPath(new Integer[][]
                {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}
        ) == 7;
        return result;
    }

    public static void main(String[] args) {
        if (doTestsPass()) {
            System.out.println("All tests pass");
        } else {
            System.out.println("Tests fail.");
        }
    }
}

Solution

public static int optimalPath(Integer[][] grid) {
    int row = grid.length;
    int col = grid[0].length;

    int[][] dp = new int[row][col];

    dp[0][0] = grid[0][0];

    // fill the 0th index column
    for (int i = 1; i < row; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    // fill the 0th index row
    for (int j = 1; j < col; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

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

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

Reference

leetcode