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

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

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

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

• a :=จำนวนแถว b :=จำนวนคอลัมน์

• ผม :=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] :=เมทริกซ์[i, j] + เมทริกซ์ขั้นต่ำ[i, j + 1] และเมทริกซ์[i + 1, j]

    • ลด j โดย 1

  • เจ :=b - 1

  • ผม :=ผม - 1

• ส่งคืนเมทริกซ์[0, 0]

ตัวอย่าง

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

class Solution(object):
   def minPathSum(self, grid):
      """
      :type grid: List[List[int]]
      :rtype: int
      """
      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])

อินพุต

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

ผลลัพธ์

7