Course contentsShow
← Computer Science
Lesson 941 of 2,87222. Dynamic ProgrammingFree lesson

Minimum Path Sum in Grid

Find path from top-left to bottom-right with minimum sum of values along the path.

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.