在Python中给定矩阵的最长递增路径长度的程序

假设我们有一个二维矩阵，我们需要找到最长严格递增路径的长度。为了遍历路径，我们可以向上、向下、向左或向右移动，但不能斜向移动。

因此，如果输入为

2	4	6
1	5	7
3	3	9

那么输出将为6，因为最长路径是[1,2,4,6,7,9]

为了解决这个问题，我们将按照以下步骤进行-

n：矩阵的行数，m：矩阵的列数 
moves：向上、向下、向左和向右移动的一对列表[[1, 0], [-1, 0], [0, 1], [0, -1]] 
定义一个函数dp（）。这需要y、x 
如果x和y在矩阵的范围内，则 
   返回0 
currVal：=matrix [y，x] 
res：=0 
对于移动的每个d，执行以下操作 
   （dy，dx）：=d 
   （newY，newX）：=（y + dy，x + dx） 
      如果newY和newX在矩阵的范围内且matrix [newY，newX]>currVal，则 
         res：=res和dp（newY，newX）的最大值 
返回res + 1 
从主方法执行以下操作： 
结果：=0 
for i in range 0 to n - 1，do 
   for j in range 0 to m - 1，do 
      结果：=结果和dp（i，j）的最大值 
返回结果

例子 (Python)

为了更好的理解，让我们看一下以下实现 –

class Solution:
   def solve(self, matrix):
      n, m = len(matrix), len(matrix[0])
      moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
      def dp(y, x):
         if y < 0 or y >= n or x < 0 or x >= m:
            return 0
         currVal = matrix[y][x]
         res = 0
         for d in moves:
            dy, dx = d
            newY, newX = y + dy, x + dx
            if (newY >= 0 and newY < n and newX >= 0 and newX < m and matrix[newY][newX] > currVal):
               res = max(res, dp(newY, newX))
         return res + 1
      result = 0
      for i in range(n):
         for j in range(m):
            result = max(result, dp(i, j))
      return result
ob = Solution()
matrix = [
   [2, 4, 6],
   [1, 5, 7],
   [3, 3, 9]
]
print(ob.solve(matrix))