题目浅析

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

  • 简单地说，就是给一个二维数组，现在要从第一行走到最后一行，但是两个相邻行的取数不能同列

思路分享

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

  • 参考题解
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 minFallingPathSum(self, grid: List[List[int]]) -> int:
        # 递推
        ans = 0
        n = len(grid)
        if n == 1:
            return grid[0][0]
        # f[i][j] = min(f[i+1][k] for k in range(n) if k != j) + grid[i][j]
        f = [[0]*n for _ in range(n+1)]
        for i in range(n-1, -1, -1):
            for j in range(n):
                f[i][j] = min(f[i+1][k] for k in range(n) if k != j) + grid[i][j]
        return min(f[0])

        # 记忆化搜索
        ans = 0
        n = len(grid)
        @cache
        def dfs(i:int, j:int) -> int:
            if not (0 <= j <= n-1):
                return inf

            if i == n-1:
                return grid[i][j]
            
            return min(dfs(i+1, k) for k in range(n) if k != j) + grid[i][j]
        
        return min(dfs(0, i) for i in range(n))