2304. Minimum Path Cost in a Grid

Problem Description

In this LeetCode problem, you're presented with a unique puzzle that involves navigating a matrix called grid, which is of size m x n, where m represents the number of rows and n represents the number of columns. Each cell in the matrix contains a distinct integer value ranging from 0 to m * n - 1. Your goal is to find a path from the top row to the bottom row that minimizes the total cost of the path.

The path’s total cost consists of two parts:

1. The sum of the values of all cells that you visit on the path.
2. The sum of additional move costs for each step you take from one row to the next.

You're allowed to move from your current cell to any cell in the directly next row. However, you cannot make moves from cells in the last row as the path ends there.

To calculate the cost of moving to the next row, you're given a matrix called moveCost. This matrix has the dimensions of the number of distinct integers m * n by n, which means for every possible value in grid there is a corresponding row of move costs for each column in the next row.

The task is to compute the minimum cost of any such path starting from the first row and ending in the last row of the grid.

Intuition

The intuition behind the solution lies in dynamic programming. Since you can move to any cell in the next row, and each move has a cost based on the current cell's value and the column you’re moving to, this problem can naturally lead us to think about state and transition.

We define a state that represents the minimum cost of reaching a particular cell in the grid. The transition will be the action of moving from the current cell to any cell in the next row. To compute the state, we consider all possible cells in the previous row from which we can arrive at the current cell and choose the one with the minimum total cost (value of the cell plus move cost).

The solution approach systematically builds up the answer row by row:

1. Start with the first row, where the cost of reaching any cell is just the value of that cell.
2. For each row after the first, compute the minimum cost of reaching each cell by checking all possible preceding cells from the previous row and adding the corresponding move cost and cell value.
3. After computing the costs for the second-last row, the best path's cost will be the cell in this row with the lowest cost because there are no more moves needed to enter cells in the last row.
4. Since we’re allowed to take the path starting from any cell in the first row and ending in any cell in the last row, we consider all possibilities when calculating minimum costs.

In terms of implementation, the g list represents the minimum costs of reaching each cell in the current row based on the previous row's calculations stored in f. We iterate through each cell in the current row (j) and each cell in the previous row (k) to determine the minimum cost g[j] by considering the existing cost f[k], the additional move cost moveCost[grid[i - 1][k]][j], and the value of the current cell grid[i][j]. We continue this process until we reach the second-last row, after which we can find the minimum cost of the final path by taking the smallest value in f.

Note: inf represents infinity and is used to initialize the minimum costs such that any actual cost computed would be lesser than inf.

Learn more about Dynamic Programming patterns.

Solution Approach

To implement the proposed solution, we use a dynamic programming approach. Let's inspect the given Python code snippet more closely to understand how the algorithm operates step by step:

Firstly, we retrieve the dimensions of the grid using m, n = len(grid), len(grid[0]) to determine the number of rows (m) and columns (n).

We then initialize a list f with the values of the first row of the grid, as for the first row, the cost is simply the value of the cells themselves since no moves are yet made.

1f = grid[0]

Next, an outer loop runs from 1 to m-1 (not included), iterating over the rows of the grid. We skip row 0 because we've already initialized f with its values.

1for i in range(1, m):

Within this loop, we prepare a new list g with inf (infinity) to keep track of the minimum costs for the current row (i). Since we haven't calculated any costs yet, we set them to inf as a placeholder.

1g = [inf] * n

We then use two nested loops to consider every cell in the current row and every possible cell from which we could have reached it from the previous row, respectively.

1for j in range(n):
2    for k in range(n):

Inside the nested loops, we update g[j] for each cell in the current row (j). We calculate the potential cost of reaching g[j] from each cell k in the previous row. This cost includes:

• The previously calculated minimum cost to reach the cell k (f[k]).
• The move cost from the value of the cell in the previous row (grid[i - 1][k]) to the current column j (moveCost[grid[i - 1][k]][j]).
• The value of the current cell (grid[i][j]).

We take the minimum of the current value of g[j] and this newly calculated potential cost. This updates the g[j] with the lowest possible cost to reach that cell from the previous row.

1g[j] = min(g[j], f[k] + moveCost[grid[i - 1][k]][j] + grid[i][j])

After we have processed all cells for the current row, we assign the values of g to f to use in the calculation of the next row.

1f = g

After exiting the outer loop, we have calculated the minimum costs of reaching each cell in the second-last row. To find the minimum cost of the path from the first row down to the last row, we return the minimum value in f.

1return min(f)

This implementation clocks in at O(m*n^2) time complexity because for each of the m-1 rows, we are performing two nested loops that run n times respectively for calculating the costs.

The code thus combines principles of dynamic programming - including storing intermediate results (in f) and optimizing by considering previously made decisions - to efficiently solve the problem and avoid redundant calculations.

Example Walkthrough

Let's consider a small 2x3 grid example to illustrate the solution approach:

Assume our grid looks like this, representing the values of each cell:

1[
2    [1, 2, 3],
3    [4, 5, 6]
4]

And let's say our moveCost matrix is given as follows, where each row corresponds to move costs from a grid value to the next row's columns:

1[
2    [1, 1, 1],   // move costs from grid value 0
3    [2, 2, 2],   // move costs from grid value 1
4    [3, 3, 3],   // move costs from grid value 2
5    [4, 4, 4],   // move costs from grid value 3
6    [5, 5, 5],   // move costs from grid value 4
7    [6, 6, 6]    // move costs from grid value 5
8]

Following the solution approach:

Step 1: We start with the first row. The cost of reaching any cell in the first row is simply the value of that cell. Hence, f = [1, 2, 3].

Step 2: We now consider the second row. We initiate the new cost array g to store the minimum costs for each cell with [inf, inf, inf].

Step 3: We calculate the minimum cost of reaching each cell in the second row (row index 1) considering all cells from the first row.

When processing the second row:

• To reach the first cell (value 4) from the first row's cells, we calculate the following potentials:

  • First cell: f[0] + moveCost[1][0] + grid[1][0] = 1 + 2 + 4 = 7
  • Second cell: f[1] + moveCost[2][0] + grid[1][0] = 2 + 3 + 4 = 9
  • Third cell: f[2] + moveCost[3][0] + grid[1][0] = 3 + 4 + 4 = 11 We take the minimum of these, which is 7, so g[0] = 7.

• To reach the second cell (value 5) from the first row's cells, similar calculations yield:

  • First cell: f[0] + moveCost[1][1] + grid[1][1] = 1 + 2 + 5 = 8
  • Second cell: f[1] + moveCost[2][1] + grid[1][1] = 2 + 3 + 5 = 10
  • Third cell: f[2] + moveCost[3][1] + grid[1][1] = 3 + 4 + 5 = 12 The minimum cost is 8, so g[1] = 8.

• To reach the third cell (value 6) from the first row's cells, we get:

  • First cell: f[0] + moveCost[1][2] + grid[1][2] = 1 + 2 + 6 = 9
  • Second cell: f[1] + moveCost[2][2] + grid[1][2] = 2 + 3 + 6 = 11
  • Third cell: f[2] + moveCost[3][2] + grid[1][2] = 3 + 4 + 6 = 13 Here, the minimum cost is 9, so g[2] = 9.

Step 4: After completing the loop for row 1, we have g = [7, 8, 9]. We copy g to f for the next iteration.

Since we're at the last row, we stop and return the minimum value in f, which is the minimum total cost to reach the bottom of the grid considering the path and move costs.

The minimum of f is 7, so the minimum cost to get from top to bottom is 7.

Solution Implementation

Time and Space Complexity

The time complexity of the provided code can be analyzed by looking at the loops in the function minPathCost. We see that there are three nested loops. The outermost loop runs for m - 1 iterations, where m is the number of rows in grid. The two inner loops each run for n iterations, where n is the number of columns. The work inside the innermost loop consists of constant-time operations. Therefore, the time complexity is O((m - 1) * n * n), which simplifies to O(m * n^2).

The space complexity is impacted by the auxiliary space used. We have a list f initialized with the first row of grid, and a list g re-initialized for each of the m rows. Since each list contains n elements, and no other data structures grow with the size of the input, the space complexity is O(n).

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