Staircase (quy hoạch động) - bài này thường được hỏi trong các kỳ phỏng vấn của Amazon
Xem dạng PDF
Gửi bài giải
Điểm:
2,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Một chiếc cầu thang có N bậc. Mỗi bước, bạn được phép bước lên trên tối đa K bước. Hỏi có tất cả bao nhiều cách bước để đi hết cầu thang? (Tổng số bước đúng bằng N).
Đầu vào: Dòng duy nhất chứa 2 số nguyên N và K
Ràng buộc: 1<=N<=100000; 1<=K＜=100
Đầu ra: In ra đáp án tìm được trên một dòng theo modulo 10^9+7.
Input:
7 3
Output:
44
Bình luận