Lập trình độ dài của đường dẫn tăng dài nhất trong một ma trận nhất định bằng Python

Giả sử chúng ta có một ma trận 2D, chúng ta phải tìm độ dài của đường đi tăng dần dài nhất. Để đi qua con đường, chúng ta có thể di chuyển lên, xuống, sang trái, sang phải hoặc theo đường chéo.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 6, vì Đường dẫn dài nhất là [1, 2, 4, 6, 7, 9]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n := row count of matrix , m := column count of matrix
moves := a list of pairs to move up, down, left and right [[1, 0], [-1, 0], [0, 1], [0, -1]]
Define a function dp() . This will take y, x
if x and y are in range of matrix, then
   return 0
currVal := matrix[y, x]
res := 0
for each d in moves, do
   (dy, dx) := d
   (newY, newX) := (y + dy, x + dx)
      if newY and newX are in range of matrix and matrix[newY, newX] > currVal, then
         res := maximum of res and dp(newY, newX)
return res + 1
From the main method do the following:
result := 0
for i in range 0 to n - 1, do
   for j in range 0 to m - 1, do
      result := maximum of result and dp(i, j)
return result

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[ [2, 4, 6], [1, 5, 7], [3, 3, 9] ]

Đầu ra

6