# Dynamic Path Sum in a Grid

##### February 25, 2024

## 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: #

- Initialize a 2D array
`dp`

with the same dimensions as the input grid to store the minimum path sum to reach each cell. - Set
`dp[0][0]`

to`grid[0][0]`

. - 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). - 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]`

. - 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.