题目浅析

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

  • 简单地说，就是给一个二维数组，要从第一列向右走，可以同行或者上下一行，但下一个位置的值必须严格大于当前的值。

思路分享

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

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

        # 记忆化搜索
        # ans = 0
        # m, n = len(grid), len(grid[0])
        # # 走到 i j 的最大步数为 val
        # @cache
        # def dfs(i:int, j:int) -> None:
        #     nonlocal ans
        #     ans = max(ans, j)
        #     if j == n-1:
        #         return 
        #     cur = grid[i][j]
        #     for k in range(i-1, i+2):
        #         if 0 <= k <= m-1 and cur < grid[k][j+1]:
        #             dfs(k, j+1)   
        #     grid[i][j] = 0

        # for i in range(m):
        #     dfs(i, 0)
        # return ans