Minimum Path Sum | Leetcode 64 | All 4 DP Solutions

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.

Here’s the [Problem Link] to begin with.

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

Approach 1: Recursion (Brute Force)

Intuition

Imagine you need to get to a particular cell (i, j). There are only two ways:

• Coming from above (i-1, j)
• Coming from left (i, j-1)

So, for each cell, the minimum path sum is its own value plus the minimum path sum to either its top or left neighbor. Keep repeating this logic till you reach the top-left cell (base case), which is the start. If you move out of the grid (i.e., i < 0 or j < 0), return infinity so as not to consider invalid paths.

This approach explores all possible down and right paths recursively, always aggregating the minimum sum.

Detailed Steps

• Base case: When you reach the starting cell (0, 0), just return its value (grid).
• Out of bounds: Return infinity if i < 0 or j < 0.
• Recursive step: For every cell (i, j), compute:
  • up = solve(i-1, j, grid)
  • left = solve(i, j-1, grid)
  • The answer for (i, j) is grid[i][j] + min(up, left)

Code (with comments)

class Solution:
    def solve(self, i, j, grid):
        # Base case: reached start of grid
        if i == 0 and j == 0:
            return grid[0][0]
        # Out of grid bounds: not allowed, return infinity
        if i < 0 or j < 0:
            return float("inf")
        # Path sum if coming from above
        up = self.solve(i - 1, j, grid)
        # Path sum if coming from left
        left = self.solve(i, j - 1, grid)
        # Current cell's value plus minimum path from above or left
        return grid[i][j] + min(up, left)

    def minPathSum(self, grid: List[List[int]]) -> int:
        r = len(grid)
        c = len(grid[0])
        # Start from bottom-right cell (goal)
        return self.solve(r - 1, c - 1, grid)

Code Explanation

Recursively explores every possible path to the bottom-right, always trying both directions and returning the minimum sum. It uses infinity to block off-going moves out of the grid, so only valid paths count.

Time and Space Complexity

• Time: O(2^(m+n))
  Each cell can branch into up to two recursive calls (up and left), forming an exponential tree.
• Space: O(m + n)
  The recursion stack depth is at most m + n (the path length).

Simplified: Exponential time and linear space (not practical for large grids).

Approach 2: Memoization (Top-Down DP)

Intuition

The brute force recursion repeats much work, subpaths to the same cell from different directions are computed over and over. Memoization fixes this by storing the minimum path sum for each (i, j) in a DP array the first time it’s computed, then looking it up for every subsequent request.

Detailed Steps

• Use a 2D array dp initialized to -1.
• If dp[i][j] is already computed (not -1), just return it, no need to recalculate.
• Otherwise, compute it as in recursion, store, and return.

Code (with comments)

class Solution:
    def solve(self, i, j, grid, dp):
        # Base case: starting cell
        if i == 0 and j == 0:
            return grid[0][0]
        # Out of bounds, treat as infinite sum so won't be chosen
        if i < 0 or j < 0:
            return float("inf")
        # If already computed, reuse
        if dp[i][j] != -1:
            return dp[i][j]
        # Try coming from above and left
        up = self.solve(i - 1, j, grid, dp)
        left = self.solve(i, j - 1, grid, dp)
        # Record and return minimum path sum to (i, j)
        dp[i][j] = grid[i][j] + min(up, left)
        return dp[i][j]

    def minPathSum(self, grid: List[List[int]]) -> int:
        r = len(grid)
        c = len(grid[0])
        dp = [[-1 for _ in range(c)] for _ in range(r)]
        return self.solve(r - 1, c - 1, grid, dp)

Code Explanation

Adds a 2D DP matrix to cache results per cell. Whenever a subproblem (cell (i, j)) is solved, its answer is stored for fast future lookups, eliminating redundant computation.

Time and Space Complexity

• Time: O(r * c)
  Each cell is solved only once, so total number of subproblems = number of cells.
• Space: O(r * c) (DP array) + O(r + c) (recursion stack).

Simplified: Linear in grid size O(r * c) for both time and space.

Approach 3: Tabulation (Bottom-Up DP)

Intuition

Instead of recursion, tabulation builds up the answer iteratively from the start, using a 2D DP table.
At each cell (i, j), the minimum path sum is its own value plus the minimum of:

• The cell above (dp[i-1][j])
• The cell to the left (dp[i][j-1])

Handle the first row and column carefully, as they only have one direction available (left or up).

Detailed Steps

• Set dp = grid
• For all cells (i, j), fill the value from top and left neighbors
• Use float("inf") for out-of-bounds neighbors
• Final result is dp[r-1][c-1]

Code (with comments)

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        r = len(grid)
        c = len(grid[0])
        dp = [[-1 for _ in range(c)] for _ in range(r)]
        dp[0][0] = grid[0][0]  # Start cell
        for i in range(0, r):
            for j in range(0, c):
                if i == 0 and j == 0:
                    continue  # Skip start cell
                # If no row above, set up = inf; else, use value above
                if i == 0:
                    up = float("inf")
                else:
                    up = dp[i - 1][j]
                # If no col to left, set left = inf; else, use value to left
                if j == 0:
                    left = float("inf")
                else:
                    left = dp[i][j - 1]
                # Current cell = its value + min path sum from up or left
                dp[i][j] = grid[i][j] + min(up, left)
        return dp[r - 1][c - 1]

Code Explanation

A DP grid is built row by row, always adding the grid value to the minimum from the previous row or column. Edges are handled using infinity to avoid picking out-of-bounds sums.

Time and Space Complexity

• Time: O(r * c)
  Each grid cell is filled exactly once.
• Space: O(r * c)
  Due to the 2D DP table.

Simplified: Linear in the grid size for both time and space.

Approach 4: Tabulation (Space Optimization)

Intuition

At any step, to fill the value for the current cell, we only need:

• The value directly to the left (in the current row)
• The value right above (from the previous row)

This means we can store results for a single previous row (and the current row we’re computing) rather than the whole matrix, reducing the space from O(r * c) to O(c).

Detailed Steps

• Use two 1D arrays: prev (previous row) and curr (current row).
• For each row, build curr left-to-right using only prev and itself.
• After each row, update prev = curr.

Code (with comments)

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        r = len(grid)
        c = len(grid[0])
        prev = [0] * c  # Previous row's DP
        for i in range(0, r):
            curr = [0] * c  # Current row's DP
            for j in range(0, c):
                # Start cell
                if i == 0 and j == 0:
                    curr[0] = grid[0][0]
                    continue
                # Value from the cell above (prev row, same col)
                if i == 0:
                    up = float("inf")
                else:
                    up = prev[j]
                # Value from the left (current row, prev col)
                if j == 0:
                    left = float("inf")
                else:
                    left = curr[j - 1]
                curr[j] = grid[i][j] + min(up, left)
            prev = curr  # Move current row to prev
        return prev[c - 1]  # Last cell of last row

Code Explanation

Uses only two arrays to capture the rolling DP values, significantly reducing space without loss of clarity or correctness.

Time and Space Complexity

• Time: O(r * c)
  Every element visited once.
• Space: O(1)
  Only two rows of data are ever kept at once.

Simplified: Time O(r * c), Space O(c), optimal for big grids.

Summary Table

Conclusion

“Minimum Path Sum” is a fundamental grid DP problem. Mastering all these approaches builds up both your coding skill and your DP intuition. Start with recursion for the concept, then use memoization or iterative tabulation, and for large grids, always remember to optimize your space. Keep practicing, and soon you’ll be confident with any grid-based dynamic programming challenge!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.