โปรแกรมตามความยาวของเส้นทางที่เพิ่มขึ้นที่ยาวที่สุดในเมทริกซ์ที่กำหนดใน Python

สมมติว่าเรามีเมทริกซ์ 2 มิติ เราต้องหาความยาวของเส้นทางที่เพิ่มขึ้นอย่างเคร่งครัด ในการข้ามเส้นทางนั้น เราสามารถเลื่อนขึ้น ลง ซ้าย ขวา หรือแนวทแยงได้

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 6 เนื่องจากเส้นทางที่ยาวที่สุดคือ [1, 2, 4, 6, 7, 9]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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

ตัวอย่าง (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))

อินพุต

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

ผลลัพธ์

6