Problem

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.

Examples

Example 1:

$$ \huge \begin{array}{|c|c|c|} \hline \colorbox{orange} 1 & \colorbox{orange} 3 & \colorbox{orange} 1 \\ \hline 1 & 5 & \colorbox{orange} 1 \\ \hline 4 & 2 & \colorbox{orange} 1 \\ \hline \end{array} $$

1
2
3

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:

$$ \huge \begin{array}{|c|c|c|} \hline \colorbox{orange} 1 & \colorbox{orange} 2 & \colorbox{orange} 3 \\ \hline 4 & 5 & \colorbox{orange} 6 \\ \hline \end{array} $$

1
2

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

Solution

Method 1 – Recursion (Top-Down)

Intuition

The problem asks for the minimum path sum from the top-left to the bottom-right of a grid, moving only right or down. Recursion allows us to break the problem into smaller subproblems: the minimum path sum to a cell is the cell’s value plus the minimum of the path sums to its top or left neighbor. We use recursion to explore all possible paths, handling edge cases for the first row and column.

Approach

  1. Define a recursive helper function that computes the minimum path sum to cell (row, col).
  2. Base case: If at (0, 0), return grid[0][0].
  3. If in the first row, can only move left; if in the first column, can only move up.
  4. Otherwise, return the cell’s value plus the minimum of the path sums from the top and left neighbors.
  5. Start recursion from the bottom-right cell.

Complexity

  • ⏰ Time complexity: O(2^{m+n}) in the worst case, since each cell can be reached from two directions and there is no memoization.
  • 🧺 Space complexity: O(m+n), due to the recursion stack depth.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        return dfs(grid, m - 1, n - 1);
    }
    int dfs(vector<vector<int>>& grid, int row, int col) {
        if (row == 0 && col == 0) return grid[0][0];
        if (row == 0) return grid[0][col] + dfs(grid, 0, col - 1);
        if (col == 0) return grid[row][0] + dfs(grid, row - 1, 0);
        return grid[row][col] + min(dfs(grid, row - 1, col), dfs(grid, row, col - 1));
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        return dfs(grid, m - 1, n - 1);
    }
    public int dfs(int[][] grid, int row, int col) {
        if (row == 0 && col == 0) return grid[0][0];
        if (row == 0) return grid[0][col] + dfs(grid, 0, col - 1);
        if (col == 0) return grid[row][0] + dfs(grid, row - 1, 0);
        return grid[row][col] + Math.min(dfs(grid, row - 1, col), dfs(grid, row, col - 1));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        return self.dfs(grid, m - 1, n - 1)
    def dfs(self, grid: list[list[int]], row: int, col: int) -> int:
        if row == 0 and col == 0:
            return grid[0][0]
        if row == 0:
            return grid[0][col] + self.dfs(grid, 0, col - 1)
        if col == 0:
            return grid[row][0] + self.dfs(grid, row - 1, 0)
        return grid[row][col] + min(self.dfs(grid, row - 1, col), self.dfs(grid, row, col - 1))

Method 2 – Top-Down DP with Memoization

Intuition

To avoid redundant calculations in recursion, we use memoization to store the minimum path sum for each cell. This ensures each subproblem is solved only once, making the solution efficient for large grids.

Approach

  1. Create a DP table to store the minimum path sum for each cell.
  2. Define a recursive helper function that checks if the value is already computed in the DP table.
  3. For each cell (row, col), compute the minimum path sum using the same logic as recursion, but store and reuse results from the DP table.
  4. Start recursion from the bottom-right cell.

Complexity

  • ⏰ Time complexity: O(m * n), where m and n are the grid dimensions, since each cell is computed once.
  • 🧺 Space complexity: O(m * n), for the DP table and recursion stack.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, -1));
        return dfs(grid, m - 1, n - 1, dp);
    }
private:
    int dfs(vector<vector<int>>& grid, int row, int col, vector<vector<int>>& dp) {
        if (row == 0 && col == 0) return grid[0][0];
        if (dp[row][col] != -1) return dp[row][col];
        if (row == 0) return dp[row][col] = grid[0][col] + dfs(grid, 0, col - 1, dp);
        if (col == 0) return dp[row][col] = grid[row][0] + dfs(grid, row - 1, 0, dp);
        return dp[row][col] = grid[row][col] + min(dfs(grid, row - 1, col, dp), dfs(grid, row, col - 1, dp));
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) Arrays.fill(dp[i], -1);
        return dfs(grid, m - 1, n - 1, dp);
    }
    private int dfs(int[][] grid, int row, int col, int[][] dp) {
        if (row == 0 && col == 0) return grid[0][0];
        if (dp[row][col] != -1) return dp[row][col];
        if (row == 0) return dp[row][col] = grid[0][col] + dfs(grid, 0, col - 1, dp);
        if (col == 0) return dp[row][col] = grid[row][0] + dfs(grid, row - 1, 0, dp);
        return dp[row][col] = grid[row][col] + Math.min(dfs(grid, row - 1, col, dp), dfs(grid, row, col - 1, dp));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[-1] * n for _ in range(m)]
        return self._dfs(grid, m - 1, n - 1, dp)
    def _dfs(self, grid: list[list[int]], row: int, col: int, dp: list[list[int]]) -> int:
        if row == 0 and col == 0:
            return grid[0][0]
        if dp[row][col] != -1:
            return dp[row][col]
        if row == 0:
            dp[row][col] = grid[0][col] + self._dfs(grid, 0, col - 1, dp)
            return dp[row][col]
        if col == 0:
            dp[row][col] = grid[row][0] + self._dfs(grid, row - 1, 0, dp)
            return dp[row][col]
        dp[row][col] = grid[row][col] + min(self._dfs(grid, row - 1, col, dp), self._dfs(grid, row, col - 1, dp))
        return dp[row][col]

Method 3 – Bottom-Up Dynamic Programming (In-Place)

Intuition

Instead of using recursion or extra memory, we can solve the problem by updating the grid directly. Each cell in the grid will store the minimum path sum to reach that cell from the top-left, using only previously computed values. This approach leverages the fact that the minimum path to each cell depends only on its top and left neighbors.

Approach

  1. Iterate through each cell in the grid row by row and column by column.
  2. For the top-left cell, keep its value as is.
  3. For cells in the first row, update by adding the value from the left neighbor.
  4. For cells in the first column, update by adding the value from the top neighbor.
  5. For all other cells, update by adding the minimum of the top and left neighbors.
  6. The answer is the value in the bottom-right cell after processing.

Complexity

  • ⏰ Time complexity: O(m * n), where m and n are the grid dimensions, as each cell is visited once.
  • 🧺 Space complexity: O(1), since the grid is updated in-place and no extra space is used.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int row = 0; row < m; ++row) {
            for (int col = 0; col < n; ++col) {
                if (row == 0 && col == 0) continue;
                else if (row == 0) grid[row][col] += grid[row][col - 1];
                else if (col == 0) grid[row][col] += grid[row - 1][col];
                else grid[row][col] += min(grid[row - 1][col], grid[row][col - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (row == 0 && col == 0) continue;
                else if (row == 0) grid[row][col] += grid[row][col - 1];
                else if (col == 0) grid[row][col] += grid[row - 1][col];
                else grid[row][col] += Math.min(grid[row - 1][col], grid[row][col - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for row in range(m):
            for col in range(n):
                if row == 0 and col == 0:
                    continue
                elif row == 0:
                    grid[row][col] += grid[row][col - 1]
                elif col == 0:
                    grid[row][col] += grid[row - 1][col]
                else:
                    grid[row][col] += min(grid[row - 1][col], grid[row][col - 1])
        return grid[m - 1][n - 1]