Minimum Path Sum - Python Solution

1. Introduction

"Minimum Path Sum" is a key problem in dynamic programming, often encountered in coding interviews. It involves finding the path through a grid that minimizes the sum of the values along the path. This problem is essential for understanding optimization in grid-based problems and introduces key concepts in dynamic programming.

Problem

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

2. Solution Steps

1. Use dynamic programming to store the minimum path sum at each cell.

2. Initialize the top-left cell with its own value, as it's the starting point.

3. Iterate through the grid, updating each cell with the minimum path sum to reach that cell.

4. A cell's minimum path sum is the value of the cell plus the minimum of the path sums to the cell directly above and to the left.

5. The value in the bottom-right cell will be the minimum path sum for the entire grid.

3. Code Program

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    for i in range(1, m):
        grid[i][0] += grid[i - 1][0]
    for j in range(1, n):
        grid[0][j] += grid[0][j - 1]

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

    return grid[m - 1][n - 1]

# Example Usage
print(minPathSum([[1,3,1],[1,5,1],[4,2,1]]))
print(minPathSum([[1,2,3],[4,5,6]]))

Output:

7
12

Explanation:

1. Grid Initialization: The first row and column of the grid are initialized with the cumulative sums, as these are the only paths to reach those cells.

2. Dynamic Programming Fill: Each cell's value is updated to be its value plus the minimum of the two possible paths leading to it (from above or from the left).

3. Iterative Solution: The grid is filled iteratively, considering each cell's value and the minimum path to reach it.

4. Optimal Path Calculation: The value in the bottom-right cell after filling the grid represents the minimum path sum.

5. Result: The function returns the minimum sum of a path from the top-left to the bottom-right corner.