পাইথনে সর্বনিম্ন পথের যোগফল

ধরুন আমাদের কাছে একটি m x n ম্যাট্রিক্স রয়েছে যা অ-ঋণাত্মক পূর্ণসংখ্যা দিয়ে পূর্ণ, উপরের বাম কোণ থেকে নীচের ডানদিকের কোণে একটি পথ সন্ধান করুন যা তার পথ বরাবর সমস্ত সংখ্যার যোগফলকে ছোট করে। নড়াচড়া শুধুমাত্র সময়ে যে কোন সময়ে হয় নিচে বা ডান হতে পারে। সুতরাং উদাহরণস্বরূপ, যদি ম্যাট্রিক্স নীচের মত হয়

৷ ৷ ৷

1	3	1
1	5	1
4	2	1

আউটপুট হবে 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]
- i 1 দ্বারা হ্রাস করুন
j :=b – 1 এবং i :=সারি – 1
যখন i>=0
- যখন j>=0
  - ম্যাট্রিক্স[i, j] :=ম্যাট্রিক্স[i, j] + সর্বনিম্ন ম্যাট্রিক্স[i, j + 1] এবং ম্যাট্রিক্স[i + 1, j]
  - j 1 দ্বারা কমিয়ে দিন
- j :=b – 1
- i :=i – 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]]