💻 Minimum Cost Path in Grid (Right/Down Only)

Master dynamic programming to traverse the cost grid efficiently — find the cheapest path from start to end using only right and down moves!

🗺️ The Budget Traveler's Route

🎯 The Challenge:

You are given a 2D grid of size R x C where each cell contains a cost to enter. Calculate the minimum cost to reach the bottom-right cell (R-1, C-1) from the top-left cell (0, 0). You can only move right or down from a cell.

Problem Specifications

  • Input: First line: R C (1 ≤ R, C ≤ 1000). Next R lines: C integers (0 ≤ Cost[i][j] ≤ 10^4).
  • Output: Single integer: Minimum cost to (R-1, C-1).

Example: Input 1

3 3
1 2 3
4 8 2
1 5 3

Output: 11 (path: 1→2→2→3)

Example: Input 2

2 2
1 2
4 3

Output: 6 (path: 1→2→3)

🔄 Dynamic Programming Strategy

Key Idea

  1. dp[i][j] = minimum cost to reach (i,j) from (0,0).
  2. Base: dp[0][0] = grid[0][0].
  3. First row: dp[0][j] = dp[0][j-1] + grid[0][j] (only right).
  4. First col: dp[i][0] = dp[i-1][0] + grid[i][0] (only down).
  5. Inner: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

Note: Fill row-by-row. Result: dp[R-1][C-1].

DP Fill

Time: O(R * C)

Recursion (Naive)

O(2^(R+C)) — exponential

🔍 Step-by-Step DP Demo

Ready. Use controls below to start demo.

Cost Grid

DP Table State (min cost to cell)

Min cost will appear here

Progress Tracker

1. Set dp[0][0] = grid[0][0]
2. Fill first row (cumulative right)
3. Fill first column (cumulative down)
4. For inner cells: grid[i][j] + min(up, left)
5. Proceed row-by-row, left-to-right
6. Result at dp[R-1][C-1]

🎮 Build Your Min Cost Path Calculator

Enter R, C, grid and press Compute

Examples

3x3 Sample 1
→ 11
2x2 Sample 2
→ 6

📊 Analysis & Optimization

Time

O(R * C)

Single pass over grid.

Space

O(R * C)

DP table; optimizable to O(C).

Optimization Ideas

  • Modify grid in-place to save space (dp[i][j] = grid[i][j] + min...).
  • For R>>C, use 1D array of size C, update per row.
  • In C++, fast input with std::ios::sync_with_stdio(false) for 1000x1000.