Path with Maximum Sum

Dynamic programming (DP) is a powerful technique used to solve complex problems by breaking them down into simpler subproblems. One of the fascinating challenges within this domain is the "Path with Maximum Sum." This involves finding the most profitable route through a grid from the top-left corner to the bottom-right corner, where each cell in the grid contains a certain integer value.

Understanding the Problem

Given a 2D grid filled with integers, our goal is to find a path that maximizes the sum of its values. Moving can only occur downwards or rightwards, meaning you can progress to an adjacent cell in the row below or the next cell in the same row.

Let’s illustrate this with a simple example:

For the above grid, one optimal path is 1 → 2 → 5 → 8 → 9, which gives us a sum of 25.

Dynamic Programming Approach

To solve this problem, dynamic programming can be utilized to build a solution that optimally calculates the maximum sum at each cell based on its predecessors. Here’s a step-by-step explanation of how to implement this:

Step 1: Initialization

We will create a 2D array dp where dp[i][j] represents the maximum sum that can be achieved to reach cell (i, j) in the grid. The dimensions of dp will be the same as the grid.

Step 2: Base Case

The value at our starting point (dp[0][0]) will be equal to grid[0][0] since that’s where we begin our path.

Step 3: Fill in the first row and first column

Since we can only move right on the first row and down on the first column, we can fill these out easily.

For the first row: dp[0][j] = dp[0][j-1] + grid[0][j]
For the first column: dp[i][0] = dp[i-1][0] + grid[i][0]

Step 4: Fill in the rest of the `dp` table

For each cell (i, j), the maximum sum will be the maximum of the two possible preceding cells:

From the left: dp[i][j-1]
From above: dp[i-1][j]

Thus, we can express our relationship as:


dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

Step 5: The Final Result

The maximum sum path will ultimately be stored in dp[m-1][n-1], where m and n are the dimensions of the grid.

Implementation

Here is how you can implement the above approach in Python:


def maxPathSum(grid):
    if not grid:
        return 0

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

    dp[0][0] = grid[0][0]

    # Fill the first row
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    # Fill the first column
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]

    # Fill the rest of the dp table
    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[m-1][n-1]

# Example usage
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(maxPathSum(grid))  # Output: 25

Time Complexity and Space Complexity

Time Complexity: O(m*n), where m is the number of rows and n is the number of columns in the grid. We have to visit each cell once.
Space Complexity: O(m*n) for the dp table. However, we can optimize space to O(n) if we only keep track of the current and previous rows.

By using this dynamic programming technique, you can effectively tackle the "Path with Maximum Sum" problem and similar pathfinding challenges! Happy coding!