Introduction

The Minimum Path Sum problem is a classic 2D Dynamic Programming question.

You are given a grid where each cell contains a cost.

Goal:

Reach the bottom-right cell with the minimum possible path sum.

Allowed Moves:

Move Right or Move Down

Example

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

Output:

 7

Path:

1 → 3 → 1 → 1 → 1

Sum:

7

Key Observation

To reach cell:

(i,j)

We can come from:

Top Cell (i-1,j) or Left Cell (i,j-1)

Recurrence:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Approach 1 : Memoization

Explanation

Use recursion and store already calculated results.

Steps:

  1. Solve smaller subproblems.
  2. Store answers.
  3. Reuse stored values.
  4. Avoid repeated calculations.

Approach 2 : Tabulation

Explanation

Build a DP table from top-left to bottom-right.

Base Case:

dp[0][0] = grid[0][0]

Transition:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Dry Run

Input:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

DP Table:

1 4 5
2 7 6
6 8 7

Answer:

7

Approach 3 : Space Optimized DP

Explanation

Instead of storing the entire matrix:

m × n

Store only one row.

This reduces memory usage.

Practice

Complexity Analysis

Memoization
Time Complexity: O(m × n)
Space Complexity: O(m × n)

Tabulation
Time Complexity: O(m × n)
Space Complexity: O(m × n)

Space Optimized DP
Time Complexity: O(m × n)
Space Complexity: O(n)

Why This Problem is Important

  • 2D Dynamic Programming
  • Grid Traversal
  • Cost Optimization
  • State Transition
  • Space Optimization

Common Beginner Mistakes

  • Wrong base cases
  • Incorrect first row initialization
  • Incorrect first column initialization
  • Using max instead of min
  • Forgetting bounds checks

Interview Tip

Always explain:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Meaning:

Current Cell Cost = Current Value + Minimum(Top Path, Left Path)

Related Questions

  • Unique Paths
  • Unique Paths II
  • Dungeon Game
  • Cherry Pickup
  • Edit Distance

Final Takeaway

Minimum Path Sum is one of the most important 2D Dynamic Programming problems.

It teaches:

  • Grid DP
  • Cost Optimization
  • State Transitions
  • Space Optimization

Mastering this problem makes advanced matrix-based Dynamic Programming questions much easier to solve.