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

ধরুন, আমাদের একটি 2D ম্যাট্রিক্স রয়েছে যেখানে কোষগুলি এতে মুদ্রার সংখ্যা উপস্থাপন করে। কয়েন সংগ্রহ করার জন্য আমাদের দুই বন্ধু আছে, এবং তারা উপরের বাম কোণে এবং শুরুতে উপরের ডান কোণায় স্থাপন করা হয়েছে। তারা এই নিয়মগুলি অনুসরণ করে:

• সেল (i, j), একটি মুদ্রা-সংগ্রাহক কক্ষে যেতে পারে (i + 1, j - 1), (i + 1, j), বা (i + 1, j + 1)।

• একটি কক্ষে পৌঁছে তারা কোষটি খালি করে উপলব্ধ সমস্ত মুদ্রা সংগ্রহ করে।

• সংগ্রাহকরা একটি কক্ষে থাকতে বেছে নিতে পারেন, তবে যে কোনো ঘরে কয়েন শুধুমাত্র একবার সংগ্রহ করা যেতে পারে।

আমাদের সর্বোচ্চ সংখ্যক কয়েন সংগ্রহ করতে হবে।

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

তাহলে আউটপুট হবে 17।

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

• A :=ইনপুট ম্যাট্রিক্স

• R :=A

  এর সারি গণনা

• C :=A

  এর কলাম সংখ্যা

• একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি r, c1, c2

  লাগবে

  • যদি r R এর মত হয়, তাহলে

    • রিটার্ন 0

  • উত্তর :=A[r, c1] +(যদি c1 c2 এর সমান না হয়, তাহলে 1 অন্য 0) * A[r, c2]

  • ভিত্তি :=উত্তর

  • প্রতিটি nc1-এর জন্য [c1 − 1, c1, c1 + 1], করুন

    • প্রতিটি nc2 এর জন্য [c2 − 1, c2, c2 + 1], করুন

      • যদি 0 <=nc1

        • উত্তর :=সর্বাধিক উত্তর এবং (বেস + dp(r + 1, nc1, nc2))

  • উত্তর ফেরত দিন

• dp(0, 0, C − 1)

  ফেরত দিন

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

উদাহরণ

class Solution:
   def solve(self, A):
      R, C = len(A), len(A[0])
      def dp(r, c1, c2):
         if r == R:
            return 0
         ans = base = A[r][c1] + (c1 != c2) * A[r][c2]
         for nc1 in [c1 − 1, c1, c1 + 1]:
            for nc2 in [c2 − 1, c2, c2 + 1]:
               if 0 <= nc1 < C and 0 <= nc2 < C:
                  ans = max(ans, base + dp(r + 1, nc1, nc2))
         return ans
      return dp(0, 0, C − 1)
ob = Solution()
print(ob.solve([
   [0, 4, 1, 0],
   [3, 1, 4, 0],
   [2, 5, 1, 1],
   [3, 0, 0, 0]
]))

ইনপুট

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

আউটপুট

17