D, 58

– Giải thích: Việc ko thể bước lên bậc 4 làm giảm số cách đi lên của bạn Alice. Bằng cách sử dụng công thức đệ quy và tính toán từng bước, ta có thể tìm ra số cách hợp lí để leo lên một cách chính xác

– Sử dụng công thức đệ quy:

Đặt f (n) là số cách để leo lên bậc n:

f (n) = f (n - 1) + f (n - 2) + f (n - 3)

Tuy nhiên do ko thể lên bậc 4, ta cần thêm điều kiện:

f (4) = 0

Bắt đầu tính từ:

•f (1) = 1 (chỉ có 1 cách: 1 bước)

•f (2) = 2 (chỉ có 2 cách: 1+1 hoặc

2)

•f (3) = 4 (chỉ có 4 cách: 1+1+1, 1+2, 2+1, 3)

Bây giờ ta tính tiếp đến bậc 9:

f (4) = 0

• 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

Vậy nên số cách mà Alice có thể đi hết cầu thang 9 bậc là 58

Chúc cậu học tốt