题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个二维数组，要从这个数组的第一行移动到最后一行，其中每个值会有移动到下一行的对应代价，路径代价由移动的代价和移动格子值相加所得，求最小的路径代价。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        # 递推
        m, n = len(grid), len(grid[0])
        f = [[0] * n for _ in range(m)]
        for i in range(n):
            f[m-1][i] = grid[m-1][i]

        # f[i][j] = min(f[i+1][k] + moveCost[grid[i][j]][k] for k in range(n)) + grid[i][j]
        for i in range(m-2, -1, -1):
            for j in range(n):
                val = grid[i][j]
                f[i][j] = min(f[i+1][k] + moveCost[val][k] for k in range(n)) + val
        # print(f)
        return min(f[0])

        ## 记忆化搜索
        m, n = len(grid), len(grid[0])
        # 移动到下标 i j 时，最小的值之和
        @cache
        def dfs(i:int, j:int) -> int:
            val = grid[i][j]
            if i == m-1:
                return val

            return min(dfs(i+1, k) + moveCost[val][k] for k in range(n)) + val
        
        return min(dfs(0, j) for j in range(n))