เส้นทางที่เพิ่มขึ้นที่ยาวที่สุดในเมทริกซ์ใน Python

สมมติว่าเรามีเมทริกซ์หนึ่งอัน เราต้องหาความยาวของทางที่เพิ่มขึ้นที่ยาวที่สุด จากแต่ละเซลล์ เราสามารถย้ายไปที่สี่ทิศทาง - ซ้าย ขวา ขึ้นหรือลง เราไม่สามารถเคลื่อนที่เป็นแนวทแยงมุมหรือเคลื่อนออกนอกเขตได้

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

จากนั้นผลลัพธ์จะเป็น 4 เนื่องจากเส้นทางที่เพิ่มขึ้นที่ยาวที่สุดคือ [3, 4, 5, 6]

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

• กำหนดฟังก์ชัน Solve() จะได้ i,j,matrix

• ถ้า dp[i,j] ไม่ใช่ศูนย์ ดังนั้น

  • กลับ dp[i, j]

• dp[i, j] :=1

• อุณหภูมิ :=0

• สำหรับ r ในช่วง i-1 ถึง i+2 ให้ทำ

  • สำหรับ c ในช่วง j-1 ถึง j+2 ทำ

    • ถ้า r เหมือนกับ i และ c เหมือนกับ j or(|r-i| เหมือนกับ 1 และ |c-j| เหมือนกับ 1) ดังนั้น

      • ไปอ่านตอนต่อไป

    • ถ้า c>=0 และ r>=0 และ r<จำนวนแถวของเมทริกซ์และ c <ขนาด col ของเมทริกซ์[0] และเมทริกซ์[r, c]>เมทริกซ์[i, j] แล้ว

      • temp :=สูงสุดของ temp, แก้ (r, c, matrix)

• dp[i, j] :=dp[i, j] + อุณหภูมิ

• กลับ dp[i, j]

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ถ้าไม่ใช่เมทริกซ์ก็ไม่ใช่ศูนย์ แล้ว

  • คืนค่า 0

• dp :=เมทริกซ์ที่มีขนาดเท่ากับเมทริกซ์ที่กำหนดและเติมด้วย 0

• ตอบ :=0

• สำหรับฉันในช่วง 0 ถึงขนาดของเมทริกซ์ ทำ

  • สำหรับ j ในช่วง 0 ถึงขนาดของเมทริกซ์[0] ให้ทำ

    • ถ้า dp[i, j] เท่ากับ 0 แล้ว

      • แก้ (i, j, เมทริกซ์)

• กลับมาอีกครั้ง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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