题目浅析

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

  • 简单地说，就是给一个二维数组从左上角走到右下角，注意进入格子和待在格子都有代价（具体规则请看原题），求最终的最小代价。

思路分享

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

  • 参考题解
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def minCost(self, m: int, n: int, waitCost: List[List[int]]) -> int:
        # 空间优化
        ans = 0
        f = [inf]*(n+1)
        f[1] = -waitCost[0][0]
        # f[i+1][j+1] = (i+1)*(j+1) + waitCost[i][j] +  min(f[i+1][j], f[i][j+1])
        for i in range(m):
            for j in range(n):
                f[j+1] = (i+1)*(j+1) + min(f[j], f[j+1])
                if i != m-1 or j != n-1:
                    f[j+1] += waitCost[i][j]
        # print(f)
        return f[n]

        # 递推
        ans = 0
        f = [[inf]*(n+1) for _ in range(m+1)]
        f[0][1] = -waitCost[0][0]
        # f[i+1][j+1] = (i+1)*(j+1) + waitCost[i][j] +  min(f[i+1][j], f[i][j+1])
        for i in range(m):
            for j in range(n):
                f[i+1][j+1] = (i+1)*(j+1) + min(f[i+1][j], f[i][j+1])
                if i != m-1 or j != n-1:
                    f[i+1][j+1] += waitCost[i][j]
        # print(f)
        return f[m][n]
        
        # 记忆化搜索
        ans = 0
        @cache
        def dfs(i, j):
            if not (0 <= i <= m-1 and 0<=j<=n-1):
                return inf
            val = (i+1) * (j+1)
            if i == m-1 and j == n-1:
                return val
            
            val += waitCost[i][j]
            return min(dfs(i+1, j), dfs(i, j+1)) + val

        return min(dfs(1, 0), dfs(0, 1)) + 1