পাইথনে ক্রমাগত সর্বাধিক k গেমে জেতার উপায় গণনা করার প্রোগ্রাম

ধরুন আমাদের দুটি সংখ্যা আছে n এবং k। এখানে n আমরা যে গেম খেলতে যাচ্ছি তার সংখ্যা উপস্থাপন করে। আমাদের খুঁজে বের করতে হবে কত উপায়ে আমরা ক্রমাগত k বা কম গেম জিততে পারি। যদি উত্তরটি খুব বড় হয় তাহলে ফলাফলটি 10^9 + 7 দ্বারা পরিবর্তন করুন।

সুতরাং, যদি ইনপুটটি n =3 k =2 এর মত হয়, তাহলে আউটপুট হবে 7, কারণ আমরা যে সম্ভাব্য উপায়ে পরপর 2 বা তার কম বার জিততে পারি, তা হল ["LLL", "WLL", "LWL", "LLW", "WWL", "LWW", "WLW"]

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

m :=1^9 + 7
একটি ফাংশন dp() সংজ্ঞায়িত করুন। এর জন্য i, K
যদি i>=n বা K> k হয়, তাহলে
- সত্য ফেরত যখন K <=k, অন্যথায় মিথ্যা
dp(i + 1, 0) mod m + dp(i + 1, K + 1) mod m ফেরত দিন
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
রিটার্ন dp(0, 0) mod m

উদাহরণ

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

def solve(n, k):
   m = 1**9 + 7

   def dp(i, K):
      if i >= n or K > k:
         return K <= k
      return dp(i + 1, 0) % m + dp(i + 1, K + 1) % m

   return dp(0, 0) % m

n = 4
k = 2
print(solve(n, k))

ইনপুট

4, 2