Dynamic Path Sum in a Grid

Dynamic Path Sum in a Grid

February 25, 2024
medium
dynamic programming

Problem Statement: #

Given a m x n grid filled with non-negative integers, find a path from the top left corner to the bottom right corner which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time. Return the minimum path sum.

Example: #

  • Input:
grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
  • Output: 7
  • Explanation: The path that minimizes the sum is 1→3→1→1→1, which sums to 7.

Solution Approach: #

This problem can be efficiently solved using Dynamic Programming. The idea is to start from the top-left corner and calculate the minimum path sum to reach each cell in the grid by considering the minimum of the two possible paths to reach that cell (from the left or from the top).

Algorithm Steps: #

  1. Initialize a 2D array dp with the same dimensions as the input grid to store the minimum path sum to reach each cell.
  2. Set dp[0][0] to grid[0][0].
  3. For the first row and first column in dp, populate each cell with the sum of the current cell in grid and the previous cell in dp since there’s only one path to reach cells in these positions (either from the left or from the top).
  4. Iterate through the grid starting from cell (1, 1) and for each cell, calculate the minimum path sum to reach that cell as min(dp[i-1][j], dp[i][j-1]) + grid[i][j], and store it in dp[i][j].
  5. The minimum path sum to reach the bottom-right corner is stored in dp[m-1][n-1]. Return this value.

Code: # 

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0 for _ in range(n)] for _ in range(m)]
    
    dp[0][0] = grid[0][0]
    
    # Initialize first column of dp array
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
        
    # Initialize first row of dp array
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
        
    # Fill in the dp array
    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]

# Example usage
grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
print(minPathSum(grid))

Time Complexity: #

  • O(m * n): Each cell in the grid is visited exactly once, and for each cell, the computation is done in constant time.

Space Complexity: #

  • O(m * n): A 2D array dp of the same dimensions as the input grid is used for dynamic programming.