leetcode_0329 矩阵中的最长递增路径

Posted on | In , ,

题目

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

1
2
3
4
5
6
7
8
输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2:

1
2
3
4
5
6
7
8
输入: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
输出: 4 
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

答案

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
45
46
47
48
49
50
51
class Solution:
    def longestIncreasingPath(self, matrix):
        # 设置一个矩阵 每个元素表示由该节点出发最远到别的地方的长度 先把初始值都为一个空字符串"；表示这个是没有被检测过的位置
        if not matrix:
            return 0;
        m = len(matrix)
        n = len(matrix[0])
        dp = [[""]*n for _ in range(m)]
        
        # 这个函数用来得到一个元素点最远所能达到的距离。
        def getDPElement(i,j):
            #   1. 如果再dp矩阵中已经有了的就直接返回
            #   2. 如果没有的现场算一下
            if dp[i][j] != "":
                return dp[i][j]
            else:
                # 此时矩阵中这个位置的值还没求出，想要外延展，则需要要那周围四个位置的值要大于（i，j）的值为前提才可以
                D_x = [0,1,0,-1]
                D_y = [1,0,-1,0]
                res = 0     # 用这个值获取周围有比它大的数字的最大长度。
                for x,y in zip(D_x,D_y):
                    # 判断边界，再比较大小，同时满足后对邻居调用本函数
                    if not (i+x < 0 or i+x >= m or j+y < 0 or j+y >= n):
                        if matrix[i][j] < matrix[i+x][j+y]:
                            res = max(res, getDPElement(i+x,j+y))

                dp[i][j] = res + 1  #    此时包括了该位置
                return dp[i][j]
        
        # 主函数里调用
        res = 1
        for i in range(m):
            for j in range(n):
                temp = getDPElement(i,j)
                if res < temp:
                    res = temp

        return res

if __name__ == "__main__":
    nums_1 =[
    [9, 9, 4],
    [6, 6, 8],
    [2, 1, 1]]
    nums_2 =[
        [3, 4, 5],
        [3, 2, 6],
        [2, 2, 1]]
    a = Solution()
    print(a.longestIncreasingPath(nums_1))
    print(a.longestIncreasingPath(nums_2))