[70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/description/)

# 1. Tóm tắt đề bài

Cho cầu thang có $n$ bậc. Mỗi bước, bạn có thể trèo $1$ hoặc $2$ bậc một lúc.

Hỏi, có bao nhiêu cách để lên được bậc thứ $n$ (bạn đang ở mặt đất, có thể coi là bậc $0$).


### Giới hạn

$1 \le n \le 45$

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(n)$**

Để tính được số cách đi đến bậc $i$, ta có thể suy ra theo bước trước đó (trèo 1 hay 2 bước):

Số cách đi đến bậc $i$ = số cách đi đến bậc $i - 1$ + số cách đi đến bậc $i - 2$.

# 3. Lời giải chi tiết

Công thức đã có: gọi $f(i)$ là số cách trèo lên bậc thứ $i$. Ta có $f(i) = f(i - 1) + f(i - 2)$.

Ta xét base case cho các $i$ bé:

- $i = 0$ thì có một cách duy nhất: đứng nguyên tại chỗ, không trèo => $f(i) = 1$.
- $i = 1$ thì có một cách duy nhất: bước $1$ bậc từ mặt đất. => $f(i) = 1$.
- $i = 2$ thì có hai cách: bước $1$ bậc từ $1$ và trèo $2$ bậc từ $0$ => $f(i) = 2$.

Các $i$ lớn hơn tính theo công thức đã cho.

### Độ phức tạp thuật toán

Thời gian: $O(n)$.
Bộ nhớ mở rộng: $O(n)$.

Code mẫu: https://leetcode.com/problems/climbing-stairs/submissions/1149328139/

# 4. Đánh giá:

Bài tập này có pattern tính toán giống với dãy Fibonacci. Dưới đây là một số bài tập gợi ý liên quan:

[1137. N-th Tribonacci Number](https://leetcode.com/problems/n-th-tribonacci-number/description/)
[2244. Minimum Rounds to Complete All Tasks](https://leetcode.com/problems/minimum-rounds-to-complete-all-tasks/description/)
[2320. Count Number of Ways to Place Houses](https://leetcode.com/problems/count-number-of-ways-to-place-houses/description/)