LeetCode 2304 - Minimum Path Cost in a Grid

The problem gives us a matrix called grid with m rows and n columns. Every cell contains a unique integer from 0 to m n - 1. We may start from any cell in the first row and move downward one row at a time until we reach the last row. The movement rule is very flexible.

leetcodemediumarraydynamic-programmingmatrix

LeetCode Problem 2304

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem gives us a matrix called grid with m rows and n columns. Every cell contains a unique integer from 0 to m * n - 1. We may start from any cell in the first row and move downward one row at a time until we reach the last row.

The movement rule is very flexible. If we are currently at position (r, c), we may move to any column in the next row, meaning from (r, c) we can move to (r + 1, 0), (r + 1, 1), and so on up to (r + 1, n - 1).

Each move has an additional cost. This cost is not based on coordinates, it is based on the value stored in the current cell and the destination column. Specifically:

  • Suppose the current cell contains value v
  • Suppose we move into column nextCol of the next row
  • Then the move cost is moveCost[v][nextCol]

The total path cost contains two components:

  1. The sum of all grid cell values visited
  2. The sum of all move costs between rows

We must compute the minimum possible total cost among all valid top-to-bottom paths.

The constraints are important because they tell us how large the search space can become:

  • m and n are each at most 50
  • The grid contains at most 2500 cells
  • From every cell we may branch into up to 50 possible next cells

A naive recursive exploration would potentially examine an exponential number of paths. Since each row transition multiplies the number of possibilities, brute force quickly becomes infeasible.

The problem guarantees that:

  • All grid values are distinct
  • Grid values range from 0 to m*n - 1
  • Every move cost lookup is valid
  • There are always at least two rows and two columns

Important edge cases include:

  • Very small grids such as 2 x 2
  • Situations where the cheapest next cell value is not part of the optimal path because move costs dominate
  • Cases where a large cell value is still optimal because it enables a very cheap transition later
  • Multiple paths producing similar intermediate costs

These observations strongly suggest a dynamic programming approach because the minimum cost to reach a state depends only on previously computed states.

Approaches

Brute Force Approach

The brute force solution tries every possible path from the first row to the last row.

Starting from each cell in the first row, we recursively explore all possible column choices in the next row. For every transition, we add:

  • The current cell value
  • The move cost
  • The future path cost

Eventually we reach the last row, where we add the final cell value and terminate the recursion.

This approach is correct because it explicitly checks every valid path and returns the minimum total cost.

However, it is far too slow. If there are n choices per row transition and m rows, then the number of paths is approximately:

$$n^{m-1}$$

With n = 50 and m = 50, this becomes astronomically large.

Optimal Dynamic Programming Approach

The key insight is that many paths overlap in subproblems.

Suppose we already know the minimum cost to reach every cell in row r. Then we can compute the minimum cost for every cell in row r + 1.

Define:

$$dp[r][c]$$

as the minimum cost to reach cell (r, c).

To transition into (r + 1, nextCol) from (r, c):

$$dp[r][c] + moveCost[grid[r][c]][nextCol] + grid[r+1][nextCol]$$

We take the minimum over all possible previous columns.

Since every state depends only on the previous row, dynamic programming efficiently avoids repeated computation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^(m-1)) O(m) Recursively explores every possible path
Optimal Dynamic Programming O(m * n²) O(n) Computes minimum cost row by row

Algorithm Walkthrough

  1. Let m be the number of rows and n be the number of columns.
  2. Create a DP array representing the minimum cost to reach each cell in the current row.

Initially, the first row costs are simply the grid values themselves because no moves have been made yet.

dp[c] = grid[0][c]
  1. Process rows one by one from top to bottom.
  2. For each new row, create a temporary array next_dp initialized with infinity.

This array will store the minimum cost to reach each column in the next row. 5. For every column c in the current row:

  • Let currentValue = grid[row][c]
  • The current accumulated cost is dp[c]
  1. Try moving from this cell into every column nextCol in the next row.

The new cost becomes:

$$dp[c] + moveCost[currentValue][nextCol] + grid[row+1][nextCol]$$ 7. Update:

next_dp[nextCol] = min(next_dp[nextCol], newCost)
  1. After processing all transitions for the current row, replace dp with next_dp.
  2. After processing the final row, the answer is the minimum value inside dp.

Why it works

The algorithm maintains the invariant that dp[c] always stores the minimum possible cost to reach column c in the current row.

Every valid path into the next row must come from some cell in the previous row. By checking all transitions and taking the minimum, we guarantee that the optimal substructure property holds. Since each state is computed from already optimal previous states, the final answer is globally optimal.

Python Solution

from typing import List

class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        dp = grid[0][:]

        for row in range(m - 1):
            next_dp = [float("inf")] * n

            for col in range(n):
                current_value = grid[row][col]
                current_cost = dp[col]

                for next_col in range(n):
                    total_cost = (
                        current_cost
                        + moveCost[current_value][next_col]
                        + grid[row + 1][next_col]
                    )

                    next_dp[next_col] = min(
                        next_dp[next_col],
                        total_cost
                    )

            dp = next_dp

        return min(dp)

The implementation begins by storing the dimensions of the grid. The dp array is initialized with the values from the first row because starting at a cell costs exactly the value of that cell.

For each row transition, a fresh next_dp array is created. Every element starts as infinity because we are searching for minimum costs.

The nested loops represent all possible transitions:

  • Current column in the current row
  • Destination column in the next row

For every transition, the algorithm computes the total accumulated path cost and updates the best known value for the destination column.

After processing all transitions from one row, dp is replaced with next_dp. This works because future rows only depend on the immediately previous row.

Finally, once all rows are processed, the minimum value in dp represents the cheapest path ending anywhere in the last row.

Go Solution

package main

import "math"

func minPathCost(grid [][]int, moveCost [][]int) int {
	m := len(grid)
	n := len(grid[0])

	dp := make([]int, n)

	for col := 0; col < n; col++ {
		dp[col] = grid[0][col]
	}

	for row := 0; row < m-1; row++ {
		nextDP := make([]int, n)

		for i := 0; i < n; i++ {
			nextDP[i] = math.MaxInt32
		}

		for col := 0; col < n; col++ {
			currentValue := grid[row][col]
			currentCost := dp[col]

			for nextCol := 0; nextCol < n; nextCol++ {
				totalCost := currentCost +
					moveCost[currentValue][nextCol] +
					grid[row+1][nextCol]

				if totalCost < nextDP[nextCol] {
					nextDP[nextCol] = totalCost
				}
			}
		}

		dp = nextDP
	}

	answer := dp[0]

	for i := 1; i < n; i++ {
		if dp[i] < answer {
			answer = dp[i]
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built in infinity value for integers, math.MaxInt32 is used to initialize the DP array with very large values.

Slices are used for dynamic arrays. The algorithm updates nextDP row by row and then reassigns dp = nextDP.

Integer overflow is not a concern here because the maximum possible path cost remains comfortably within 32 bit integer range under the given constraints.

Worked Examples

Example 1

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

moveCost =
[
  [9, 8],
  [1, 5],
  [10, 12],
  [18, 6],
  [2, 4],
  [14, 3]
]

Initial DP:

Column Cost
0 5
1 3

We now process transitions into row 1.

From value 5 at column 0

Destination Calculation Total
column 0 5 + 14 + 4 23
column 1 5 + 3 + 0 8

From value 3 at column 1

Destination Calculation Total
column 0 3 + 18 + 4 25
column 1 3 + 6 + 0 9

Updated DP:

Column Minimum Cost
0 23
1 8

Now process transitions into row 2.

From value 4 at column 0

Destination Calculation Total
column 0 23 + 2 + 2 27
column 1 23 + 4 + 1 28

From value 0 at column 1

Destination Calculation Total
column 0 8 + 9 + 2 19
column 1 8 + 8 + 1 17

Final DP:

Column Minimum Cost
0 19
1 17

Answer:

min(19, 17) = 17

Example 2

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

Initial DP:

Column Cost
0 5
1 1
2 2

Process transitions into the last row.

From value 5

Destination Total
4 14
0 8
3 10

From value 1

Destination Total
4 25
0 24
3 12

From value 2

Destination Total
4 27
0 9
3 6

Final DP:

Column Minimum Cost
0 9
1 8
2 6

Answer:

6

Complexity Analysis

Measure Complexity Explanation
Time O(m * n²) For each row transition, every column tries all next columns
Space O(n) Only the current and next DP rows are stored

The algorithm processes m - 1 row transitions. For each row, it iterates through all n current columns and all n next columns, resulting in O(n²) work per row.

The space optimization works because each DP row depends only on the immediately previous row, so storing the entire DP table is unnecessary.

Test Cases

from typing import List

class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        dp = grid[0][:]

        for row in range(m - 1):
            next_dp = [float("inf")] * n

            for col in range(n):
                current_value = grid[row][col]
                current_cost = dp[col]

                for next_col in range(n):
                    total_cost = (
                        current_cost
                        + moveCost[current_value][next_col]
                        + grid[row + 1][next_col]
                    )

                    next_dp[next_col] = min(next_dp[next_col], total_cost)

            dp = next_dp

        return min(dp)

solution = Solution()

# Example 1 from problem statement
assert solution.minPathCost(
    [[5, 3], [4, 0], [2, 1]],
    [[9, 8], [1, 5], [10, 12], [18, 6], [2, 4], [14, 3]]
) == 17

# Example 2 from problem statement
assert solution.minPathCost(
    [[5, 1, 2], [4, 0, 3]],
    [[12, 10, 15], [20, 23, 8], [21, 7, 1],
     [8, 1, 13], [9, 10, 25], [5, 3, 2]]
) == 6

# Smallest valid grid size
assert solution.minPathCost(
    [[0, 1], [2, 3]],
    [[1, 1], [1, 1], [1, 1], [1, 1]]
) == 4

# Path where move cost dominates cell values
assert solution.minPathCost(
    [[0, 1], [2, 3]],
    [[100, 1], [1, 100], [1, 1], [1, 1]]
) == 4

# Single optimal transition among many expensive ones
assert solution.minPathCost(
    [[2, 1, 0], [3, 4, 5]],
    [
        [1, 50, 50],
        [50, 1, 50],
        [50, 50, 1],
        [1, 1, 1],
        [1, 1, 1],
        [1, 1, 1]
    ]
) == 6

# Larger grid to stress multiple transitions
assert solution.minPathCost(
    [[0, 1, 2], [3, 4, 5], [6, 7, 8]],
    [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
        [1, 1, 1],
        [2, 2, 2],
        [3, 3, 3],
        [1, 1, 1],
        [1, 1, 1],
        [1, 1, 1]
    ]
) == 11

print("All test cases passed!")
Test Why
Example 1 Validates the official sample
Example 2 Confirms correct handling of a two row grid
Smallest valid grid Tests minimum constraint sizes
Move cost dominates Ensures transitions are considered properly
Single optimal transition Verifies global optimization
Larger grid Tests repeated DP transitions

Edge Cases

One important edge case is the smallest possible grid, where m = 2 and n = 2. In this situation there is only one row transition. Bugs often appear when implementations assume more rows exist or incorrectly initialize DP states. This implementation handles the case naturally because the loop runs exactly once and computes all valid transitions.

Another important case occurs when the smallest grid values do not produce the cheapest path. A greedy approach might incorrectly choose the smallest current cell value, but move costs can completely change the optimal decision. The DP solution correctly evaluates total accumulated cost, not just local choices.

A third edge case involves multiple paths converging into the same destination cell. A naive recursive solution may recompute the same state repeatedly, causing exponential runtime. The dynamic programming solution avoids this by storing the minimum known cost for every column in each row and reusing those computed values efficiently.