【LetMeFly】2304.網格中的最小路徑代價：DP

力扣題目鏈接：https://leetcode.cn/problems/minimum-path-cost-in-a-grid/

給你一個下標從 0 開始的整數矩陣?grid ，矩陣大小為 m x n ，由從 0 到 m * n - 1 的不同整數組成。你可以在此矩陣中，從一個單元格移動到 下一行 的任何其他單元格。如果你位于單元格 (x, y) ，且滿足 x < m - 1 ，你可以移動到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一個單元格。注意：?在最后一行中的單元格不能觸發移動。

每次可能的移動都需要付出對應的代價，代價用一個下標從 0 開始的二維數組 moveCost 表示，該數組大小為 (m * n) x n ，其中 moveCost[i][j] 是從值為 i 的單元格移動到下一行第 j 列單元格的代價。從?grid 最后一行的單元格移動的代價可以忽略。

grid 一條路徑的代價是：所有路徑經過的單元格的 值之和 加上 所有移動的 代價之和 。從 第一行 任意單元格出發，返回到達 最后一行 任意單元格的最小路徑代價。

?

示例 1：

輸入：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
輸出：17
解釋：最小代價的路徑是 5 -> 0 -> 1 。
- 路徑途經單元格值之和 5 + 0 + 1 = 6 。
- 從 5 移動到 0 的代價為 3 。
- 從 0 移動到 1 的代價為 8 。
路徑總代價為 6 + 3 + 8 = 17 。

示例 2：

輸入：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]]
輸出：6
解釋：
最小代價的路徑是 2 -> 3 。 
- 路徑途經單元格值之和 2 + 3 = 5 。 
- 從 2 移動到 3 的代價為 1 。 
路徑總代價為 5 + 1 = 6 。

?

提示：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 50
• grid 由從 0 到 m * n - 1 的不同整數組成
• moveCost.length == m * n
• moveCost[i].length == n
• 1 <= moveCost[i][j] <= 100

方法一：DP

從倒數第二行開始往第一行遍歷：

• 對于這一行的每一個元素：
  • 計算出 從下一行的所有元素中來到這一行，增加值最小的那個
• 這個元素加上下一行來的最小增加量

最終返回第一行中的最小元素即為答案。

• 時間復雜度$O(n{m}^2)$，其中$size(grid)=n\times m$（$n$行$m$列）
• 空間復雜度$O(1)$

AC代碼

C++

class Solution {
public:int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {int n = grid.size(), m = grid[0].size();for (int i = n - 2; i >= 0; i--) {for (int j = 0; j < m; j++) {int m_ = 100000000;for (int k = 0; k < m; k++) {m_ = min(m_, grid[i + 1][k] + moveCost[grid[i][j]][k]);}grid[i][j] += m_;}}return *min_element(grid[0].begin(), grid[0].end());}
};

Python

# from typing import Listclass Solution:def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:n, m = len(grid), len(grid[0])for i in range(n - 2, -1, -1):for j in range(m):m_ = 100000000for k in range(m):m_ = min(m_, grid[i + 1][k] + moveCost[grid[i][j]][k])grid[i][j] += m_return min(grid[0])

同步發文于CSDN，原創不易，轉載經作者同意后請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134563145