Minimum Path Cost in a Grid

Minimum Path Cost in a Grid

What is this problem about?

The Minimum Path Cost in a Grid problem presents you with a 2D grid of integers and a move-cost matrix. You start in any cell of the first row and move to the last row, choosing cells in each row and paying both the cell value and the transition cost. The goal is to find the path with minimum total cost. This Minimum Path Cost in a Grid interview question is a beautiful blend of dynamic programming and matrix traversal.

Why is this asked in interviews?

Google asks this problem to test classical DP on grids with transition costs — a pattern that generalizes to routing, logistics, and game development. It validates that a candidate can define a DP state capturing both position and cost simultaneously, and correctly handle the move-cost matrix. The array, matrix, and dynamic programming interview pattern is core here, and the multi-dimensional state space tests structured thinking.

Algorithmic pattern used

The pattern is row-by-row dynamic programming. Define dp[j] as the minimum cost to reach column j in the current row. When transitioning from row i to row i+1, for each cell (i+1, col), try all possible source columns in row i: dp[col] + moveCost[grid[i][sourceCol]][col] + grid[i+1][col]. Update the DP table row by row. Final answer is min(dp[j]) after the last row.

Example explanation

Suppose a 3x3 grid:

Row 0: [5, 3, 2]
Row 1: [6, 1, 4]

Move costs are given per cell value. Starting from row 0, the cheapest path might be: pick value 2 at (0,2), then pay moveCost[2][1] to go to (1,1) with value 1. Total = 2 + moveCost[2][1] + 1. Compare all paths to find the global minimum.

Common mistakes candidates make

• Forgetting to add the current cell's value in addition to the transition cost.
• Using the wrong row's DP values (mixing current row and previous row in-place updates).
• Initializing DP for the first row incorrectly (it should just be the cell values themselves).
• Iterating transition costs in the wrong direction (from destination back to source).

Interview preparation tip

Grid DP problems require clear state definitions. Before coding, write out dp[i][j] = minimum cost to reach cell (i,j) and derive the recurrence explicitly. Always separate the initialization step (first row) from the transition step (subsequent rows). Practice similar problems where movement has an associated cost beyond just the destination cell value — they build the intuition for two-component cost modeling.