题目浅析

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

  • 简单地说，就是给一个二维数组，可以从二维数组的第一行任意位置触发，到同列或者相邻列（加减一），求走到最底的最小数值是多少。

思路分享

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

  • 参考题解
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
44
class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        # 空间优化
        n = len(matrix)
        if n == 1:
            return matrix[0][0]

        f = [inf] + [0]*n + [inf]
        for i in range(n):
            pre = f[0]
            for j in range(n):
                pre, f[j+1] = f[j+1], min(pre, f[j+1], f[j+2]) + matrix[i][j]
                # print(f)
        return min(f)

        # 递推
        # f[i][j] = min(f[i-1][j-1], f[i-1][j], f[i-1][j+1]) + matrix[i][j]
        n = len(matrix)
        if n == 1:
            return matrix[0][0]

        f = [[0]*n for _ in range(n+1)]
        for i in range(n):
            for j in range(n):
                if j == 0:
                    f[i+1][j] = min(f[i][j], f[i][j+1]) + matrix[i][j]
                elif j == n-1:
                    f[i+1][j] = min(f[i][j], f[i][j-1]) + matrix[i][j]
                else:
                    f[i+1][j] = min(f[i][j], f[i][j-1], f[i][j+1]) + matrix[i][j]
                # print(f)
        return min(f[-1])

        # 记忆化搜索
        # n = len(matrix)
        # @cache
        # def dfs(i:int, j:int) -> int:
        #     if j < 0 or j >= n:
        #         return inf
        #     if i == 0:
        #         return matrix[i][j]
        #     return min(dfs(i-1, j-1), dfs(i-1, j), dfs(i-1, j+1)) + matrix[i][j]
        
        # return min(dfs(n-1, j) for j in range(n))