Problem Description

You have a grid with m rows and n columns containing distinct integers from 0 to m * n - 1. You need to find the minimum cost path from any cell in the first row to any cell in the last row.

Movement Rules:

• You can only move downward to the next row
• From cell (x, y), you can move to any cell in the next row: (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1)
• You cannot move from cells in the last row

Cost Calculation:

• Each cell has a value (the number in the grid at that position)
• Moving from one cell to another has an additional movement cost
• The movement cost is given by a 2D array moveCost where:
  • moveCost[i][j] is the cost of moving from a cell with value i to column j of the next row
• The total path cost = sum of all cell values visited + sum of all movement costs

Example: If you have a path that visits cells with values [a, b, c] and the movement costs are [cost1, cost2], then:

• Total path cost = a + b + c + cost1 + cost2

The goal is to find the path with the minimum total cost starting from any cell in the first row and ending at any cell in the last row.

Intuition

This is a classic dynamic programming problem because we need to find the optimal path and the problem has overlapping subproblems.

Think about it this way: to reach any cell in row i, we must have come from some cell in row i-1. The key insight is that the minimum cost to reach a cell (i, j) depends only on the minimum costs to reach cells in the previous row.

Why? Because once we know the minimum cost to reach each cell in row i-1, we can calculate the minimum cost to reach any cell in row i by trying all possible moves from row i-1 and picking the cheapest option.

For each cell (i, j), we need to consider:

• Which cell in the previous row should we come from?
• We could come from any column k in row i-1
• The cost would be: (minimum cost to reach (i-1, k)) + (movement cost from that cell to (i, j)) + (value of cell (i, j))

This naturally leads to a dynamic programming solution where:

• f[i][j] = minimum cost to reach cell (i, j) from the first row
• We build up the solution row by row
• For each cell, we try all possible previous cells and take the minimum

Since we only need information from the previous row to calculate the current row, we can optimize space by using a rolling array - just keeping track of the costs for the previous row instead of the entire grid.

The final answer is the minimum value among all cells in the last row, since we can end at any cell in the last row.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the dynamic programming solution using a space-optimized approach with a rolling array.

Step 1: Initialize the DP array

• Start with f = grid[0], which represents the minimum costs to reach each cell in the first row
• These costs are just the cell values themselves since there's no movement cost to reach the first row

Step 2: Process each row iteratively For each row i from 1 to m-1:

• Create a new array g of size n initialized with infinity to store the minimum costs for the current row
• For each cell (i, j) in the current row:
  • Try all possible previous cells (i-1, k) where k ranges from 0 to n-1
  • Calculate the cost: f[k] + moveCost[grid[i-1][k]][j] + grid[i][j]
    • f[k]: minimum cost to reach cell (i-1, k)
    • moveCost[grid[i-1][k]][j]: cost to move from cell with value grid[i-1][k] to column j
    • grid[i][j]: value of the current cell
  • Update g[j] with the minimum cost found

Step 3: Update the rolling array

• After processing all cells in row i, update f = g
• This makes f now represent the minimum costs for the current row, ready for the next iteration

Step 4: Return the result

• After processing all rows, f contains the minimum costs to reach each cell in the last row
• Return min(f) to get the overall minimum path cost

State Transition Formula:

f[i][j] = min{f[i-1][k] + moveCost[grid[i-1][k]][j] + grid[i][j]} for all k in [0, n-1]

Time Complexity: O(m × n²) - For each of the m×n cells, we check n possible previous cells

Space Complexity: O(n) - We only maintain arrays for the current and previous rows

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• Grid (3×3):

[5, 3, 2]
[1, 7, 8]
[4, 6, 9]

• Movement costs (moveCost[value][column]):

moveCost[5][0]=1, moveCost[5][1]=2, moveCost[5][2]=3
moveCost[3][0]=4, moveCost[3][1]=1, moveCost[3][2]=2
moveCost[2][0]=2, moveCost[2][1]=3, moveCost[2][2]=1
moveCost[1][0]=3, moveCost[1][1]=2, moveCost[1][2]=1
moveCost[7][0]=1, moveCost[7][1]=3, moveCost[7][2]=2
moveCost[8][0]=2, moveCost[8][1]=1, moveCost[8][2]=3

Step 1: Initialize

• f = [5, 3, 2] (costs to reach first row cells are just their values)

Step 2: Process Row 1 Calculate minimum cost to reach each cell in row 1:

For cell (1,0) with value 1:

• From (0,0): cost = 5 + moveCost[5][0] + 1 = 5 + 1 + 1 = 7
• From (0,1): cost = 3 + moveCost[3][0] + 1 = 3 + 4 + 1 = 8
• From (0,2): cost = 2 + moveCost[2][0] + 1 = 2 + 2 + 1 = 5
• Minimum: g[0] = 5

For cell (1,1) with value 7:

• From (0,0): cost = 5 + moveCost[5][1] + 7 = 5 + 2 + 7 = 14
• From (0,1): cost = 3 + moveCost[3][1] + 7 = 3 + 1 + 7 = 11
• From (0,2): cost = 2 + moveCost[2][1] + 7 = 2 + 3 + 7 = 12
• Minimum: g[1] = 11

For cell (1,2) with value 8:

• From (0,0): cost = 5 + moveCost[5][2] + 8 = 5 + 3 + 8 = 16
• From (0,1): cost = 3 + moveCost[3][2] + 8 = 3 + 2 + 8 = 13
• From (0,2): cost = 2 + moveCost[2][2] + 8 = 2 + 1 + 8 = 11
• Minimum: g[2] = 11

Update: f = [5, 11, 11]

Step 3: Process Row 2 Calculate minimum cost to reach each cell in row 2:

For cell (2,0) with value 4:

• From (1,0): cost = 5 + moveCost[1][0] + 4 = 5 + 3 + 4 = 12
• From (1,1): cost = 11 + moveCost[7][0] + 4 = 11 + 1 + 4 = 16
• From (1,2): cost = 11 + moveCost[8][0] + 4 = 11 + 2 + 4 = 17
• Minimum: g[0] = 12

For cell (2,1) with value 6:

• From (1,0): cost = 5 + moveCost[1][1] + 6 = 5 + 2 + 6 = 13
• From (1,1): cost = 11 + moveCost[7][1] + 6 = 11 + 3 + 6 = 20
• From (1,2): cost = 11 + moveCost[8][1] + 6 = 11 + 1 + 6 = 18
• Minimum: g[1] = 13

For cell (2,2) with value 9:

• From (1,0): cost = 5 + moveCost[1][2] + 9 = 5 + 1 + 9 = 15
• From (1,1): cost = 11 + moveCost[7][2] + 9 = 11 + 2 + 9 = 22
• From (1,2): cost = 11 + moveCost[8][2] + 9 = 11 + 3 + 9 = 23
• Minimum: g[2] = 15

Final: f = [12, 13, 15]

Step 4: Return Result The minimum cost path is min(12, 13, 15) = 12

The optimal path is: (0,2) → (1,0) → (2,0) with total cost 12.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n²)

The code contains three nested loops:

• The outer loop runs m-1 times (from row 1 to row m-1)
• The middle loop runs n times (for each column j in the current row)
• The inner loop runs n times (for each column k in the previous row)

For each iteration of the three loops, we perform constant time operations: accessing array elements, computing the minimum, and addition. Therefore, the total time complexity is O((m-1) × n × n) = O(m × n²).

Space Complexity: O(n)

The space complexity is determined by the additional space used:

• Array f stores the minimum costs for the previous row, using O(n) space
• Array g stores the minimum costs for the current row, using O(n) space

Since we only maintain two arrays of size n at any time (reusing them by reassigning f = g), the total space complexity is O(n). The input arrays grid and moveCost are not counted in the space complexity analysis as they are given inputs.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Movement Cost Indexing

The Problem: A frequent mistake is using the wrong indices when accessing the movement cost array. Developers often confuse:

• Using row/column indices directly instead of cell values
• Using the destination cell's value instead of the source cell's value

Incorrect Implementation:

# WRONG: Using row/column indices
cost = dp[prev_col] + moveCost[current_row - 1][current_col] + grid[current_row][current_col]

# WRONG: Using destination cell value
cost = dp[prev_col] + moveCost[grid[current_row][current_col]][current_col] + grid[current_row][current_col]

Correct Implementation:

# CORRECT: Use the VALUE of the source cell as the first index
cost = dp[prev_col] + moveCost[grid[current_row - 1][prev_col]][current_col] + grid[current_row][current_col]

Pitfall 2: Forgetting to Include Cell Values in Path Cost

The Problem: Another common error is calculating only the movement costs without including the actual cell values in the total path cost. The problem requires both the sum of cell values AND movement costs.

Incorrect Implementation:

# WRONG: Only considering movement costs
cost = dp[prev_col] + moveCost[grid[current_row - 1][prev_col]][current_col]

Correct Implementation:

# CORRECT: Include both movement cost and current cell value
cost = dp[prev_col] + moveCost[grid[current_row - 1][prev_col]][current_col] + grid[current_row][current_col]

Pitfall 3: Improper DP Initialization

The Problem: Failing to properly initialize the DP array for the first row. Since there's no movement cost to reach the first row, the initial costs should be just the cell values themselves.

Incorrect Implementation:

# WRONG: Initializing with zeros
dp = [0] * cols

# WRONG: Initializing with infinity
dp = [float('inf')] * cols

Correct Implementation:

# CORRECT: Initialize with first row values
dp = grid[0]  # or dp = grid[0].copy() if you want to be explicit

Complete Corrected Solution:

class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
      
        # Initialize with first row values (no movement cost to reach first row)
        dp = grid[0].copy()
      
        for current_row in range(1, rows):
            new_dp = [float('inf')] * cols
          
            for current_col in range(cols):
                for prev_col in range(cols):
                    # Correct indexing: moveCost[cell_value][destination_column]
                    source_value = grid[current_row - 1][prev_col]
                    movement_cost = moveCost[source_value][current_col]
                    current_cell_value = grid[current_row][current_col]
                  
                    # Total cost includes: previous path cost + movement cost + current cell value
                    total_cost = dp[prev_col] + movement_cost + current_cell_value
                    new_dp[current_col] = min(new_dp[current_col], total_cost)
          
            dp = new_dp
      
        return min(dp)