Problem Statement

You are given an m x n grid filled with non-negative integers, representing the cost to travel through each cell.

You can only move right or down at any point in time.

Return the minimum sum of the path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1).

Example

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

Output: 7

Explanation:
Path with minimum sum = 1 → 3 → 1 → 1 → 1 = 7

Key Constraints

• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

Approach Overview

This is a classic Dynamic Programming (DP) problem. You are choosing between two directions: right and down.

At any cell (i,j), the minimum path sum to reach it is the minimum of:

• the path sum to the top cell (i-1,j)
• the path sum to the left cell (i,j-1)

Then, add the current cell’s value.

Recursive Solution (Without DP – Brute Force)

Idea:

From (i,j), we recursively compute the minimum path sum by checking:

• move down: (i+1,j)
• move right: (i,j+1)

This approach is exponential, and leads to Time Limit Exceeded for large grids.

Code:

public int minPathSum(int[][] grid) {
    return dfs(grid, 0, 0);
}

private int dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;

    // Base case: out of bounds
    if (i >= m || j >= n) return Integer.MAX_VALUE;

    // Base case: destination reached
    if (i == m - 1 && j == n - 1) return grid[i][j];

    int right = dfs(grid, i, j + 1);
    int down = dfs(grid, i + 1, j);

    return grid[i][j] + Math.min(right, down);
}

Time: O(2^(m+n)) – Exponential
Space: O(m + n) – Recursion stack

Recursive + Memoization (Top-Down DP)

We cache the results of subproblems using a 2D dp[][] array.

Code:

public class MinimumPathSum {

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Integer[][] dp = new Integer[m][n];
        return dfs(grid, 0, 0, dp);
    }

    private int dfs(int[][] grid, int i, int j, Integer[][] dp) {
        int m = grid.length;
        int n = grid[0].length;

        if (i >= m || j >= n) return Integer.MAX_VALUE;

        if (i == m - 1 && j == n - 1) return grid[i][j];

        if (dp[i][j] != null) return dp[i][j];

        int right = dfs(grid, i, j + 1, dp);
        int down = dfs(grid, i + 1, j, dp);

        dp[i][j] = grid[i][j] + Math.min(right, down);
        return dp[i][j];
    }
}

Time: O(m * n)
Space: O(m * n) for memo + recursion stack

Bottom-Up DP (Tabulation)

We build a DP table from bottom up by initializing dp[0][0] = grid[0][0].

Each cell dp[i][j] is filled using:

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

Code:

public class MinimumPathSum {

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

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

        // Fill first row
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        // Fill first column
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        // Fill the rest of the grid
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m - 1][n - 1];
    }
}

Time: O(m * n)
Space: O(m * n)

Optimized Space (1D Array)

Since each row only depends on the current and previous values, we can use a 1D DP array.

Code:

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];

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

    // First row
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }

    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0]; // First column
        for (int j = 1; j < n; j++) {
            dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
        }
    }

    return dp[n - 1];
}