#2304
Minimum Path Cost in a Grid
specialist · 605 · lc medium +29 · verified · 68% accepted · 973 likes · top 75%
Description
You are given a 0-indexed m x n integer matrix grid of distinct integers from 0 to m * n - 1. From cell (x, y) with x < m - 1, you may move to any cell in row x + 1. Movement from the last row is not allowed.
Move costs are given by a 2D array moveCost of size (m * n) x n, where moveCost[i][j] is the cost of transitioning from a cell with value i to column j in the next row.
A path's total cost is the sum of all visited cell values plus all transition costs. Return the minimum cost of any path that starts in the first row and ends in the last row.
Example 1:
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.
Code
1
2
3