leetcode 矩阵中的最长递增路径 python【动态规划】

题目描述

**分析:**假设最长路径终点的是[i][j],则其最长路径值为nums1[i][j],则nums1[i][j]等于它上下左右四个数中，比它小的数中最长路径值最大的那一个+1
因此，我们可以从矩阵的最小值出发，其最长路径值为1，然后计算第二小的数的最长路径值，以此类推

class Solution:
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        a = len(matrix)
        dic = {}
        nums_max = 1
        if a == 0:
            nums_max = 0
        else:
            b = len(matrix[0])
            for i in range(a):
                for j in range(b):
                    dic[(i,j)] = matrix[i][j]
            v =  dic.keys()
            nums1 = [[1 for i in range(b)] for j in range(a)]        
            dic = sorted(dic.items(),key = lambda x:x[1])
            for k in dic:
                i = k[0][0]
                j = k[0][1]
                if (i+1,j) in v and matrix[i+1][j]<matrix[i][j] and nums1[i][j]<nums1[i+1][j]+1:
                    nums1[i][j] = nums1[i+1][j] + 1
                if (i,j+1) in v and matrix[i][j+1]<matrix[i][j] and nums1[i][j]<nums1[i][j+1]+1:
                    nums1[i][j] = nums1[i][j+1] +1
                if (i-1,j) in v and matrix[i-1][j]<matrix[i][j] and nums1[i][j]<nums1[i-1][j]+1:
                    nums1[i][j] = nums1[i-1][j] +1
                if (i,j-1) in v and matrix[i][j-1]<matrix[i][j] and nums1[i][j]<nums1[i][j-1]+1:
                    nums1[i][j] = nums1[i][j-1] + 1    
                nums_max = max(nums_max,nums1[i][j])              
        return nums_max