পাইথনে আমরা কতগুলো উপায়ে সিঁড়ি বেয়ে উঠতে পারি তা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের n ধাপ সহ একটি সিঁড়ি আছে এবং আমরা একবারে 1 বা 2 ধাপ উপরে উঠতে পারি। আমাদের একটি ফাংশন সংজ্ঞায়িত করতে হবে যা আমরা সিঁড়ি বেয়ে উঠতে পারি এমন অনন্য উপায়ের সংখ্যা প্রদান করে৷

পদক্ষেপের ক্রম পরিবর্তন করা উচিত নয়, তাই প্রতিটি ধাপের ক্রম একটি উপায় হিসাবে গণনা করা হয়। যদি উত্তরটি খুব বড় হয় তবে ফলাফলটি 10^9 + 7

সুতরাং, যদি ইনপুটটি n =5 এর মত হয়, তাহলে আউটপুট হবে 8, কারণ 8টি অনন্য উপায় রয়েছে −

• 1, 1, 1, 1, 1
• 2, 1, 1, 1
• 1, 2, 1, 1
• 1, 1, 2, 1
• 1, 1, 1, 2
• 1, 2, 2
• 2, 1, 2
• 2, 2, 1

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

• dp:=n+1 আকারের একটি অ্যারে, এবং 0 দিয়ে পূরণ করুন
• dp[1]:=1
• 2 থেকে n+1 রেঞ্জের জন্য,
  করুন
  • dp[i]:=dp[i-1]+dp[i-2]
• dp mod m-এর শেষ উপাদান ফেরত দিন

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

উদাহরণ

m =(10**9)+7
class Solution:
   def solve(self, n):
      dp=[0 for _ in range(n+2)]
      dp[1]=1
      for i in range(2,n+2):
         dp[i]=dp[i-1]+dp[i-2]
      return dp[-1] % m
ob = Solution()
print(ob.solve(5))

ইনপুট

5

আউটপুট

8