Minimum Path Sum medium

Problem Statement

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.

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

Steps

1. Initialization: Create a DP table (matrix) of the same size as the input grid, initialized with all values set to infinity except for the top-left cell which is set to the value of the top-left cell in the grid.

2. Iteration: Iterate through the DP table. For each cell (i, j), update its value by taking the minimum of:

   • The value of the cell above it (i-1, j) plus the grid value at (i, j)
   • The value of the cell to its left (i, j-1) plus the grid value at (i, j)

3. Base Cases: The top row and leftmost column are handled specially. The top row's values are cumulatively summed from left to right. The leftmost column's values are cumulatively summed from top to bottom.

4. Result: The bottom-right cell of the DP table will contain the minimum path sum.

Explanation

This problem can be solved efficiently using dynamic programming. The key idea is that the minimum path sum to reach a cell (i, j) is the minimum of the minimum path sums to reach (i-1, j) and (i, j-1), plus the value of the cell (i, j) itself. By iteratively calculating these minimum path sums, we avoid redundant computations and find the optimal solution. The DP table stores the minimum path sum to reach each cell.

Code

def minPathSum(grid):
    """
    Finds the minimum path sum in a grid using dynamic programming.

    Args:
        grid: A list of lists representing the grid of numbers.

    Returns:
        The minimum path sum from top-left to bottom-right.
    """

    m = len(grid)
    n = len(grid[0])

    # Initialize DP table
    dp = [[float('inf')] * n for _ in range(m)]
    dp[0][0] = grid[0][0]


    # Initialize first row and column
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    # Iterate and update DP table
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

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

Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the grid. We iterate through the DP table once.
• Space Complexity: O(m*n), due to the DP table. We could optimize this to O(min(m,n)) by using only one row or column of the DP table if space is a major concern, but it would make the code a bit more complex.