Một cầu thang có 9 bậc. Alice có thể bước lên 1 bậc, 2 bậc hoặc 3 bậc mỗi lần. Biết rằng bậc thứ 4 không thể bước lên được do bị hỏng. Hỏi có bao nhiêu cách để Alice đi hết cầu thang?
- A. 44
- B. 125
- C. 149
- D. 58 ✓
Đáp án: D. 58
Gọi f(n) là số cách để lên đến bậc n. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 4. f(4) = 0 (do bậc 4 hỏng). f(5) = f(4) + f(3) + f(2) = 0 + 4 + 2 = 6. f(6) = f(5) + f(4) + f(3) = 6 + 0 + 4 = 10. f(7) = f(6) + f(5) + f(4) = 10 + 6 + 0 = 16. f(8) = f(7) + f(6) + f(5) = 16 + 10 + 6 = 32. f(9) = f(8) + f(7) + f(6) = 32 + 16 + 10 = 58.