Quy hoạch động nhập môn — Dynamic Programming Phase 1

Năm 2019, một ứng viên senior tại Google bị trượt phỏng vấn vì giải bài Climbing Stairs bằng recursion thuần — O(2^n) — mà không nhận ra đây là bài DP kinh điển. Dynamic Programming không phải magic — nó chỉ là "đừng tính lại thứ bạn đã tính rồi." Bài này dạy bạn nhận diện DP pattern và 4 cấp độ tối ưu: từ O(2^n) đến O(1) space.

Đây là Phase 1 teaser — đủ để nhận diện DP và giải 80% bài DP cơ bản trong phỏng vấn. Phase 2 sẽ mở rộng sang Knapsack, LCS, Bitmask DP, Tree DP.

🎯 Mục tiêu

Sau bài này, bạn sẽ:

Hiểu 2 trụ cột: optimal substructure + overlapping subproblems
Biến recursion O(2^n) → memoization O(n) → tabulation O(n) → O(1) space
Giải Climbing Stairs và nhận ra pattern Fibonacci ẩn bên trong
Nhận diện "đây có phải bài DP không?" với 4 câu hỏi kiểm tra
Biết rõ phạm vi Phase 1 vs Phase 2 — không mò mẫm thiếu định hướng

Bức tranh tư duy — DP như "ghi chú thông minh"

Bạn đang làm bài kiểm tra và nhận ra câu 5 cần kết quả từ câu 3. Thay vì tính lại từ đầu, bạn lật lại trang trước xem kết quả đã ghi. ĐÓ là Dynamic Programming — ghi nhớ kết quả đã tính để không phải tính lại.

Thuật ngữ "Dynamic Programming" do nhà toán học Richard Bellman đặt ra vào những năm 1950 — và chính ông thừa nhận cái tên này nghe "cool" chứ chẳng mô tả gì bản chất kỹ thuật. Bản chất thực sự chỉ gói gọn trong hai điều kiện: bài toán có cấu trúc con tối ưu, và các bài toán con bị trùng lặp.

Hai trụ cột của DP

Trụ cột 1: Optimal Substructure

Giải pháp tối ưu của bài toán lớn được xây dựng từ giải pháp tối ưu của bài toán con.

Ví dụ: đường đi ngắn nhất A→C qua B = shortest(A→B) + shortest(B→C). Nếu shortest(A→B) thay đổi thì shortest(A→C) cũng phải cập nhật. Bài toán lớn phụ thuộc trực tiếp vào bài toán con.

Trụ cột 2: Overlapping Subproblems

Cùng một bài toán con xuất hiện nhiều lần trong quá trình giải.

Khi bạn tính Fibonacci(5), bạn cần Fibonacci(3) ở hai nhánh khác nhau của cây đệ quy. Nếu không ghi nhớ, máy sẽ tính Fibonacci(3) lặp đi lặp lại — lãng phí.

Khi nào dùng gì?

✅ Optimal Substructure + Overlapping Subproblems → Dynamic Programming
✅ Optimal Substructure + KHÔNG Overlapping       → Greedy hoặc Divide-and-Conquer
❌ KHÔNG Optimal Substructure                     → Thử approach khác (backtracking, brute force)

💡 Quy tắc nhận diện nhanh

Nếu bài toán hỏi "minimum", "maximum", "count ways", hoặc "yes/no feasibility" — và bạn có thể chia thành bài toán con nhỏ hơn cùng dạng — thử DP trước.

Fibonacci — Gateway Drug cho DP

Fibonacci là bài toán đơn giản nhất chứa đầy đủ DNA của DP. Chúng ta sẽ đi qua 4 cấp độ tối ưu — từ brute force đến optimal — và pattern này áp dụng cho mọi bài DP khác.

Level 1: Naive Recursion — O(2^n) 😱

                    fib(5)
                   /      \
              fib(4)       fib(3)
             /    \        /    \
          fib(3)  fib(2) fib(2) fib(1)
          /  \    /  \   /  \
       fib(2) fib(1) ... ...
       /  \
    fib(1) fib(0)

⚠️ fib(3) tính 2 lần, fib(2) tính 3 lần, fib(1) tính 5 lần!

PythonC++Java

python

def fib_naive(n):
    """Naive recursion. Time: O(2^n), Space: O(n) stack."""
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)  # 💀 Exponential

cpp

int fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2); // O(2^n)
}

java

public int fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2); // O(2^n)
}

Với n=50, hàm này cần ~1.1 × 10¹⁵ phép tính. Máy tính hiện đại mất vài ngày để trả kết quả. Không chấp nhận được.

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

Ghi nhớ kết quả đã tính vào dictionary/array. Mỗi subproblem chỉ tính đúng 1 lần.

PythonC++Java

python

def fib_memo(n, memo={}):
    """Top-down memoization. Time: O(n), Space: O(n)."""
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Hoặc pythonic hơn với decorator:
from functools import lru_cache

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

cpp

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

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

java

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

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

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

Xây dựng từ nhỏ đến lớn, không cần recursion. Không lo stack overflow.

PythonC++Java

python

def fib_tabulation(n):
    """Bottom-up tabulation. Time: O(n), Space: O(n)."""
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

cpp

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

java

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

Level 4: Space-Optimized — O(n) time, O(1) space 🚀

Chỉ cần 2 biến trước đó. Đây là production choice.

PythonC++Java

python

def fib_optimized(n):
    """Space-optimized. Time: O(n), Space: O(1)."""
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

cpp

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

java

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

So sánh 4 cấp độ

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

VISUALIZER STATES — Fibonacci DP:
State 1: CALL — recursion node appears (naive version shows full tree)
State 2: CACHE_HIT — node found in memo, highlight green (skip computation)
State 3: COMPUTE — node being calculated, turns yellow
State 4: STORE — result stored in memo/dp array, turns green
State 5: OPTIMIZE — show only prev2 and prev1 sliding forward

Climbing Stairs — Interview Classic

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ạn nhận ra gì không? Để đến bậc n, bạn nhất định phải đến từ bậc (n-1) rồi bước 1, hoặc từ bậc (n-2) rồi nhảy 2. Vậy:

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

Base cases: ways(0) = 1, ways(1) = 1

n:      0   1   2   3   4   5   6   7   8
ways:   1   1   2   3   5   8  13  21  34
                                          ↑ Fibonacci!

Climbing Stairs chính xác là Fibonacci — chỉ khác base case. Khi nhận ra điều này, bạn đã biết cách tối ưu từ O(2^n) xuống O(1) space ngay lập tức.

💡 HPN Pro Tip

Khi interviewer cho bài toán mới, hãy thử: "Nếu tôi đã biết answer cho n-1 và n-2, tôi có thể tính answer cho n không?" Nếu CÓ → đây là DP. Đây là câu hỏi mạnh nhất để phát hiện DP pattern.

PythonC++Java

python

# Approach 1: Memoization
from functools import lru_cache

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

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

# Approach 3: Space-Optimized ← dùng cái này trong interview
def climb_stairs(n: int) -> int:
    """Time: O(n), Space: O(1). Production choice."""
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

cpp

// Space-Optimized — Production choice
int climbStairs(int n) {
    if (n <= 1) return 1;
    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

java

// Space-Optimized — Production choice
public int climbStairs(int n) {
    if (n <= 1) return 1;
    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Coin Change — Teaser cho bài DP khó hơn

Bài toán: Cho coins = [1, 5, 10, 25], tìm số coin ít nhất để tạo amount = 36.

Khác với Fibonacci/Climbing Stairs chỉ phụ thuộc 2 state trước, Coin Change phụ thuộc nhiều state — mỗi coin tạo ra một nhánh quyết định khác nhau.

State:      dp[i] = minimum coins to make amount i
Transition: dp[i] = min(dp[i - coin] + 1) cho mỗi coin ≤ i
Base case:  dp[0] = 0 (0 coins cho amount 0)

Bảng DP cho coins = [1, 5, 10, 25], amount = 36:
dp[0]=0  dp[1]=1  dp[5]=1  dp[10]=1  dp[25]=1  dp[30]=2  dp[35]=2  dp[36]=3
                                                                      ↑
                                                              25 + 10 + 1 = 36

PythonC++Java

python

def coin_change(coins: list[int], amount: int) -> int:
    """Min coins to make amount. Time: O(amount × len(coins)), Space: O(amount)."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    return dp[amount] if dp[amount] != float('inf') else -1

cpp

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX)
                dp[i] = min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

java

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != Integer.MAX_VALUE)
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

Bài này phức tạp hơn Fibonacci vì state space lớn hơn và mỗi state có nhiều transition (mỗi coin là một lựa chọn). Phase 2 sẽ cover Knapsack — biến thể nâng cao của Coin Change — và nhiều pattern khác.

Top-Down vs Bottom-Up — Chọn gì?

Tiêu chí	Top-Down (Memoization)	Bottom-Up (Tabulation)
Approach	Recursive + cache	Iterative + dp array
Dễ tư duy	Dễ hơn (tự nhiên) ✅	Cần xác định thứ tự fill
Stack depth	Có thể overflow ⚠️	Không stack issue ✅
Tính tất cả states?	Chỉ states cần thiết ✅	Tất cả states
Space optimization	Khó (recursive structure)	Dễ (rolling array) ✅
Cache behavior	Kém (random access)	Tốt (sequential access) ✅

💡 Chiến thuật phỏng vấn

Trong interview: bắt đầu với Top-Down (dễ code, dễ giải thích), sau đó đề xuất Bottom-Up optimization nếu interviewer hỏi "có thể tối ưu thêm không?" Điều này cho thấy bạn hiểu cả hai approach và biết trade-off.

"Is This a DP Problem?" — 4 câu hỏi kiểm tra

Trước khi lao vào code DP, hãy kiểm tra 4 điều kiện:

#	Câu hỏi	Ví dụ "Có"
1	Bài toán hỏi count, minimum, maximum, hoặc yes/no?	"Bao nhiêu cách?", "Chi phí ít nhất?"
2	Bạn có thể chia thành bài toán con nhỏ hơn cùng dạng?	f(n) phụ thuộc f(n-1), f(n-2)
3	Bài toán con trùng lặp (cùng input xuất hiện nhiều lần)?	fib(3) tính 2 lần trong cây đệ quy
4	Nghiệm tối ưu của bài lớn phụ thuộc nghiệm tối ưu của bài con?	shortest(A→C) = shortest(A→B) + shortest(B→C)

Nếu 3-4 câu trả lời "Có" → thử DP. Nếu chỉ có điều kiện 1 và 2 mà không có 3 → có thể là Greedy hoặc Divide-and-Conquer.

⚠️ Cẩn thận

Không phải mọi bài "tìm min/max" đều là DP. Binary Search tìm min/max nhưng không có overlapping subproblems. Luôn kiểm tra cả 4 điều kiện trước khi kết luận.

Phase 2 Preview — Ranh giới Phase 1 kết thúc ở đây

🔭 Phase 2 sẽ cover

Phase 1 cho bạn nền tảng nhận diện DP. Phase 2 cho bạn kho vũ khí giải mọi biến thể:

0/1 Knapsack — tối ưu hóa lựa chọn với ràng buộc (chọn item nào cho value max?)
LCS (Longest Common Subsequence) — so sánh chuỗi, DP 2 chiều trên bảng
Bitmask DP — state compression cho tổ hợp, biểu diễn tập con bằng bit
Tree DP — DP trên cấu trúc cây, kết hợp DFS
Digit DP — đếm số thỏa điều kiện trong range [L, R]
DP Optimization — Convex Hull Trick, Knuth's optimization, Divide-and-Conquer optimization

Bạn không cần Phase 2 để pass interview cơ bản. Nhưng nếu muốn tackle hard problems → Phase 2 là bước tiếp theo.

Sai lầm điển hình

❌ Sai lầm 1: Quên base case

Vấn đề: Recursion không bao giờ dừng → stack overflow.

python

# SAI: Thiếu base case
def fib(n, memo={}):
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)  # Không bao giờ dừng!
    return memo[n]

❌ Sai lầm 2: Memoize nhưng quên check cache

Vấn đề: Có ghi nhớ nhưng không bao giờ dùng kết quả đã ghi → vẫn O(2^n).

python

# SAI: Ghi vào memo nhưng không check trước khi tính
def fib(n, memo={}):
    if n <= 1:
        return n
    # Thiếu: if n in memo: return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

❌ Sai lầm 3: Sai state definition

Vấn đề: Định nghĩa dp[i] sai → toàn bộ logic sai.

Ví dụ Coin Change: nếu bạn định nghĩa dp[i] = "số cách tạo amount i" thay vì "số coin ít nhất" → giải sai bài toán ngay từ đầu.

❌ Sai lầm 4: Off-by-one trong loop

Vấn đề: range(n) thay vì range(n + 1) → bỏ sót state cuối cùng.

python

# SAI: range(n) bỏ sót dp[n]
for i in range(n):       # i chạy từ 0 đến n-1
    dp[i] = dp[i-1] + dp[i-2]

# ĐÚNG: range(2, n+1) bao gồm dp[n]
for i in range(2, n + 1):  # i chạy từ 2 đến n
    dp[i] = dp[i-1] + dp[i-2]

❌ Sai lầm 5: Dùng DP khi không cần

Vấn đề: Không phải bài nào cũng cần DP. Binary Search tìm phần tử không có overlapping subproblems — đừng ép DP vào.

⚠️ Cạm bẫy

Quy tắc vàng: Trước khi code DP, luôn vẽ cây đệ quy cho input nhỏ (n=4 hoặc 5). Nếu bạn thấy cùng một node xuất hiện ≥ 2 lần → DP đúng hướng. Nếu không → xem lại approach.

Practice Blocks

🧠 Quiz — Nhận diện DP

🧠 Quiz

Câu 1: Bài nào sau đây KHÔNG phải bài toán DP?

[ ] A) Fibonacci
[x] B) Binary Search
[ ] C) Climbing Stairs
[ ] D) Coin Change

💡 Giải thích: Binary Search không có overlapping subproblems — mỗi bước chia đôi mảng và chỉ đi vào một nửa, không bao giờ quay lại tính nửa kia. Đây là Divide-and-Conquer, không phải DP.

🧠 Quiz

Câu 2: Memoization và Tabulation khác nhau ở điểm nào?

[ ] A) Memoization nhanh hơn Tabulation
[ ] B) Tabulation dùng recursion, Memoization dùng iteration
[x] C) Memoization là top-down (recursive + cache), Tabulation là bottom-up (iterative)
[ ] D) Không có sự khác biệt

💡 Giải thích: Memoization bắt đầu từ bài toán lớn, đệ quy xuống bài con, cache kết quả. Tabulation bắt đầu từ base case, build lên bài toán lớn bằng iteration. Cả hai đều O(n) nhưng Tabulation thường có cache locality tốt hơn và không có stack overflow risk.

🐛 Spot the Bug — Fibonacci Memoization

Tìm bug trong code sau. Tại sao nó vẫn chạy O(2^n) dù có dictionary memo?

python

def fib(n, memo={}):
    if n <= 1:
        return n
    # 🐛 BUG ở đâu?
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

💡 Đáp án

Bug: Thiếu dòng if n in memo: return memo[n] trước khi tính. Code ghi kết quả vào memo nhưng không bao giờ kiểm tra xem đã tính chưa. Kết quả: mỗi subproblem vẫn bị tính lại → O(2^n).

Fix:

python

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:        # ← Dòng này bị thiếu!
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

🧩 Parsons Problem — Coin Change Bottom-Up

Sắp xếp các dòng code sau thành hàm coin_change hoàn chỉnh:

python

# Xáo trộn — sắp xếp lại cho đúng:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
    return dp[amount] if dp[amount] != float('inf') else -1
def coin_change(coins, amount):
    dp[0] = 0
    for i in range(1, amount + 1):
                dp[i] = dp[i - coin] + 1
    dp = [float('inf')] * (amount + 1)
        for coin in coins:

💡 Đáp án

python

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    return dp[amount] if dp[amount] != float('inf') else -1

Chú ý thứ tự: khởi tạo dp → set base case → loop qua amounts → loop qua coins → check và update → return.

Checklist ghi nhớ

✅ Checklist triển khai

Nhận diện DP

[ ] Bài hỏi count/min/max/yes-no?
[ ] Chia được thành bài toán con cùng dạng?
[ ] Bài toán con trùng lặp? (vẽ cây đệ quy kiểm tra)
[ ] Optimal substructure tồn tại?

4 cấp độ tối ưu

[ ] Level 1: Naive recursion → hiểu bài toán
[ ] Level 2: Memoization → O(n) time, O(n) space
[ ] Level 3: Tabulation → loại bỏ recursion stack
[ ] Level 4: Space optimization → O(1) space nếu dp[i] chỉ phụ thuộc k states

Phỏng vấn

[ ] Bắt đầu bằng Top-Down (dễ code, dễ giải thích)
[ ] Đề xuất Bottom-Up nếu interviewer hỏi optimize
[ ] Đề xuất Space-Optimized nếu hỏi tiếp
[ ] Luôn nêu rõ Time & Space complexity cho mỗi approach

Phase 1 scope

[ ] Fibonacci pattern ✅
[ ] Climbing Stairs & variants ✅
[ ] Coin Change cơ bản ✅
[ ] Knapsack, LCS, Bitmask DP → Phase 2

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

📍 Trang tiếp theo

Bạn đã nắm được nền tảng DP — hai trụ cột, 4 cấp độ tối ưu, và cách nhận diện bài DP. Tiếp theo, chúng ta sẽ tổng hợp tất cả kiến thức Phase 1 vào bài cuối cùng: Interview Traps & Tips — những bẫy phỏng vấn phổ biến và chiến thuật xử lý.

→ Tiếp tục: Interview Traps & Tips

Từ khóa glossary: dynamic programming, quy hoạch động, memoization, tabulation, overlapping subproblems, optimal substructure, fibonacci, climbing stairs, coin change, space optimization

Tìm kiếm liên quan: quy hoạch động cơ bản, DP nhập môn, fibonacci memoization, climbing stairs solution, coin change algorithm

Quy hoạch động nhập môn — Dynamic Programming Phase 1 ​

Bức tranh tư duy — DP như "ghi chú thông minh" ​

Hai trụ cột của DP ​

Trụ cột 1: Optimal Substructure ​

Trụ cột 2: Overlapping Subproblems ​

Khi nào dùng gì? ​

Fibonacci — Gateway Drug cho DP ​

Level 1: Naive Recursion — O(2^n) 😱 ​

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

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

Level 4: Space-Optimized — O(n) time, O(1) space 🚀 ​

So sánh 4 cấp độ ​

Climbing Stairs — Interview Classic ​

Coin Change — Teaser cho bài DP khó hơn ​

Top-Down vs Bottom-Up — Chọn gì? ​

"Is This a DP Problem?" — 4 câu hỏi kiểm tra ​

Phase 2 Preview — Ranh giới Phase 1 kết thúc ở đây ​

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

❌ Sai lầm 1: Quên base case ​

❌ Sai lầm 2: Memoize nhưng quên check cache ​

❌ Sai lầm 3: Sai state definition ​

❌ Sai lầm 4: Off-by-one trong loop ​

❌ Sai lầm 5: Dùng DP khi không cần ​

Practice Blocks ​

🧠 Quiz — Nhận diện DP ​

Câu 1: Bài nào sau đây KHÔNG phải bài toán DP? ​

Câu 2: Memoization và Tabulation khác nhau ở điểm nào? ​

🐛 Spot the Bug — Fibonacci Memoization ​

🧩 Parsons Problem — Coin Change Bottom-Up ​

Checklist ghi nhớ ​

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

📍 Trang tiếp theo ​

Quy hoạch động nhập môn — Dynamic Programming Phase 1

Bức tranh tư duy — DP như "ghi chú thông minh"

Hai trụ cột của DP

Trụ cột 1: Optimal Substructure

Trụ cột 2: Overlapping Subproblems

Khi nào dùng gì?

Fibonacci — Gateway Drug cho DP

Level 1: Naive Recursion — O(2^n) 😱

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

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

Level 4: Space-Optimized — O(n) time, O(1) space 🚀

So sánh 4 cấp độ

Climbing Stairs — Interview Classic

Coin Change — Teaser cho bài DP khó hơn

Top-Down vs Bottom-Up — Chọn gì?

"Is This a DP Problem?" — 4 câu hỏi kiểm tra

Phase 2 Preview — Ranh giới Phase 1 kết thúc ở đây

Sai lầm điển hình

❌ Sai lầm 1: Quên base case

❌ Sai lầm 2: Memoize nhưng quên check cache

❌ Sai lầm 3: Sai state definition

❌ Sai lầm 4: Off-by-one trong loop

❌ Sai lầm 5: Dùng DP khi không cần

Practice Blocks

🧠 Quiz — Nhận diện DP

Câu 1: Bài nào sau đây KHÔNG phải bài toán DP?

Câu 2: Memoization và Tabulation khác nhau ở điểm nào?

🐛 Spot the Bug — Fibonacci Memoization

🧩 Parsons Problem — Coin Change Bottom-Up

Checklist ghi nhớ

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

📍 Trang tiếp theo