Minimum path cost in a grid

Array Dynamic Programming Matrix

68.0% acceptance

Feb 25, 2026

973

177

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. Each possible move has a cost given by moveCost[i][j] = cost of moving from cell with value i to column j. The cost of a path is the sum of all values of cells visited plus the sum of costs of all 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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_path_cost(grid: Vec<Vec<i32>>, move_cost: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut dp: Vec<i32> = grid[0].clone();
    for r in 0..m - 1 {
      let mut ndp = vec![i32::MAX; n];
      for c in 0..n {
        let val = grid[r][c] as usize;
        for nc in 0..n {
          let cost = dp[c] + move_cost[val][nc] + grid[r + 1][nc];
          if cost < ndp[nc] {
            ndp[nc] = cost;
          }
        }
      }
      dp = ndp;
    }
    *dp.iter().min().unwrap()
  }
}