Minimum Path Cost in a Grid

medium dp matrix

Problem

You are given an m×n integer grid where every cell holds a distinct value from 0 to m·n−1. Starting from any cell in the top row, you walk down one row at a time until you reach the bottom row. Moving from a cell into column j of the next row costs moveCost[v][j], where v is the value of the cell you are leaving. The total cost of a path is the sum of all the cell values it visits plus the cost of every move. Return the minimum possible total cost of any top-to-bottom path.

Inputgrid = [[5,3],[4,0],[2,1]], moveCost row per value 0..5

Output17

Path 5 → 0 → 1 collects cells 5 + 0 + 1 = 6, and the two move costs add 11, for a total of 17 — the cheapest possible.

grid (rows separated by ';')

moveCost (rows by value, separated by ';')

def minPathCost(grid, moveCost):
    m, n = len(grid), len(grid[0])
    dp = grid[0][:]
    for r in range(1, m):
        nxt = [float('inf')] * n
        for c in range(n):
            for p in range(n):
                cost = dp[p] + moveCost[grid[r - 1][p]][c] + grid[r][c]
                if cost < nxt[c]:
                    nxt[c] = cost
        dp = nxt
    return min(dp)

function minPathCost(grid, moveCost) {
  const m = grid.length, n = grid[0].length;
  let dp = grid[0].slice();
  for (let r = 1; r < m; r++) {
    const nxt = new Array(n).fill(Infinity);
    for (let c = 0; c < n; c++) {
      for (let p = 0; p < n; p++) {
        const cost = dp[p] + moveCost[grid[r - 1][p]][c] + grid[r][c];
        if (cost < nxt[c]) nxt[c] = cost;
      }
    }
    dp = nxt;
  }
  return Math.min(...dp);
}

class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length, n = grid[0].length;
        int[] dp = grid[0].clone();
        for (int r = 1; r < m; r++) {
            int[] nxt = new int[n];
            for (int c = 0; c < n; c++) {
                nxt[c] = Integer.MAX_VALUE;
                for (int p = 0; p < n; p++) {
                    int cost = dp[p] + moveCost[grid[r - 1][p]][c] + grid[r][c];
                    if (cost < nxt[c]) nxt[c] = cost;
                }
            }
            dp = nxt;
        }
        int ans = Integer.MAX_VALUE;
        for (int v : dp) ans = Math.min(ans, v);
        return ans;
    }
}

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

Explanation

Every path drops straight down the grid one row at a time, and at each step it may land in any column of the next row. The price of a path is the sum of the cell values it touches plus a moveCost charged for each downward hop. We want the cheapest path that starts somewhere in the top row and finishes somewhere in the bottom row.

This is a classic row-by-row DP. Let dp[c] be the cheapest cost to reach the current row at column c, counting that cell's own value. The top row is the base case: dp[c] = grid[0][c], because you simply start there.

To fill the next row we look at every target column c. To arrive at it we could come from any column p of the row above. Coming from p costs dp[p] (best cost to that previous cell) plus moveCost[grid[r-1][p]][c] (the charge to step into column c, keyed by the value in the previous cell) plus grid[r][c] (the new cell's own value). We keep the smallest of these over all p.

Example: grid = [[5,3],[4,0],[2,1]]. Tracing the DP, reaching the value-0 cell in the middle row is cheap (it comes from 5 with a low move cost), and from there stepping to value 1 in the bottom row is also cheap. The path 5 → 0 → 1 totals 17, which beats every alternative.

Once the last row is filled, the answer is the smallest entry in dp, since a path may end at any bottom column. Each cell of each row scans the whole previous row, giving O(m·n²) work overall.

Time: O(m·n²) Space: O(n)