Chương trình tìm bao nhiêu cách chúng ta có thể leo cầu thang bằng Python

Giả sử chúng ta có một cầu thang với n bậc và chúng ta có thể leo lên 1 hoặc 2 bậc cùng một lúc. Chúng ta phải xác định một hàm trả về số cách duy nhất mà chúng ta có thể leo lên cầu thang.

Thứ tự của các bước không được thay đổi, vì vậy mỗi thứ tự khác nhau của các bước được tính là một cách. Nếu câu trả lời là rất lớn thì hãy sửa đổi kết quả bằng 10 ^ 9 + 7

Vì vậy, nếu đầu vào là n =5, thì đầu ra sẽ là 8, vì có 8 cách duy nhất -

• 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

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

• dp:=một mảng có kích thước n + 1 và điền bằng 0
• dp [1]:=1
• đối với tôi trong phạm vi từ 2 đến n + 1, hãy thực hiện
  • dp [i]:=dp [i-1] + dp [i-2]
• trả về phần tử cuối cùng của dp mod m

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

Ví dụ

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

Đầu vào

5

Đầu ra

8