โปรแกรมหาจำนวนวิธีเดินขึ้นบันไดใน Python

บันได n ขั้น เดินได้ 1 หรือ 2 ขั้นต่อครั้ง หาจำนวนวิธีเดินถึงขั้น n (ลำดับขั้นตอนต่างกันนับคนละวิธี) mod 1e9+7

ตัวอย่าง: n=5 → 8 วิธี (Fibonacci)

Dynamic Programming

• dp[i]: วิธีเดินถึงขั้น i
• dp[1]=1, dp[i] = dp[i-1] + dp[i-2]
• คืน dp[n+1] % MOD

การนำไปใช้

MOD = 10**9 + 7

class Solution:
    def solve(self, n):
        dp = [0] * (n + 2)
        dp[1] = 1
        for i in range(2, n + 2):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1] % MOD

ob = Solution()
print(ob.solve(5))  # 8