2304.网格中的最小路径代价

链接：2304.网格中的最小路径代价
难度：Medium
标签：数组、动态规划、矩阵
简介：从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。

题解 1 - python

• 编辑时间：2023-11-22
• 执行用时：296ms
• 内存消耗：21.95MB
• 编程语言：python
• 解法介绍：dp[i][j]表示到ij时的最小开销。

class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        dp = [[inf] * m for _ in range(n)]
        for j in range(m): dp[0][j] = grid[0][j]
        for i in range(1, n):
            for j in range(m):
                dp[i][j] = grid[i][j] + min(moveCost[grid[i - 1][k]][j] + dp[i - 1][k] for k in range(m))
        return min(dp[n - 1])