Python 中的矩陣最長遞增路徑

假設我們有一個矩陣；我們需要找到最長遞增路徑的長度。從每個單元格，我們可以移動到四個方向——左、右、上或下。我們不能對角移動或移出邊界。

因此，如果輸入類似於

則輸出將為 4，因為最長遞增路徑為 [3, 4, 5, 6]。

為了解決這個問題，我們將遵循以下步驟：

• 定義一個函式 solve()。這將接收 i、j、matrix 作為引數。

• 如果 dp[i,j] 不為零，則

  • 返回 dp[i, j]

• dp[i, j] := 1

• temp := 0

• 對於 r 從 i-1 到 i+2，執行

  • 對於 c 從 j-1 到 j+2，執行

    • 如果 r 等於 i 且 c 等於 j 或 (|r-i| 等於 1 且 |c-j| 等於 1)，則

      • 進入下一個迭代

    • 如果 c>=0 且 r>=0 且 r< 矩陣的行數 且 c < matrix[0] 的列大小 且 matrix[r, c]>matrix[i, j]，則

      • temp := temp 和 solve(r, c, matrix) 的最大值

• dp[i, j] := dp[i, j] + temp

• 返回 dp[i, j]

• 從主方法執行以下操作：

• 如果 matrix 不為零，則

  • 返回 0

• dp := 一個與給定矩陣大小相同的矩陣，並填充 0

• ans := 0

• 對於 i 從 0 到 matrix 的大小，執行

  • 對於 j 從 0 到 matrix[0] 的大小，執行

    • 如果 dp[i, j] 等於 0，則

      • solve(i, j, matrix)

• 返回 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

Arnab Chakraborty

更新於: 2020-07-23

484 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習