Chương trình tìm bao nhiêu cách chúng ta có thể leo cầu thang (số bước tối đa nhiều nhất k lần) bằng Python

Giả sử chúng ta có một cầu thang với n bậc và chúng ta cũng có một số k khác, ban đầu chúng ta đang ở cầu thang 0 và chúng ta có thể leo lên 1, 2 hoặc 3 bậc cùng một lúc. nhưng chúng tôi chỉ có thể leo 3 bậc cầu thang nhiều nhất k lần. Bây giờ chúng ta phải tìm số cách chúng ta có thể leo lên cầu thang.

Vì vậy, nếu đầu vào là n =5, k =2, thì đầu ra sẽ là 13, vì có nhiều cách khác nhau để chúng ta có thể leo lên cầu thang -

• [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]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu n giống 0, thì
  • trả lại 1
• nếu n giống 1, thì
  • trả lại 1
• k:=tối thiểu của k, n
• memo:=ma trận có kích thước (n + 1) x (k + 1)
• đối với r trong phạm vi từ 0 đến k, thực hiện
  • memo [r, 0]:=1, memo [r, 1]:=1, memo [r, 2]:=2
• đối với tôi trong phạm vi từ 3 đến n, thực hiện
  • memo [0, i]:=memo [0, i-1] + memo [0, i-2]
• đối với j trong phạm vi từ 1 đến k, thực hiện
  • đối với tôi trong phạm vi từ 3 đến n, thực hiện
    • count:=thương số của i / 3
    • nếu đếm <=j, thì
      • memo [j, i]:=memo [j, i-1] + memo [j, i-2] + memo [j, i-3]
    • nếu không,
      • memo [j, i]:=memo [j, i-1] + memo [j, i-2] + memo [j-1, i-3]
• trả lại thư báo [k, n]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

5, 2

Đầu ra

13