Minimum Path Sum

Explanation & Solution

Description

Given an m x n grid filled with non-negative numbers, find a path from the top-left corner to the bottom-right corner that minimizes the sum of all numbers along its path.

You can only move either down or right at any point in time.

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

Output: 7

Explanation: The path 1 → 3 → 1 → 1 → 1 minimizes the sum to 7.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

Approach

Dynamic Programming pattern

1. Initialize the DP Table

Create a 2D array dp of the same dimensions as grid.
Set dp[0][0] = grid[0][0] since the starting cell cost is just its own value.

2. Fill the First Column

For each row i from 1 to m - 1, set dp[i][0] = dp[i - 1][0] + grid[i][0].
There is only one way to reach any cell in the first column: straight down from the top.

3. Fill the First Row

For each column j from 1 to n - 1, set dp[0][j] = dp[0][j - 1] + grid[0][j].
There is only one way to reach any cell in the first row: straight right from the left.

4. Fill the Rest of the DP Table

For each cell (i, j) where both i >= 1 and j >= 1, compute dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j].
Each cell can be reached from the cell above or the cell to the left. We take the minimum of those two paths and add the current cell's value.

5. Return the Result

The answer is dp[m - 1][n - 1], which holds the minimum path sum from top-left to bottom-right.

Key Insight

This is a classic 2D dynamic programming problem. The optimal substructure property holds because the minimum path to any cell depends only on the minimum paths to its top and left neighbors.

Time

O(m * n)we visit every cell exactly once.

Space

O(m * n) for the DP table (can be optimized to O(n) by reusing a single row).

Visualization

Input:

DFS Traversal3×3 grid

output—

Press play to start dfs traversal

CurrentQueuedVisitedSource

57 steps

Solution Code

Unique Paths

Longest Palindromic Substring