Chương trình tìm số cách leo cầu thang trong Python

Cho một cầu thang n bậc, có thể leo 1 hoặc 2 bậc mỗi lần. Tìm số cách duy nhất để leo lên đỉnh. Thứ tự các bước quan trọng, mỗi thứ tự khác nhau tính là một cách. Nếu kết quả lớn, lấy modulo 10^9 + 7.

Ví dụ, n = 5, đầu ra là 8. Các cách:

• 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

Các bước giải quyết:

• Tạo mảng dp kích thước n+1 khởi tạo 0.
• dp[1] = 1.
• Với i từ 2 đến n+1: dp[i] = dp[i-1] + dp[i-2].
• Trả về phần tử cuối của dp modulo m.

Ví dụ minh họa

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