Climbing Stairs - The Gateway to DP

"Hiểu Climbing Stairs = Hiểu 50% các bài DP trong interview." - HPN

Problem Statement

Bạn đang leo cầu thang có n bậc. Mỗi lần, bạn có thể leo 1 hoặc 2 bậc.

Câu hỏi: Có bao nhiêu cách khác nhau để leo lên đến đỉnh?

Input: n = 4
Output: 5

Các cách:
1. 1 + 1 + 1 + 1
2. 1 + 1 + 2
3. 1 + 2 + 1
4. 2 + 1 + 1
5. 2 + 2

Phân Tích DP

Nhận diện DP patterns

Checklist	Có?	Giải thích
Overlapping Subproblems	✅	`ways(3)` cần `ways(2)` và `ways(1)`, nhiều lần
Optimal Substructure	✅	`ways(n) = ways(n-1) + ways(n-2)`
"Count ways" signal	✅	Đề bài hỏi "bao nhiêu cách"

📘 Core Insight

Để đến bậc thứ n, bạn có thể:

Từ bậc n-1 bước 1 bước, HOẶC
Từ bậc n-2 bước 2 bước

→ ways(n) = ways(n-1) + ways(n-2)

Đây chính xác là Fibonacci!

Recursion Tree (Tại sao cần DP)

🎯 THE WASTE

climb(3) tính 2 lần
climb(2) tính 3 lần
Với N lớn: Exponential time!

Từng Bước Implementation

Step 1: Naive Recursion - O(2^N) ❌

python

def climb_naive(n: int) -> int:
    """
    ❌ BRUTE FORCE - Chỉ để hiểu vấn đề.
    Time: O(2^N)
    Space: O(N) call stack
    """
    if n <= 2:
        return n  # 1 bậc → 1 cách, 2 bậc → 2 cách
    
    return climb_naive(n - 1) + climb_naive(n - 2)

Step 2: Top-Down Memoization - O(N) ✅

python

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_memo(n: int) -> int:
    """
    ✅ PYTHONIC - Dùng decorator có sẵn.
    Time: O(N)
    Space: O(N)
    """
    if n <= 2:
        return n
    
    return climb_memo(n - 1) + climb_memo(n - 2)

Step 3: Bottom-Up Tabulation - O(N) ✅

python

def climb_tabulation(n: int) -> int:
    """
    ✅ CLASSIC DP - Dễ debug, no stack overflow.
    Time: O(N)
    Space: O(N)
    """
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1  # 1 bậc → 1 cách
    dp[2] = 2  # 2 bậc → 2 cách
    
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

Step 4: Space-Optimized - O(1) ✅✅

python

def climb_optimized(n: int) -> int:
    """
    ✅✅ PRODUCTION-READY - Tối ưu space.
    Time: O(N)
    Space: O(1)
    
    Key insight: Chỉ cần 2 giá trị trước đó!
    """
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2  # dp[1], dp[2]
    
    for _ in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1

Complexity Analysis

Approach	Time	Space	n=50 (calls)
Naive	$O (2^{N})$	$O (N)$	~1.1 triệu tỷ
Memoization	$O (N)$	$O (N)$	50
Tabulation	$O (N)$	$O (N)$	50
Space-Optimized	$O (N)$	$O (1)$	50

Production Code

python

# HPN Engineering Standard
# Implementation: Climbing Stairs - All Approaches

from functools import lru_cache
from typing import List
import time


# ============================================
# CORE IMPLEMENTATIONS
# ============================================

def climb_naive(n: int) -> int:
    """❌ O(2^N) - Educational only."""
    if n <= 2:
        return n
    return climb_naive(n - 1) + climb_naive(n - 2)


@lru_cache(maxsize=None)
def climb_memo(n: int) -> int:
    """✅ O(N) time, O(N) space - Pythonic."""
    if n <= 2:
        return n
    return climb_memo(n - 1) + climb_memo(n - 2)


def climb_tabulation(n: int) -> int:
    """✅ O(N) time, O(N) space - Classic DP."""
    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]


def climb_optimized(n: int) -> int:
    """✅✅ O(N) time, O(1) space - Production."""
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2
    
    for _ in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1


# ============================================
# VARIANTS (INTERVIEW EXTENSIONS)
# ============================================

def climb_k_steps(n: int, k: int) -> int:
    """
    Variant: Có thể leo 1, 2, ..., k bước mỗi lần.
    
    Time: O(N * K)
    Space: O(N) - có thể tối ưu thành O(K)
    """
    if n == 0:
        return 1
    
    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]


def climb_with_cost(cost: List[int]) -> int:
    """
    Variant: Min Cost Climbing Stairs (LeetCode 746)
    Mỗi bậc có cost, tìm min cost để đến đỉnh.
    
    Time: O(N)
    Space: O(1)
    """
    n = len(cost)
    
    # Có thể bắt đầu từ bậc 0 hoặc 1
    prev2, prev1 = cost[0], cost[1]
    
    for i in range(2, n):
        current = cost[i] + min(prev1, prev2)
        prev2, prev1 = prev1, current
    
    # Có thể kết thúc từ bậc n-1 hoặc n-2
    return min(prev1, prev2)


def climb_paths(n: int) -> List[List[int]]:
    """
    Variant: Liệt kê TẤT CẢ các cách đi (không chỉ đếm).
    
    Time: O(2^N) - Vì số cách tăng theo Fibonacci
    Space: O(2^N) - Lưu tất cả paths
    
    ⚠️ Chỉ dùng khi N nhỏ!
    """
    if n == 0:
        return [[]]
    if n == 1:
        return [[1]]
    if n == 2:
        return [[1, 1], [2]]
    
    paths = []
    
    # Thêm 1 bước vào tất cả paths của (n-1)
    for path in climb_paths(n - 1):
        paths.append(path + [1])
    
    # Thêm 2 bước vào tất cả paths của (n-2)
    for path in climb_paths(n - 2):
        paths.append(path + [2])
    
    return paths


# ============================================
# USAGE & DEMO
# ============================================

if __name__ == "__main__":
    n = 10
    
    print(f"=== Climbing Stairs: {n} bậc ===\n")
    
    # Basic
    print(f"Số cách đi (optimized): {climb_optimized(n)}")
    
    # K-steps variant
    k = 3
    print(f"Số cách đi (1-{k} bước): {climb_k_steps(n, k)}")
    
    # Min cost variant
    cost = [10, 15, 20, 5, 8, 12, 3, 7, 11, 9]
    print(f"Min cost để leo {len(cost)} bậc: {climb_with_cost(cost)}")
    
    # List all paths (chỉ với n nhỏ)
    small_n = 4
    paths = climb_paths(small_n)
    print(f"\nTất cả {len(paths)} cách leo {small_n} bậc:")
    for i, path in enumerate(paths, 1):
        print(f"  {i}. {' + '.join(map(str, path))} = {sum(path)}")

Interview Variants

Variant	Thay đổi	Signal
K Steps	Leo 1→k bước	"At most k steps"
Min Cost	Có cost mỗi bậc	"Minimum cost"
List Paths	Liệt kê tất cả cách	"All possible ways"
Forbidden Steps	Một số bậc bị cấm	"Cannot step on..."
Variable Steps	Mỗi bậc có list steps khác nhau	"From step i, can go to..."

💡 HPN's Interview Tip

Khi gặp bài toán "Count ways", hãy:

Xác định state: dp[i] = số cách đến vị trí i
Xác định transition: Từ đâu có thể đến i?
Xác định base case: dp[0], dp[1] = ?
Code: Top-down hoặc Bottom-up
Optimize: Có thể giảm space không?

LeetCode 70: Climbing Stairs
LeetCode 746: Min Cost Climbing Stairs
LeetCode 198: House Robber (tương tự nhưng không liên tiếp)
LeetCode 509: Fibonacci Number

Climbing Stairs - The Gateway to DP ​

Problem Statement ​

Phân Tích DP ​

Nhận diện DP patterns ​

Recursion Tree (Tại sao cần DP) ​

Từng Bước Implementation ​

Step 1: Naive Recursion - O(2^N) ❌ ​

Step 2: Top-Down Memoization - O(N) ✅ ​

Step 3: Bottom-Up Tabulation - O(N) ✅ ​

Step 4: Space-Optimized - O(1) ✅✅ ​

Complexity Analysis ​

Production Code ​

Interview Variants ​

Related Problems ​

Climbing Stairs - The Gateway to DP

Problem Statement

Phân Tích DP

Nhận diện DP patterns

Recursion Tree (Tại sao cần DP)

Từng Bước Implementation

Step 1: Naive Recursion - O(2^N) ❌

Step 2: Top-Down Memoization - O(N) ✅

Step 3: Bottom-Up Tabulation - O(N) ✅

Step 4: Space-Optimized - O(1) ✅✅

Complexity Analysis

Production Code

Interview Variants

Related Problems