70. Climbing Stairs

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
2244. Minimum Rounds to Complete All Tasks
2320. Count Number of Ways to Place Houses