Optimal Path in a Grid

December 25, 2023

Problem #

You are given a grid filled with non-negative numbers. Find a path from the top left to the bottom right, which minimizes the sum of all numbers along its path.

Solution #

To solve this problem, a typical approach is to use dynamic programming. The idea is to create a 2D array (or modify the given grid in place, if mutation is acceptable) where each cell contains the minimum sum required to reach that cell from the top-left corner. You update each cell by choosing the minimum sum between the top and left neighbor, adding the current cell’s value.

Here’s a Python implementation for the problem:

def minPathSum(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])

    # Initialize the first row and first column
    for i in range(1, rows):
        grid[i][0] += grid[i - 1][0]
    for j in range(1, cols):
        grid[0][j] += grid[0][j - 1]

    # Compute the minimum path sum for the rest of the cells
    for i in range(1, rows):
        for j in range(1, cols):
            grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])

    return grid[rows - 1][cols - 1]

# Example Usage
grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print("Minimum path sum:", minPathSum(grid))

In this code:

• We first handle the edge cases where the grid is empty.
• We then initialize the first row and the first column of the grid, because each of these cells can only be reached from one direction.
• For each of the remaining cells, we calculate the minimum sum by considering the minimum of the top and left neighbors and adding the current cell’s value.
• The final answer, which is the minimum path sum to reach the bottom-right corner, will be in the last cell of the grid.

This approach ensures we consider all possible paths and select the minimum at each step, effectively applying dynamic programming. The time complexity of this algorithm is O(mn), where m is the number of rows and n is the number of columns in the grid.