Code Implementation

from heapq import heappush, heappop

class Solution:
    def minPathCost(self, grid, moveCost):
        m, n = len(grid), len(grid[0])
        # dp[r][c] = min cost to reach (r, c)
        dp = [[float('inf')] * n for _ in range(m)]
        for c in range(n):
            dp[0][c] = grid[0][c]
        for r in range(1, m):
            for c in range(n):
                for prev_c in range(n):
                    prev_val = grid[r-1][prev_c]
                    cost = dp[r-1][prev_c] + moveCost[prev_val][c] + grid[r][c]
                    if cost < dp[r][c]:
                        dp[r][c] = cost
        return min(dp[-1])
      

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        for (int c = 0; c < n; ++c)
            dp[0][c] = grid[0][c];
        for (int r = 1; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                for (int prev_c = 0; prev_c < n; ++prev_c) {
                    int prev_val = grid[r-1][prev_c];
                    int cost = dp[r-1][prev_c] + moveCost[prev_val][c] + grid[r][c];
                    if (cost < dp[r][c])
                        dp[r][c] = cost;
                }
            }
        }
        return *min_element(dp[m-1].begin(), dp[m-1].end());
    }
};
      

class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int[] row : dp)
            java.util.Arrays.fill(row, Integer.MAX_VALUE);
        for (int c = 0; c < n; ++c)
            dp[0][c] = grid[0][c];
        for (int r = 1; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                for (int prev_c = 0; prev_c < n; ++prev_c) {
                    int prev_val = grid[r-1][prev_c];
                    int cost = dp[r-1][prev_c] + moveCost[prev_val][c] + grid[r][c];
                    if (cost < dp[r][c])
                        dp[r][c] = cost;
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int c = 0; c < n; ++c)
            res = Math.min(res, dp[m-1][c]);
        return res;
    }
}
      

var minPathCost = function(grid, moveCost) {
    const m = grid.length, n = grid[0].length;
    const dp = Array.from({length: m}, () => Array(n).fill(Infinity));
    for (let c = 0; c < n; ++c)
        dp[0][c] = grid[0][c];
    for (let r = 1; r < m; ++r) {
        for (let c = 0; c < n; ++c) {
            for (let prev_c = 0; prev_c < n; ++prev_c) {
                const prev_val = grid[r-1][prev_c];
                const cost = dp[r-1][prev_c] + moveCost[prev_val][c] + grid[r][c];
                if (cost < dp[r][c])
                    dp[r][c] = cost;
            }
        }
    }
    return Math.min(...dp[m-1]);
};
      

Problem Description

You are given a 2D integer array grid with m rows and n columns. Each cell grid[r][c] contains a value. You also have a 2D array moveCost where moveCost[x][y] represents the cost to move from a cell with value x in the current row to column y in the next row.

Your task is to find the minimum path cost from any cell in the first row to any cell in the last row. A path consists of choosing one cell from each row, starting from the first row and moving down one row at a time. When moving from row i and column j to row i+1 and column k, you must pay the cost moveCost[grid[i][j]][k].

The cost of a path is the sum of all the values of the chosen cells plus all the movement costs incurred between rows. You must return the minimum possible total path cost.

• You can start at any cell in the first row.
• You must choose exactly one cell per row, moving only to the next row.
• Each move's cost depends on the value of the cell you are moving from and the column you are moving to.

Thought Process

At first glance, the problem looks like a variant of the "minimum path sum" in a grid, but with a twist: the cost to move from one cell to another depends on both the value of the current cell and the column you move to in the next row. This means the cost is not fixed or uniform, and the path can start from any cell in the first row and end at any cell in the last row.

A brute-force approach would try all possible paths from the first row to the last, but this quickly becomes infeasible as the number of possible paths grows exponentially with the number of rows and columns.

To optimize, we recognize that the problem has an "overlapping subproblems" property, which is ideal for dynamic programming. For each cell in a given row, we can compute the minimum cost to reach it by considering all possible cells in the previous row. By storing and reusing these results, we avoid redundant calculations and significantly speed up the solution.

Solution Approach

We use dynamic programming to solve this problem efficiently. Here’s how:

• Step 1: Create a 2D array dp where dp[r][c] represents the minimum cost to reach cell (r, c) in the grid.
• Step 2: Initialize the first row of dp with the values of the first row of grid, since there are no movement costs to start.
• Step 3: For each subsequent row, compute the minimum cost to each cell by considering every possible cell in the previous row:
  • For each cell in row r and column c, look at all cells in row r-1 (columns prev_c).
  • The cost to move from (r-1, prev_c) to (r, c) is dp[r-1][prev_c] + moveCost[grid[r-1][prev_c]][c] + grid[r][c].
  • Take the minimum over all possible prev_c values and store it in dp[r][c].
• Step 4: After filling the dp table, the answer is the minimum value in the last row, since the path can end at any cell in the last row.

This approach ensures we only compute each subproblem once, and we always use the optimal solutions to smaller subproblems to build up to the final answer.

Example Walkthrough

Let's consider the following example:

• grid = [[5,3],[4,0],[2,1]]
• moveCost = [[9,4],[6,7],[5,8],[7,6],[8,9],[6,7]]

Step 1: Initialize dp[0] = [5, 3] (the first row of the grid).

Step 2: Compute dp[1]:

• To reach dp[1][0] (cell value 4):
  • From dp[0][0] (5): cost = 5 + moveCost[5][0] + 4 = 5 + 6 + 4 = 15
  • From dp[0][1] (3): cost = 3 + moveCost[3][0] + 4 = 3 + 7 + 4 = 14
  • Take min: dp[1][0] = 14
• To reach dp[1][1] (cell value 0):
  • From dp[0][0] (5): cost = 5 + moveCost[5][1] + 0 = 5 + 7 + 0 = 12
  • From dp[0][1] (3): cost = 3 + moveCost[3][1] + 0 = 3 + 6 + 0 = 9
  • Take min: dp[1][1] = 9

Step 3: Compute dp[2]:

• To reach dp[2][0] (cell value 2):
  • From dp[1][0] (4): cost = 14 + moveCost[4][0] + 2 = 14 + 8 + 2 = 24
  • From dp[1][1] (0): cost = 9 + moveCost[0][0] + 2 = 9 + 9 + 2 = 20
  • Take min: dp[2][0] = 20
• To reach dp[2][1] (cell value 1):
  • From dp[1][0] (4): cost = 14 + moveCost[4][1] + 1 = 14 + 9 + 1 = 24
  • From dp[1][1] (0): cost = 9 + moveCost[0][1] + 1 = 9 + 4 + 1 = 14
  • Take min: dp[2][1] = 14

Final step: The answer is min(dp[2][0], dp[2][1]) = min(20, 14) = 14.

Time and Space Complexity

Brute-Force Approach: For each row, for every possible cell, you can go to any cell in the next row. This leads to O(n^m) possible paths, where n is the number of columns and m is the number of rows. This is not feasible for large grids.

Optimized Dynamic Programming Approach:

• For every cell in every row, we look at every cell in the previous row. This gives us O(m * n^2) time complexity.
• The space complexity is O(m * n), as we need to store the minimum cost for each cell.

Summary

The "Minimum Path Cost in a Grid" problem is a classic application of dynamic programming. By breaking the problem into subproblems—computing the minimum cost to reach each cell in each row—and reusing those results, we avoid the combinatorial explosion of brute-force solutions. The key insight is to recognize the dependency of each move on both the value and position of the previous cell, and to systematically build up the solution row by row. This approach is both efficient and elegant, and it demonstrates the power of dynamic programming for grid-based pathfinding problems.