C++ এ ন্যূনতম পথের যোগফল

ধরুন আমাদের কাছে একটি 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]

  • 1 দ্বারা j হ্রাস করুন

• যখন 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]

    • 1 দ্বারা j হ্রাস করুন

  • j :=b - 1

  • i :=i - 1

• রিটার্ন ম্যাট্রিক্স[0, 0]

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

শ্রেণির সমাধান(অবজেক্ট):def minPathSum(self, grid):""" :type grid:List[List[int]] :rtype:int """ row =len(grid)-1 column =len( গ্রিড[0])-1 i=row-1 j=column-1 যখন j>=0:grid[row][j]+=grid[row][j+1] j-=1 যখন i>=0 :গ্রিড[i][কলাম]+=গ্রিড[i+1][কলাম] i-=1 j=column-1 i =সারি-1 যখন i>=0:যখন j>=0:গ্রিড[i][ j] +=মিনিট(গ্রিড[i][j+1],গ্রিড[i+1][j]) j-=1 j=কলাম-1 i-=1 রিটার্ন(গ্রিড[0][0]) 
ইনপুট
 
[[1,3,1],[1,5,1],[4,2,1]]
 
আউটপুট
 
7