Minimum Path Sum in Grid
You'll learn how to find the cheapest route through a grid where each cell has a cost.
Imagine you're navigating through a city grid where each intersection has a toll fee. You start at the top-left corner (your home) and need to reach the bottom-right corner (your destination). You can only move right or down—no backtracking. Your goal: minimize the total toll paid along your path.
The Core Idea
This is a classic dynamic programming problem building directly on "Unique Paths in Grid." Instead of just counting paths, we now care about the cost of each path. Each grid cell contains a number (its cost), and we want the path from grid[0][0] to grid[m-1][n-1] with the minimum sum of values.
The key insight: to reach any cell (i, j) with minimum cost, you must have come from either:
- The cell above
(i-1, j), or - The cell to the left
(i, j-1)
You pick whichever of those two had the smaller cumulative cost, then add the current cell's value.
The DP State
State definition: dp[i][j] = minimum path sum to reach cell (i, j)
Transition: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
Base case: dp[0][0] = grid[0][0] (starting point has no previous cells)
For cells in the first row or column, you can only arrive from one direction, so initialize accordingly.
Key Takeaway: Minimum Path Sum uses DP to build up the cheapest route cell-by-cell, choosing at each step whether coming from above or from the left costs less.