Course4all
Join us on telegram
Home/dsa/Dynamic Programming/Minimum Path Sum in Grid

Minimum Path Sum in Grid

Master this topic with zero to advance depth.

Minimum Path Sum in Grid

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.

Visual Representation

Grid: [1, 3, 1] [1, 5, 1] [4, 2, 1] Paths: 1-3-1-1-1 = 7 (Min) 1-1-5-2-1 = 10 1-1-4-2-1 = 9
Medium

Examples

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

Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

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

Level I: Dynamic Programming (2D)

Intuition

The minimum sum to reach cell (i, j) is the value of the current cell plus the minimum of the paths reaching from above (i-1, j) or from the left (i, j-1).

Thought Process

  1. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
  2. Edges: For the first row, you can only come from the left. For the first column, you can only come from above.
  3. Base Case: dp[0][0] = grid[0][0].
⏱ O(M * N)💾 O(M * N)

Detailed Dry Run

grid = [[1, 3], [1, 5]]

CellCalculationSum
(0, 0)Base1
(0, 1)1 + grid[0][1] = 1+34
(1, 0)1 + grid[1][0] = 1+12
(1, 1)5 + min(dp[0][1], dp[1][0]) = 5 + min(4, 2)7
java
public class Main {
    public static 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 fromUp = (i > 0) ? dp[i-1][j] : Integer.MAX_VALUE;
                int fromLeft = (j > 0) ? dp[i][j-1] : Integer.MAX_VALUE;
                dp[i][j] = grid[i][j] + Math.min(fromUp, fromLeft);
            }
        }
        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(minPathSum(grid)); // 7
    }
}
Approach 2

Level II: Memoization (Top-Down Recursion)

Intuition

The recursive brute force for grid path counting has overlapping subproblems. We cache each (i, j) state so we never recompute it.

Visual

Memo Grid (m=3, n=3): | 0 | 1 | 1 | | 1 | 2 | ? | <- memo[1][2] reused by (2,2) | 1 | ? | ? |
⏱ O(M * N)💾 O(M * N) for memo + O(M + N) recursion stack

Detailed Dry Run

m=3, n=3. memo[2][2] = memo[1][2] + memo[2][1]. Both sub-calls are cached after first computation.

java
public class Main {
    static int[][] memo;
    public static int solve(int m, int n) {
        if (m == 1 || n == 1) return 1;
        if (memo[m][n] != 0) return memo[m][n];
        return memo[m][n] = solve(m - 1, n) + solve(m, n - 1);
    }

    public static int uniquePaths(int m, int n) {
        memo = new int[m + 1][n + 1];
        return solve(m, n);
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7)); // 28
    }
}

⚠️ Common Pitfalls & Tips

Recursion adds O(M+N) stack overhead compared to the iterative DP. For very large grids, prefer the iterative approach to avoid stack overflow.

Approach 3

Level III: Space Optimized (1D)

Intuition

To compute dp[i][j], we only need the value above it (previous row) and the value to its left (current row). We can use a single array of size n.

Logic Steps

  1. Initialize row array of size n with Infinity.
  2. Set row[0] = 0 (starting point for accumulation).
  3. For each i (row):
    • row[0] += grid[i][0]
    • For each j (col from 1 to n-1):
      • row[j] = grid[i][j] + min(row[j], row[j-1]).
  4. Return row[n-1].
⏱ O(M * N)💾 O(N)

Detailed Dry Run

grid = [[1, 3], [1, 5]]

Rowrow array calculationState
0[1, 1+3=4][1, 4]
1[1+1=2, 5+min(2, 4)=7][2, 7]
java
public class Main {
    public static int minPathSum(int[][] grid) {
        int n = grid[0].length;
        int[] row = new int[n];
        row[0] = grid[0][0];
        for (int j = 1; j < n; j++) row[j] = row[j - 1] + grid[0][j];

        for (int i = 1; i < grid.length; i++) {
            row[0] += grid[i][0];
            for (int j = 1; j < n; j++) {
                row[j] = grid[i][j] + Math.min(row[j], row[j - 1]);
            }
        }
        return row[n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 2}, {1, 1}};
        System.out.println(minPathSum(grid)); // 3
    }
}
← Previous QuestionFrog Jump
Next Question →Maximal Square