Bậc Thang & Quy Hoạch Động 1 Chiều Cơ Bản

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Một cầu thang có N bậc. Mỗi bước bạn có thể bước lên 1 bậc hoặc 2 bậc. Hãy tính số cách khác nhau để bước từ chân cầu thang (bậc 0) lên tới bậc thứ N, kết quả chia lấy dư cho 10^9 + 7.

Dữ liệu vào (Input)
  • Một dòng duy nhất chứa số nguyên dương N (1 ≤ N ≤ 10^6).
Dữ liệu ra (Output)
  • In ra số cách bước lên bậc N theo modulo 1000000007.
Ví dụ mẫu
Sample Input 1
3
Sample Output 1
3
Sample Input 2
5
Sample Output 2
8
Draft saved