Python矩阵中最长的递增路径

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个矩阵。我们必须找到最长的增长路径的长度。从每个单元格，我们可以向四个方向移动-左，右，上或下。我们不能对角移动或移动到边界之外。

所以，如果输入像

994
668
211

则最长的增长路径是[3、4、5、6]，则输出将为4。

为了解决这个问题，我们将遵循以下步骤-

  • 定义一个功能solve()。这将需要i，j，matrix

  • 如果dp [i，j]不为零，则

    • 返回dp [i，j]

  • dp [i，j]：= 1

  • 温度：= 0

  • 对于范围为i-1至i + 2的r

    • 如果r与i相同，c与j相同，或者（| ri |与1相同，| cj |与1相同），则

    • 如果c> = 0且r> = 0且r <矩阵的行数和c <矩阵[0]和matrix [r，c]>矩阵[i，j]的col大小，则

    • 进行下一次迭代

    • temp：=温度最大值，solve（r，c，矩阵）

    • 对于范围j-1至j + 2的c

    • dp [i，j]：= dp [i，j] +温度

    • 返回dp [i，j]

    • 从主要方法中执行以下操作-

    • 如果矩阵不是非零，则

      • 返回0

    • dp：=一个与给定矩阵大小相同的矩阵，并用0填充

    • 回答：= 0

    • 对于0到矩阵大小的范围内的i

      • 如果dp [i，j]等于0，则

      • 解（i，j，矩阵）

      • 对于范围为0到矩阵[0]大小的j，执行

      • 返回ans

      例 

      让我们看下面的实现以更好地理解-

      class Solution(object):
         def solve(self,i,j,matrix):
            if self.dp[i][j]:
               return self.dp[i][j]
            self.dp[i][j] = 1
            temp = 0
            for r in range(i-1,i+2):
               for c in range(j-1,j+2):
                  if r==i and c==j or (abs(r-i)==1 and abs(c-j)==1):
                     continue
                  if c>=0 and r>=0 and r<len(matrix) and c<len(matrix[0]) and matrix[r][c]>matrix[i][j]:
      temp = max(temp,self.solve(r,c,matrix))
                     self.dp[i][j]+=temp
                     return self.dp[i][j]
         def longestIncreasingPath(self, matrix):
            if not matrix:
               return 0
            self.dp = [ [0 for i in range(len(matrix[0]))] for j in range(len(matrix))]
            self.ans = 0
            for i in range(len(matrix)):
               for j in range(len(matrix[0])):
                  if self.dp[i][j]==0:
                     self.solve(i,j,matrix)
                  self.ans = max(self.ans,self.dp[i][j])
            return self.ans
      ob = Solution()print(ob.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))

      输入值

      [[9,9,4],[6,6,8],[2,1,1]]

      输出结果

      4

      以上是 Python矩阵中最长的递增路径 的全部内容， 来源链接： utcz.com/z/345489.html

      回到顶部