รวมเส้นทางขั้นต่ำใน Python

สมมติว่าเรามีเมทริกซ์ขนาด m x n ที่เต็มไปด้วยจำนวนเต็มไม่เป็นลบ ให้ค้นหาเส้นทางจากมุมบนซ้ายไปยังมุมขวาล่าง ซึ่งจะลดผลรวมของตัวเลขทั้งหมดตามเส้นทางของมัน การเคลื่อนไหวสามารถขึ้นหรือลงได้ทุกเวลาเท่านั้น ตัวอย่างเช่น ถ้าเมทริกซ์อยู่ด้านล่าง

ผลลัพธ์จะเป็น 7 เส้นทางจะเป็น 1,3,1,1,1 ซึ่งจะลดผลรวมให้เหลือน้อยที่สุด

ให้เราดูขั้นตอน -

• a :=จำนวนแถว b :=จำนวนคอลัมน์
• i :=a – 1, j :=b – 1
• ในขณะที่ j>=0
  • เมทริกซ์[a, j] :=เมทริกซ์[a, j] + เมทริกซ์[a, j + 1]
  • ลด j ทีละ 1
• ในขณะที่ i>=0
  • เมทริกซ์[i, b] :=เมทริกซ์[i, b] + เมทริกซ์[i + 1, b]
  • ลดลง 1
• j :=b – 1 และ i :=row – 1
• ในขณะที่ i>=0
  • ในขณะที่ j>=0
    • เมทริกซ์[i, j] :=matrix[i, j] + เมทริกซ์ขั้นต่ำ[i, j + 1] และเมทริกซ์[i + 1, j]
    • ลด j ทีละ 1
  • j :=b – 1
  • ผม :=ผม – 1
• เมทริกซ์ผลตอบแทน[0, 0]

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

ตัวอย่าง

class Solution(object):
   def minPathSum(self, grid):
      row = len(grid)-1
      column = len(grid[0])-1
      i=row-1
      j=column-1
      while j>=0:
         grid[row][j]+=grid[row][j+1]
         j-=1
      while i>=0:
         grid[i][column]+=grid[i+1][column]
         i-=1
      j=column-1
     i = row-1
      while i>=0:
         while j>=0:
            grid[i][j] += min(grid[i][j+1],grid[i+1][j])
            j-=1
         j=column-1
         i-=1
      return(grid[0][0])
ob1 = Solution()
print(ob1.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))

อินพุต

[[1,3,1],[1,5,1],[4,2,1]]

ผลลัพธ์

7