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

ধরুন আমাদের n ধাপ সহ একটি সিঁড়ি আছে এবং আমাদের কাছে আরও একটি সংখ্যা k আছে, প্রাথমিকভাবে আমরা 0 সিঁড়িতে আছি এবং আমরা একবারে 1, 2 বা 3 ধাপে উঠতে পারি। কিন্তু আমরা সর্বাধিক k বার মাত্র 3টি সিঁড়ি উঠতে পারি। এখন আমাদের সিঁড়ি বেয়ে ওঠার উপায় খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি n =5, k =2 এর মত হয়, তাহলে আউটপুট হবে 13, কারণ বিভিন্ন উপায়ে আমরা সিঁড়ি বেয়ে উঠতে পারি −

[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]
[1, 1, 3]
[1, 3, 1]
[3, 1, 1]
[2, 3]
[3, 2]

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

যদি n 0 এর মত হয়, তাহলে
- প্রত্যাবর্তন 1
যদি n 1 এর মত হয়, তাহলে
- প্রত্যাবর্তন 1
k:=ন্যূনতম k, n
মেমো:=আকারের একটি ম্যাট্রিক্স (n+1) x (k+1)
র জন্য 0 থেকে k রেঞ্জের মধ্যে, করুন
- মেমো[r, 0]:=1, memo[r, 1]:=1, memo[r, 2]:=2
3 থেকে n রেঞ্জের জন্য, করুন
- মেমো[0, i]:=মেমো[0, i-1] + মেমো[0, i-2]
করুন
- 3 থেকে n রেঞ্জের জন্য, করুন
  - গণনা :=i/3 এর ভাগফল
  - যদি গণনা <=j হয়, তাহলে
    - মেমো[j, i]:=মেমো[j, i-1] + memo[j, i-2] + memo[j, i-3]
  - অন্যথায়,
    - মেমো[j, i]:=মেমো[j, i-1] + memo[j, i-2] + memo[j-1, i-3]
রিটার্ন মেমো[k, n]

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

উদাহরণ

class Solution:
   def solve(self, n, k):
      if n==0:
         return 1
      if n==1:
         return 1
         k= min(k,n)
         memo=[[0]*(n+1) for _ in range(k+1)]
         for r in range(k+1):
            memo[r][0]=1
            memo[r][1]=1
            memo[r][2]=2
            for i in range(3,n+1):
               memo[0][i]=memo[0][i-1]+memo[0][i-2]
               for j in range(1,k+1):
                  for i in range(3,n+1):
                     count = i//3
                     if count<=j:
                        memo[j][i]=memo[j][i-1]+memo[j][i-2]+memo[j][i-3]
                     else:
                        memo[j][i]=memo[j][i-1]+memo[j][i-2]+memo[j-1][i-3]
         return memo[k][n]
ob = Solution()
print(ob.solve(n = 5, k = 2))

ইনপুট

5, 2