Maximum Path Sum in a Grid

Maximum Path Sum in a Grid

January 25, 2024
medium
dynamic programming

Problem Statement #

Given a m x n grid filled with non-negative numbers, find a path from the top left to the bottom right corner, which maximizes the sum of the 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: 12 Explanation: The path 1 -> 3 -> 5 -> 1 -> 1 -> 1 maximizes the sum.

Solution Approach #

The solution involves using dynamic programming to calculate the maximum path sum at each cell, considering the optimal paths from the top and left cells.

Algorithm Steps #

  1. Create a DP matrix of the same size as the grid.
  2. Initialize the top-left cell of the DP matrix with the top-left cell of the grid.
  3. Fill the first row and first column of the DP matrix.
  4. For each cell in the grid, calculate the maximum sum by considering the top and left cells.
  5. The cell in the bottom-right corner of the DP matrix contains the maximum path sum.
  6. Return this value.

Code (Python) # 

def maxPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]

    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]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[-1][-1]

# Test the function
print(maxPathSum([[1,3,1], [1,5,1], [4,2,1]]))  # Output: 12

Time Complexity #

O(m*n), where m and n are the dimensions of the grid. Each cell is processed once.

Space Complexity #

O(m*n), for the DP matrix used to store the maximum sums.