# Minimum Path Cost in a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-path-cost-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/minimum-path-cost-in-a-grid
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
---
## Problem
You are given a **0-indexed** `m x n` integer matrix `grid` consisting of **distinct** integers from `0` to `m * n - 1`. You can move in this matrix from a cell to any other cell in the **next** row. That is, if you are in cell `(x, y)` such that `x < m - 1`, you can move to any of the cells `(x + 1, 0)`, `(x + 1, 1)`, ..., `(x + 1, n - 1)`. **Note** that it is not possible to move from cells in the last row.

Each possible move has a cost given by a **0-indexed** 2D array `moveCost` of size `(m * n) x n`, where `moveCost[i][j]` is the cost of moving from a cell with value `i` to a cell in column `j` of the next row. The cost of moving from cells in the last row of `grid` can be ignored.

The cost of a path in `grid` is the **sum** of all values of cells visited plus the **sum** of costs of all the moves made. Return _the **minimum** cost of a path that starts from any cell in the **first** row and ends at any cell in the **last** row._

**Example 1:**

![](https://assets.glich.co/dsa/minimum-path-cost-in-a-grid/image0.png) 

**Input:** grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
**Output:** 17
**Explanation:** The path with the minimum possible cost is the path 5 -> 0 -> 1.
- The sum of the values of cells visited is 5 + 0 + 1 = 6.
- The cost of moving from 5 to 0 is 3.
- The cost of moving from 0 to 1 is 8.
So the total cost of the path is 6 + 3 + 8 = 17.

**Example 2:**

**Input:** grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
**Output:** 6
**Explanation:** The path with the minimum possible cost is the path 2 -> 3.
- The sum of the values of cells visited is 2 + 3 = 5.
- The cost of moving from 2 to 3 is 1.
So the total cost of this path is 5 + 1 = 6.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `2 <= m, n <= 50`
* `grid` consists of distinct integers from `0` to `m * n - 1`.
* `moveCost.length == m * n`
* `moveCost[i].length == n`
* `1 <= moveCost[i][j] <= 100`

# Approaches
## Bottom-Up Dynamic Programming
This problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. We can build a solution from the top row down to the bottom row. We define a 2D DP array, `dp[i][j]`, to store the minimum cost of a path that starts from any cell in the first row and ends at cell `(i, j)`. By systematically calculating these minimum costs for each cell row by row, we can eventually find the minimum cost to reach any cell in the last row.
**Time:** O(m * n * n). We iterate through each cell of the grid (m*n), and for each cell, we iterate through all n possible cells in the previous row to find the minimum transition cost. · **Space:** O(m * n) to store the DP table.
**Pros:** It's a conceptually straightforward implementation of the dynamic programming recurrence.; Guaranteed to find the optimal solution by exploring all possibilities in a structured manner.
**Cons:** The space complexity is O(m * n), which can be suboptimal for large grids, although it fits within the given constraints.
### Explanation
We use a 2D array `dp` of the same dimensions as `grid` to store our intermediate results. `dp[i][j]` will hold the minimum total cost to reach cell `(i, j)`.

**Initialization (Base Case):**
The paths start in the first row. The cost to reach a cell `(0, j)` in the first row is simply its own value, as there are no preceding moves or move costs. So, we initialize the first row of our `dp` table as follows:
`dp[0][j] = grid[0][j]` for all `j` from `0` to `n-1`.

**State Transition:**
For any subsequent row `i` (from `1` to `m-1`), the minimum cost to reach cell `(i, j)` is its own value `grid[i][j]` plus the minimum cost to get to this cell from the previous row `i-1`. To get to `(i, j)`, we could have come from any cell `(i-1, k)` where `0 <= k < n`. The cost of such a transition is the sum of three parts:
1. The minimum cost to reach the previous cell `(i-1, k)`, which is `dp[i-1][k]`.
2. The cost of the move from the cell with value `grid[i-1][k]` to column `j` in the next row, which is `moveCost[grid[i-1][k]][j]`.
3. The value of the current cell `grid[i][j]`.

We must find the minimum over all possible previous cells `k`.
`dp[i][j] = grid[i][j] + min_{0 <= k < n} (dp[i-1][k] + moveCost[grid[i-1][k]][j])`

**Final Answer:**
After filling the `dp` table up to the last row, `dp[m-1]` will contain the minimum costs for paths ending at each cell of that row. The overall minimum path cost is the minimum value in `dp[m-1]`.

```java
class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        // Initialize the first row of dp table
        for (int j = 0; j < n; j++) {
            dp[0][j] = grid[0][j];
        }

        // Fill the rest of the dp table
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int minPrevCost = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) {
                    // Cost to reach (i, j) from (i-1, k)
                    int cost = dp[i - 1][k] + moveCost[grid[i - 1][k]][j];
                    minPrevCost = Math.min(minPrevCost, cost);
                }
                dp[i][j] = grid[i][j] + minPrevCost;
            }
        }

        // Find the minimum cost in the last row
        int minTotalCost = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            minTotalCost = Math.min(minTotalCost, dp[m - 1][j]);
        }

        return minTotalCost;
    }
}
```
### Algorithm
- Create a 2D DP table `dp` of size `m x n`.
- **Base Case (Row 0):** Initialize the first row of the `dp` table. For each column `j`, `dp[0][j] = grid[0][j]`.
- **Transitions (Row 1 to m-1):** Iterate from the second row (`i = 1`) to the last row (`i = m-1`).
  - For each cell `(i, j)`:
    - Calculate the minimum cost to arrive at this cell from any cell `(i-1, k)` in the previous row.
    - The recurrence relation is: `dp[i][j] = grid[i][j] + min_{0 <= k < n} (dp[i-1][k] + moveCost[grid[i-1][k]][j])`.
- **Final Result:** After filling the entire `dp` table, find the minimum value in the last row, `dp[m-1]`. This value is the minimum path cost.

## Space-Optimized Dynamic Programming
This approach optimizes the space complexity of the standard bottom-up DP solution. We observe that to compute the minimum costs for the current row `i`, we only need the results from the immediately preceding row `i-1`. Information from earlier rows (`i-2`, `i-3`, etc.) is not required. This allows us to discard the full `m x n` DP table and instead use only two 1D arrays: one to store the costs of the previous row and one to compute the costs for the current row. This reduces the space complexity from O(m*n) to O(n).
**Time:** O(m * n * n). The time complexity remains the same as the unoptimized version, as the loop structure is identical. · **Space:** O(n). We only need to store the DP results for the previous and current rows, each requiring an array of size n.
**Pros:** Achieves optimal space complexity of O(n).; Maintains the same efficient time complexity as the standard DP approach.
**Cons:** The implementation is slightly more complex due to the need to manage and update the 1D DP arrays for each row.
### Explanation
Instead of a full `m x n` DP table, we can use just two 1D arrays, say `prevRowDp` and `currentRowDp`, both of size `n`. `prevRowDp` will store the minimum costs for the row we have just processed, and `currentRowDp` will be used to calculate the costs for the row we are currently processing.

**Initialization:**
We start by initializing `prevRowDp` with the values from the first row of the grid, as this is our base case.
`prevRowDp[j] = grid[0][j]` for `j` from `0` to `n-1`.

**State Transition:**
We then loop from the second row (`i = 1`) to the last row (`m-1`). In each iteration `i`, we compute the values for `currentRowDp`.
For each column `j`, the logic is the same as before, but we use `prevRowDp` instead of `dp[i-1]`:
`currentRowDp[j] = grid[i][j] + min_{0 <= k < n} (prevRowDp[k] + moveCost[grid[i-1][k]][j])`

After we have filled `currentRowDp` for all columns `j`, its values represent the minimum costs to reach each cell in row `i`. We then update `prevRowDp = currentRowDp` and proceed to the next row `i+1`.

**Final Answer:**
After the loop finishes, the final `prevRowDp` array will contain the minimum path costs ending at each cell of the last row. The minimum value in this array is our answer.

```java
class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length;
        int n = grid[0].length;
        
        int[] prevRowDp = new int[n];
        // Initialize with the first row of the grid
        for (int j = 0; j < n; j++) {
            prevRowDp[j] = grid[0][j];
        }

        // Iterate from the second row to the last
        for (int i = 1; i < m; i++) {
            int[] currentRowDp = new int[n];
            for (int j = 0; j < n; j++) {
                int minPrevCost = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) {
                    // Cost from previous row's cell k to current row's cell j
                    int cost = prevRowDp[k] + moveCost[grid[i - 1][k]][j];
                    minPrevCost = Math.min(minPrevCost, cost);
                }
                currentRowDp[j] = grid[i][j] + minPrevCost;
            }
            // The current row becomes the previous row for the next iteration
            prevRowDp = currentRowDp;
        }

        // Find the minimum cost in the last row's DP array
        int minTotalCost = Integer.MAX_VALUE;
        for (int cost : prevRowDp) {
            minTotalCost = Math.min(minTotalCost, cost);
        }

        return minTotalCost;
    }
}
```
### Algorithm
- Initialize a 1D array `dp` of size `n` with the values from the first row of the grid: `dp[j] = grid[0][j]`.
- Iterate from the second row (`i = 1`) to the last row (`i = m-1`).
  - In each iteration, create a new temporary 1D array `nextDp` of size `n`.
  - For each column `j` from `0` to `n-1`:
    - Calculate `nextDp[j]` using the values from the `dp` array (which represents the previous row's costs).
    - `nextDp[j] = grid[i][j] + min_{0 <= k < n} (dp[k] + moveCost[grid[i-1][k]][j])`.
  - After computing all values for `nextDp`, update `dp = nextDp` for the next iteration.
- **Final Result:** After the loops complete, the `dp` array holds the costs for the last row. The answer is the minimum value in this `dp` array.

# Solutions
### Java

```java
class Solution {
public
  int minPathCost(int[][] grid, int[][] moveCost) {
    int m = grid.length, n = grid[0].length;
    int[] f = grid[0];
    final int inf = 1 << 30;
    for (int i = 1; i < m; ++i) {
      int[] g = new int[n];
      Arrays.fill(g, inf);
      for (int j = 0; j < n; ++j) {
        for (int k = 0; k < n; ++k) {
          g[j] =
              Math.min(g[j], f[k] + moveCost[grid[i - 1][k]][j] + grid[i][j]);
        }
      }
      f = g;
    }
```

### CPP

```cpp
class Solution {
public:
  int minPathCost(vector<vector<int>> &grid, vector<vector<int>> &moveCost) {
    int m = grid.size(), n = grid[0].size();
    const int inf = 1 << 30;
    vector<int> f = grid[0];
    for (int i = 1; i < m; ++i) {
      vector<int> g(n, inf);
      for (int j = 0; j < n; ++j) {
        for (int k = 0; k < n; ++k) {
          g[j] = min(g[j], f[k] + moveCost[grid[i - 1][k]][j] + grid[i][j]);
        }
      }
      f = move(g);
    }
    return *min_element(f.begin(), f.end());
  }
};

```

### Python

```python
class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) f = grid[0] for i in range(1, m): g = [inf] * n for j in range(n): for k in range(n): g[j] = min(g[j], f[k] + moveCost[grid[i - 1][k]][j] + grid[i][j]) f = g return min(f)

```