题目描述
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例1：
输入: nums = [ [9,9,4], [6,6,8], [2,1,1] ] 输出: 4 解释: 最长递增路径为 [1, 2, 6, 9]。
思路
在这里比较适合使用动态规划来解题。
我们用matrix来储存原本数字的矩阵，然后创建一个新矩阵store，其中每一个元素（i,j）表示在matrix走到（i,j）最长递增路径长度。
关于具体的解释，在这里援引LeetCode上一篇非常有趣的讲解https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/ji-ge-wen-da-kan-dong-shen-du-sou-suo-ji-yi-hua-sh/：
这样的话代码就比较好写了：
class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: if not matrix: return 0 h,w = len(matrix),len(matrix[0]) store = [[None]*(w) for i in range(h)] m = 0 #储存max路径值 def search_nearby(i,j): nonlocal m compare = [] #储存可以比较的候选人 #这个楼主很懒,还没想怎么简化下面的代码 #反正下面四个代码块就是分别看一下上、下、左、右哪些格子的值可以当做候选人比较 #上 if i != 0 and matrix[i-1][j] < matrix[i][j]: #有上边且上边小于当前数的话 compare.append(store[i-1][j]) if store[i-1][j] else compare.append(search_nearby(i-1,j)) #左 if j != 0 and matrix[i][j-1] < matrix[i][j]: #有左边且左边小于当前数的话 compare.append(store[i][j-1]) if store[i][j-1] else compare.append(search_nearby(i,j-1)) #下 if i != h-1 and matrix[i+1][j] < matrix[i][j]: #有下边且下边小于当前数的话 compare.append(store[i+1][j]) if store[i+1][j] else compare.append(search_nearby(i+1,j)) #右 if j != w-1 and matrix[i][j+1] < matrix[i][j]: #有右边且右边小于当前数的话 compare.append(store[i][j+1]) if store[i][j+1] else compare.append(search_nearby(i,j+1)) store[i][j] = max(compare)+1 if compare else 1 #如果没有compare说明这是一个很小的数，是一个起始点，能组成的长度只有1 #有的话就原来最长路径+1 m = max(m,store[i][j]) return (store[i][j]) for i in range(h): for j in range(w): if not store[i][j]: search_nearby(i,j) return m