পাইথনে আমরা সর্বাধিক সংখ্যক কয়েন সংগ্রহ করতে পারি তা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি 2D ম্যাট্রিক্স আছে যেখানে প্রতিটি সেল কিছু কয়েন সঞ্চয় করে। আমরা যদি [0,0] থেকে শুরু করি, এবং শুধুমাত্র ডানে বা নিচে যেতে পারি, তাহলে নীচের ডানদিকের কোণে আমরা সর্বোচ্চ কতগুলি কয়েন সংগ্রহ করতে পারি তা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

তারপর আউটপুট 14 হবে, যেমন আমরা পথ ধরি:[1, 4, 2, 2, 5]

এটি সমাধান করার জন্য, আমরা এই পদক্ষেপগুলি অনুসরণ করব—

• রেঞ্জ 1 থেকে A এর সারি গণনার জন্য, করুন

  • A[r, 0] :=A[r, 0] + A[r-1, 0]

• রেঞ্জ 1 থেকে A এর কলাম গণনার মধ্যে c এর জন্য, করুন

  • A[0, c] :=A[0, c] + A[0, c-1]

  • রেঞ্জ 1 থেকে A এর আকারের জন্য, করুন

  • 1 থেকে A[0] এর আকারের মধ্যে c এর জন্য, করুন

  • A[r, c] =A[r, c] + সর্বাধিক (A[r-1, c] এবং A[r, c-1]

• A

  এর নিচের ডানদিকের কোণে রিটার্ন মান

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

উদাহরণ

class Solution:
   def solve(self, A):
      for r in range(1, len(A)):
         A[r][0] += A[r-1][0]
      for c in range(1, len(A[0])):
         A[0][c] += A[0][c-1]
      for r in range(1, len(A)):
         for c in range(1, len(A[0])):
            A[r][c] += max(A[r-1][c], A[r][c-1])
      return A[-1][-1]
ob = Solution()
matrix = [ [1, 4, 2, 2], [6, 0, 0, 5] ]
print(ob.solve(matrix))

ইনপুট

matrix = [
   [1, 4, 2, 2],
   [6, 0, 0, 5]
]

আউটপুট

14