Climbing Stairs: từ recursion mũ xuống còn O(1) bộ nhớ

Lần đầu giải Climbing Stairs, tôi viết cái recursion hiển nhiên nhất, bấm submit, rồi ngồi nhìn nó bò. Cái time out đó chính là toàn bộ bài học. Đề đọc như một bài đếm, nhưng thật ra nó là Fibonacci khoác áo cầu thang — và một khi nhìn ra điều đó, mọi bước tối ưu phía sau đều là chuyện bắt buộc chứ chẳng có gì khôn khéo.

Đề bài gói trong một câu

Bạn leo cầu thang n bậc, mỗi lần bước 1 hoặc 2 bậc. Đếm số cách khác nhau để lên tới đỉnh. Ràng buộc duy nhất đáng để ý: n <= 45.

Cái cận đó là gợi ý, không phải chi tiết thừa. Đáp án tại n = 45 là số Fibonacci thứ 46 — lớn, nhưng vẫn vừa một số nguyên 64-bit, và n đủ nhỏ để gần như approach nào cũng chạy được. Câu hỏi thú vị là: nếu đây là một buổi code review chứ không phải cuộc thi, bạn sẽ viết bản nào?

Vì sao recursion naive đáng bị time out

Đứng ở bậc n và nhìn lại. Bạn tới đây hoặc từ bậc n-1 bằng một bước đơn, hoặc từ bậc n-2 bằng một bước đôi. Đó là hai cách duy nhất để đến, và chúng không bao giờ trùng nhau. Vậy số cách tách ra rất gọn:

ways(n) = ways(n-1) + ways(n-2), với ways(1) = 1 và ways(2) = 2.

Đó là công thức truy hồi, và bản dịch trực tiếp ra code là một đoạn thành thật:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

Nó cũng là O(2^n). Mỗi lời gọi đẻ ra hai lời gọi nữa, và cái cây đầy những phần lặp lại — ways(10) bị tính lại hàng nghìn lần trên đường đi xuống. Công thức thì đúng; còn cách thực thi đang làm lượng việc theo cấp số mũ cho một bài toán tuyến tính. Nó nên bị time out, và khi điều đó xảy ra, đó là thuật toán đang nói cho bạn biết nó chẳng có trí nhớ gì cả.

Memoize lại, chi phí sụp đổ ngay

Cho công thức truy hồi một chỗ để nhớ những đáp án đã tính, các nhánh con trùng lặp biến mất:

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}
        def ways(k: int) -> int:
            if k <= 2:
                return k
            if k not in memo:
                memo[k] = ways(k - 1) + ways(k - 2)
            return memo[k]
        return ways(n)

Bây giờ mỗi giá trị từ 1 đến n được tính đúng một lần: O(n) thời gian, O(n) bộ nhớ cho cache cộng với call stack.

Dù vậy, tôi hiếm khi ship bản này. Memoization là bước dạy học đúng đắn — nó cho bạn thấy chính xác bản naive đã phí phạm cái gì — nhưng với một công thức nông như thế này, recursion chẳng đem lại gì mà còn âm thầm rủi ro tràn stack. Bản viết lại bottom-up ngắn hơn và không có stack nào hết.

Bản tôi thực sự viết

Bạn không bao giờ cần cả bảng. Để tính bậc i bạn chỉ nhìn lại đúng hai bậc, nên giữ hai biến và đẩy chúng tiến lên:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev2, prev1 = 1, 2          # ways(1), ways(2)
        for _ in range(3, n + 1):
            prev2, prev1 = prev1, prev1 + prev2
        return prev1

Cùng dạng đó trong C#, cho lúc phỏng vấn nằm ở phía .NET:

public class Solution {
    public int ClimbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;    // ways(1), ways(2)
        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

Lần theo n = 5 bằng tay và nó vẫn thành thật: 1, 2, 3, 5, 8. Tám cách lên một cầu thang năm bậc. O(n) thời gian, O(1) bộ nhớ, không cấp phát, không recursion. Đây là bản tôi để lại trong codebase.

Khi nào mỗi bản xứng đáng có chỗ

Bốn lời giải không phải một bảng xếp hạng mà bản cuối luôn thắng. Chúng là một cái thang đánh đổi, và bạn dừng ở bậc nào tuỳ vào việc bạn đang tối ưu cho cái gì.

Approach	Thời gian	Bộ nhớ	Vì sao chọn
Recursion thuần	O(2^n)	O(n)	Không bao giờ — nhưng nó phát biểu công thức rõ nhất
Top-down + memo	O(n)	O(n)	Khi công thức phức tạp và bạn nghĩ theo kiểu top-down
Bottom-up có mảng	O(n)	O(n)	Khi sau đó bạn cần cả bảng (để dựng lại đường đi)
Hai biến cuộn	O(n)	O(1)	Mặc định cho công thức cửa sổ cố định

Bản dùng mảng đáng giữ trong đầu vì một lý do thật: vài bài yêu cầu bạn dựng lại đường đi chứ không chỉ đếm, và khi đó bạn cần mọi ô, không chỉ hai ô cuối.

Cái dạng bài, không phải cái bài

Climbing Stairs không đáng nhớ vì bản thân nó. Cái đáng giữ là cái dạng nó dạy: đáp án tại trạng thái n được dựng từ một cửa sổ giới hạn các đáp án trước đó. Khoảnh khắc một bài khớp với câu đó, bạn với tay tới DP kiểu biến cuộn và thường là xong.

Bạn gặp lại đúng bộ khung này, mỗi lần thêm một biến tấu:

• Min Cost Climbing Stairs (746) — cùng công thức, nhưng bạn tối thiểu hoá chi phí thay vì đếm.
• House Robber (198) — dp[i] = max(dp[i-1], dp[i-2] + nums[i]); cửa sổ y hệt, phép toán đổi.
• Decode Ways (91) — vẫn là "số cách đến vị trí n", nhưng các bước chuyển phụ thuộc vào ký tự, nên một số bước bị chặn.

Từ khoá tố cáo dạng bài gần như luôn là "có bao nhiêu cách" hoặc "chi phí tối thiểu để đến", đi kèm một ràng buộc đủ nhỏ để một lượt duyệt O(n) là quá đủ.

Nếu giữ lại một phản xạ từ bài này, hãy để nó là: khi đáp án tại n phụ thuộc vào một số cố định các đáp án trước, bạn gần như không cần mảng, và không bao giờ cần recursion. Climbing Stairs là chỗ rẻ nhất để rèn phản xạ đó trước khi các bài toán bắt đầu phản đòn.