Climbing Stairs — Bước đệm vào Dynamic Programming

Năm 2019, một ứng viên senior tại Google được hỏi bài Climbing Stairs trong vòng phone screen. Không phải vì bài toán khó — mà vì interviewer muốn đánh giá một điều: ứng viên có thể nhận ra cấu trúc bài toán con chồng lấp trong chưa đầy 2 phút không? Ứng viên đó đã trượt, không phải vì thiếu kỹ năng code, mà vì thiếu tư duy DP.

Climbing Stairs là bài toán tưởng đơn giản nhất trong DP, nhưng nó chứa đựng toàn bộ DNA của kỹ thuật này: nhận diện overlapping subproblems, xây dựng công thức truy hồi, và tối ưu space từ O(n) xuống O(1). Nếu bạn thực sự hiểu Climbing Stairs, bạn đã nắm được 50% pattern của mọi bài DP trong interview.

Bài toán: có cầu thang n bậc, mỗi lần bạn leo 1 hoặc 2 bậc. Hỏi có bao nhiêu cách khác nhau để lên đến đỉnh?

Bức tranh tư duy

Hãy tưởng tượng bạn đứng trước cầu thang chung cư ở Sài Gòn. Mỗi bước chân, bạn chọn bước 1 bậc hoặc nhảy 2 bậc. Để đến bậc thứ 5, bạn nhất định phải đi qua bậc thứ 4 (rồi bước 1) hoặc bậc thứ 3 (rồi nhảy 2). Không có con đường nào khác.

Đây chính là Optimal Substructure: số cách đến bậc n = số cách đến bậc (n-1) + số cách đến bậc (n-2). Và đó chính xác là dãy Fibonacci.

Bậc:    0   1   2   3   4   5   6   7
Cách:   1   1   2   3   5   8  13  21
                              ↑
                        Fibonacci!

Cây đệ quy cho climb(5):
                    climb(5)
                   /         \
              climb(4)      climb(3)     ← climb(3) tính 2 LẦN
             /      \       /      \
        climb(3)  climb(2) climb(2) climb(1)  ← climb(2) tính 3 LẦN
        /    \
   climb(2) climb(1)

→ Không dùng DP: O(2^n) — hàng triệu tỷ phép tính cho n=50
→ Dùng DP: O(n) — chỉ 50 phép tính

Nhận diện nhanh: khi đề bài hỏi "bao nhiêu cách" (count ways), gần như chắc chắn đó là DP.

Cốt lõi kỹ thuật

Công thức truy hồi (Recurrence Relation)

dp[i] = dp[i-1] + dp[i-2]

Base cases:
  dp[0] = 1  (đứng tại chỗ = 1 cách)
  dp[1] = 1  (1 bậc = 1 cách)
  dp[2] = 2  (1+1 hoặc 2)

Approach 1: Naive Recursion — O(2^n) ❌

Chỉ để minh họa tại sao cần DP. Tuyệt đối không dùng trong production.

C++PythonJavaGo

cpp

int climbNaive(int n) {
    if (n <= 2) return n;
    return climbNaive(n - 1) + climbNaive(n - 2);
}

python

def climb_naive(n: int) -> int:
    if n <= 2:
        return n
    return climb_naive(n - 1) + climb_naive(n - 2)

java

public int climbNaive(int n) {
    if (n <= 2) return n;
    return climbNaive(n - 1) + climbNaive(n - 2);
}

func climbNaive(n int) int {
    if n <= 2 {
        return n
    }
    return climbNaive(n-1) + climbNaive(n-2)
}

Approach 2: Top-Down Memoization — O(n) time, O(n) space

C++PythonJavaGo

cpp

int climbMemo(int n, vector<int>& memo) {
    if (n <= 2) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = climbMemo(n - 1, memo) + climbMemo(n - 2, memo);
    return memo[n];
}

int climbStairs(int n) {
    vector<int> memo(n + 1, -1);
    return climbMemo(n, memo);
}

python

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_memo(n: int) -> int:
    if n <= 2:
        return n
    return climb_memo(n - 1) + climb_memo(n - 2)

java

public int climbStairs(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return climbMemo(n, memo);
}

private int climbMemo(int n, int[] memo) {
    if (n <= 2) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = climbMemo(n - 1, memo) + climbMemo(n - 2, memo);
    return memo[n];
}

func climbStairs(n int) int {
    memo := make(map[int]int)
    return climbMemo(n, memo)
}

func climbMemo(n int, memo map[int]int) int {
    if n <= 2 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = climbMemo(n-1, memo) + climbMemo(n-2, memo)
    return memo[n]
}

Approach 3: Bottom-Up Tabulation — O(n) time, O(n) space

C++PythonJavaGo

cpp

int climbStairs(int n) {
    if (n <= 2) return n;
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

python

def climb_tabulation(n: int) -> int:
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

java

public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    dp := make([]int, n+1)
    dp[1], dp[2] = 1, 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

Approach 4: Space-Optimized — O(n) time, O(1) space ✅

Nhận xét quan trọng: dp[i] chỉ phụ thuộc vào dp[i-1] và dp[i-2]. Ta chỉ cần 2 biến thay vì cả mảng.

C++PythonJavaGo

cpp

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

python

def climb_optimized(n: int) -> int:
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

java

public int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    prev2, prev1 := 1, 2
    for i := 3; i <= n; i++ {
        curr := prev1 + prev2
        prev2 = prev1
        prev1 = curr
    }
    return prev1
}

Thực chiến

Tình huống: K-Step Climbing — Mở rộng cho production

Bối cảnh: Hệ thống game cần tính số cách di chuyển khi nhân vật có thể bước 1 đến k bước mỗi lượt. Đây là generalized version thường gặp trong interview follow-up.

Mục tiêu: Từ bài cơ bản (1 hoặc 2 bước) mở rộng sang k bước tùy ý.

C++PythonJavaGo

cpp

int climbKSteps(int n, int k) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int step = 1; step <= min(k, i); step++) {
            dp[i] += dp[i - step];
        }
    }
    return dp[n];
}

python

def climb_k_steps(n: int, k: int) -> int:
    """
    Generalized: leo 1 đến k bước mỗi lần.
    Time: O(n * k), Space: O(n)
    """
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        for step in range(1, min(k, i) + 1):
            dp[i] += dp[i - step]
    return dp[n]

java

public int climbKSteps(int n, int k) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int step = 1; step <= Math.min(k, i); step++) {
            dp[i] += dp[i - step];
        }
    }
    return dp[n];
}

func climbKSteps(n, k int) int {
    dp := make([]int, n+1)
    dp[0] = 1
    for i := 1; i <= n; i++ {
        maxStep := k
        if i < k {
            maxStep = i
        }
        for step := 1; step <= maxStep; step++ {
            dp[i] += dp[i-step]
        }
    }
    return dp[n]
}

Phân tích:

Công thức mở rộng: dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k]
Khi k=2, chính xác là bài gốc
Trade-off: Time tăng từ O(n) lên O(n×k), nhưng vẫn polynomial

Tình huống: Min Cost Climbing Stairs

Bối cảnh: Mỗi bậc thang có chi phí khác nhau. Tìm chi phí tối thiểu để leo lên đỉnh. Đây là biến thể xuất hiện thường xuyên trong interview (LeetCode 746).

C++PythonJavaGo

cpp

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    int prev2 = cost[0], prev1 = cost[1];
    for (int i = 2; i < n; i++) {
        int curr = cost[i] + min(prev1, prev2);
        prev2 = prev1;
        prev1 = curr;
    }
    return min(prev1, prev2);
}

python

def min_cost_climbing(cost: list[int]) -> int:
    """Min cost to reach top. Time: O(n), Space: O(1)."""
    prev2, prev1 = cost[0], cost[1]
    for i in range(2, len(cost)):
        curr = cost[i] + min(prev1, prev2)
        prev2, prev1 = prev1, curr
    return min(prev1, prev2)

java

public int minCostClimbingStairs(int[] cost) {
    int prev2 = cost[0], prev1 = cost[1];
    for (int i = 2; i < cost.length; i++) {
        int curr = cost[i] + Math.min(prev1, prev2);
        prev2 = prev1;
        prev1 = curr;
    }
    return Math.min(prev1, prev2);
}

func minCostClimbingStairs(cost []int) int {
    prev2, prev1 := cost[0], cost[1]
    for i := 2; i < len(cost); i++ {
        curr := cost[i] + min(prev2, prev1)
        prev2 = prev1
        prev1 = curr
    }
    return min(prev1, prev2)
}

Sai lầm điển hình

❌ Sai lầm 1: Dùng recursion thuần không memoization

Vấn đề: Với n=45, hàm mất hàng chục giây. Với n=50, treo máy.

python

# SAI: Exponential time O(2^n)
def climb(n):
    if n <= 2:
        return n
    return climb(n - 1) + climb(n - 2)

Tại sao sai: Mỗi lần gọi tạo 2 nhánh đệ quy. climb(3) được tính lại hàng triệu lần. Trong production, đây là bug performance nghiêm trọng — request timeout, CPU spike, autoscaling trigger vô nghĩa.

python

# ĐÚNG: Dùng memoization hoặc bottom-up
from functools import lru_cache

@lru_cache(maxsize=None)
def climb(n):
    if n <= 2:
        return n
    return climb(n - 1) + climb(n - 2)

❌ Sai lầm 2: Base case sai

Vấn đề: Quên xử lý n=0 hoặc n=1, hoặc nhầm giá trị base case.

python

# SAI: dp[0] = 0 thay vì dp[0] = 1
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
# Khi n=0, trả về 0 thay vì 1

Tại sao sai: dp[0] = 1 vì "đứng tại bậc 0 = 1 cách (không làm gì)". Sai base case dẫn đến sai toàn bộ bảng DP — lỗi cascade mà rất khó debug vì kết quả "gần đúng".

python

# ĐÚNG: Base case chính xác
dp[0] = 1  # 1 cách: không bước
dp[1] = 1  # 1 cách: bước 1
dp[2] = 2  # 2 cách: 1+1 hoặc 2

❌ Sai lầm 3: Integer overflow với n lớn

Vấn đề: Fibonacci tăng theo exponential. Với n=93, giá trị vượt quá long long trong C++.

cpp

// SAI: Không kiểm soát overflow
int climbStairs(int n) {
    // Với n > 46, int overflow
    // Với n > 93, long long overflow
}

Tại sao sai: Production code xử lý input lớn không kiểm soát sẽ trả về kết quả sai âm thầm (silent corruption) — nguy hiểm hơn cả crash.

cpp

// ĐÚNG: Dùng kiểu dữ liệu phù hợp hoặc modular arithmetic
long long climbStairs(int n) {
    // Hoặc return dp[n] % MOD nếu đề yêu cầu
    const int MOD = 1e9 + 7;
}

Under the Hood

Hiệu năng

Approach	Time	Space	n=50 (operations)	Ghi chú
Naive Recursion	O(2^n)	O(n)	~1.1 × 10¹⁵	Chỉ cho giáo dục
Memoization	O(n)	O(n)	50	Stack overflow risk khi n lớn
Tabulation	O(n)	O(n)	50	An toàn, dễ debug
Space-Optimized	O(n)	O(1)	50	Production choice

Tại sao Space-Optimized là lựa chọn production?

Kỹ thuật rolling variable áp dụng được khi dp[i] chỉ phụ thuộc vào một số lượng cố định trạng thái trước đó. Trong Climbing Stairs, chỉ cần 2 giá trị liền trước.

Bảng DP đầy đủ:
dp[0]=1  dp[1]=1  dp[2]=2  dp[3]=3  dp[4]=5  dp[5]=8
                                     ↑
                               Chỉ cần 2 ô trước

Rolling variable:
Bước 1: prev2=1, prev1=1
Bước 2: prev2=1, prev1=2  (curr = 1+1 = 2)
Bước 3: prev2=2, prev1=3  (curr = 2+1 = 3)
Bước 4: prev2=3, prev1=5  (curr = 3+2 = 5)
Bước 5: prev2=5, prev1=8  (curr = 5+3 = 8) ✓

Kết nối Fibonacci — Matrix Exponentiation O(log n)

Với n cực lớn (hàng tỷ), có thể dùng nhân ma trận nhanh:

| F(n+1) |   | 1  1 |^n   | F(1) |
| F(n)   | = | 1  0 |   × | F(0) |

Kết hợp với fast exponentiation, đạt O(log n). Tuy nhiên trong thực tế, O(n) với space O(1) đã đủ cho hầu hết use case.

Trade-offs

Yếu tố	Memoization	Tabulation	Space-Optimized
Dễ code	✅ Dùng decorator	Trung bình	Cần suy nghĩ
Debug	Khó trace	Dễ in bảng	Không có bảng
Stack safe	❌ n lớn crash	✅	✅
Traceback	Không cần	Có thể	Không thể
Production	Prototype	General	Best choice

Checklist ghi nhớ

✅ Checklist triển khai

Nhận diện bài toán

[ ] Đề bài hỏi "bao nhiêu cách" → signal DP counting
[ ] Kiểm tra overlapping subproblems (vẽ cây đệ quy)
[ ] Kiểm tra optimal substructure (nghiệm lớn = tổng hợp nghiệm con)

Xây dựng lời giải

[ ] Định nghĩa state: dp[i] đại diện cho gì?
[ ] Viết công thức truy hồi: dp[i] phụ thuộc vào gì?
[ ] Xác định base case chính xác (dp[0], dp[1])
[ ] Chọn approach: top-down hay bottom-up?

Tối ưu hóa

[ ] Quan sát dp[i] phụ thuộc bao nhiêu trạng thái trước → rolling variable
[ ] Từ O(n) space → O(1) space nếu chỉ cần k trạng thái
[ ] Kiểm tra integer overflow với n lớn

Mở rộng

[ ] K-steps variant: tổng quát hóa số bước
[ ] Min cost variant: thêm weight vào mỗi bậc
[ ] Forbidden steps: loại bỏ một số bậc
[ ] List all paths: liệt kê thay vì đếm (backtracking)

Bài tập luyện tập

Bài 1: Climbing Stairs cơ bản — Foundation

Đề bài: Cho n bậc thang, mỗi lần leo 1 hoặc 2 bậc. Tính số cách leo lên đỉnh.

Input: n = 5
Output: 8

Input: n = 10
Output: 89

🧠 Quiz

Câu hỏi kiểm tra: Với n=6, climb(6) = ?

[ ] A. 8
[ ] B. 11
[x] C. 13
[ ] D. 21 Giải thích: dp = [1, 1, 2, 3, 5, 8, 13]. climb(6) = climb(5) + climb(4) = 8 + 5 = 13. Đáp án D (21) là climb(8), hay mắc lỗi nhầm index.

💡 Gợi ý

Bắt đầu bằng brute force recursion, quan sát các nhánh trùng lặp
dp[i] = dp[i-1] + dp[i-2] — chính xác là Fibonacci
Tối ưu space: chỉ cần 2 biến

✅ Lời giải

python

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

Phân tích: Time O(n), Space O(1). Edge case: n=0 → 1, n=1 → 1.

Bài 2: Min Cost Climbing Stairs — Intermediate

Đề bài: Mảng cost[i] là chi phí đứng trên bậc i. Bạn có thể bắt đầu từ bậc 0 hoặc 1. Tìm chi phí tối thiểu để leo qua đỉnh cầu thang.

Input: cost = [10, 15, 20]
Output: 15 (bắt đầu từ bậc 1, bước 2 bậc)

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6

🧠 Quiz

Câu hỏi kiểm tra: Với cost = [1, 2, 3], chi phí tối thiểu là?

[x] A. 2
[ ] B. 3
[ ] C. 4
[ ] D. 1 Giải thích: Bắt đầu từ bậc 1 (cost=2), nhảy 2 bậc qua đỉnh. Tổng = 2. Bắt đầu từ bậc 0 cần ít nhất 1+3=4 hoặc 1+2=3. Đáp án A là tối ưu.

💡 Gợi ý

dp[i] = cost[i] + min(dp[i-1], dp[i-2])
Kết quả cuối cùng: min(dp[n-1], dp[n-2]) vì có thể kết thúc từ 2 vị trí
Tối ưu space giống hệt bài gốc

✅ Lời giải

python

def min_cost_climbing_stairs(cost: list[int]) -> int:
    prev2, prev1 = cost[0], cost[1]
    for i in range(2, len(cost)):
        curr = cost[i] + min(prev1, prev2)
        prev2, prev1 = prev1, curr
    return min(prev1, prev2)

Phân tích: Time O(n), Space O(1). Biến thể quan trọng — thêm "weight" vào mỗi state.

Bài 3: K-Steps with Forbidden — Advanced

Đề bài: Cho n bậc, mỗi lần leo 1 đến k bậc, nhưng một số bậc bị "cấm" (không được đứng lên). Tính số cách leo lên đỉnh.

Input: n = 6, k = 3, forbidden = {3, 5}
Output: 2 (cách: 1+2+2+1, 2+2+1+1)

💡 Gợi ý

Dựa trên K-steps: dp[i] = sum(dp[i-step]) cho step 1..k
Thêm điều kiện: nếu i ∈ forbidden thì dp[i] = 0
Base case không đổi: dp[0] = 1

✅ Lời giải

python

def climb_k_forbidden(n: int, k: int, forbidden: set[int]) -> int:
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        if i in forbidden:
            dp[i] = 0
            continue
        for step in range(1, min(k, i) + 1):
            dp[i] += dp[i - step]
    return dp[n]

Phân tích: Time O(n×k), Space O(n). Pattern: DP + constraint filtering. Xuất hiện thường xuyên trong variant interview.

Liên kết học tiếp

Từ khóa glossary: climbing stairs, fibonacci, dynamic programming, memoization, tabulation, space optimization, rolling variable, recurrence relation

Tìm kiếm liên quan: leo cầu thang, bài toán đếm cách, DP cơ bản, tối ưu không gian O(1)

Climbing Stairs — Bước đệm vào Dynamic Programming ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Công thức truy hồi (Recurrence Relation) ​

Approach 1: Naive Recursion — O(2^n) ❌ ​

Approach 2: Top-Down Memoization — O(n) time, O(n) space ​

Approach 3: Bottom-Up Tabulation — O(n) time, O(n) space ​

Approach 4: Space-Optimized — O(n) time, O(1) space ✅ ​

Thực chiến ​

Tình huống: K-Step Climbing — Mở rộng cho production ​

Tình huống: Min Cost Climbing Stairs ​

Sai lầm điển hình ​

❌ Sai lầm 1: Dùng recursion thuần không memoization ​

❌ Sai lầm 2: Base case sai ​

❌ Sai lầm 3: Integer overflow với n lớn ​

Under the Hood ​

Hiệu năng ​

Tại sao Space-Optimized là lựa chọn production? ​

Kết nối Fibonacci — Matrix Exponentiation O(log n) ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Climbing Stairs cơ bản — Foundation ​

Bài 2: Min Cost Climbing Stairs — Intermediate ​

Bài 3: K-Steps with Forbidden — Advanced ​

Liên kết học tiếp ​

Climbing Stairs — Bước đệm vào Dynamic Programming

Bức tranh tư duy

Cốt lõi kỹ thuật

Công thức truy hồi (Recurrence Relation)

Approach 1: Naive Recursion — O(2^n) ❌

Approach 2: Top-Down Memoization — O(n) time, O(n) space

Approach 3: Bottom-Up Tabulation — O(n) time, O(n) space

Approach 4: Space-Optimized — O(n) time, O(1) space ✅

Thực chiến

Tình huống: K-Step Climbing — Mở rộng cho production

Tình huống: Min Cost Climbing Stairs

Sai lầm điển hình

❌ Sai lầm 1: Dùng recursion thuần không memoization

❌ Sai lầm 2: Base case sai

❌ Sai lầm 3: Integer overflow với n lớn

Under the Hood

Hiệu năng

Tại sao Space-Optimized là lựa chọn production?

Kết nối Fibonacci — Matrix Exponentiation O(log n)

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Climbing Stairs cơ bản — Foundation

Bài 2: Min Cost Climbing Stairs — Intermediate

Bài 3: K-Steps with Forbidden — Advanced

Liên kết học tiếp