Giao diện
Dynamic Programming - Core Concepts
"Brute force là lựa chọn của kẻ lười tư duy. DP là vũ khí của kỹ sư thông minh." - HPN
Định nghĩa
Dynamic Programming (DP) là kỹ thuật giải bài toán bằng cách:
- Chia nhỏ bài toán thành các subproblems nhỏ hơn
- Lưu trữ kết quả của các subproblems đã giải (để không tính lại)
- Tổng hợp kết quả để giải bài toán gốc
📘 Core Insight
DP = Recursion + Memoization (hoặc Iteration + Tabulation)
Bản chất là Trade-off SPACE cho TIME.
Hai Điều Kiện Tiên Quyết
Để áp dụng DP, bài toán BẮT BUỘC phải có:
1. Overlapping Subproblems (Bài toán con chồng lấp)
🎯 THE WASTE
Để tính fib(5):
fib(3)được tính 2 lầnfib(2)được tính 3 lầnfib(1)được tính 5 lần
Với fib(50): ~20 BILLION lần gọi hàm! → $O(2^N)$
Giải pháp: Tính một lần, lưu lại, dùng lại.
2. Optimal Substructure (Cấu trúc con tối ưu)
Nghiệm tối ưu của bài toán con có thể tổng hợp thành nghiệm tối ưu của bài toán lớn.
fib(n) = fib(n-1) + fib(n-2)
↓ ↓
[Optimal n-1] + [Optimal n-2] = [Optimal n]| Bài toán | Có Optimal Substructure? | Lý do |
|---|---|---|
| Fibonacci | ✅ Yes | fib(n) = fib(n-1) + fib(n-2) |
| Shortest Path | ✅ Yes | Đường đi ngắn nhất A→C đi qua B = A→B + B→C |
| Longest Path (general graph) | ❌ No | Có thể visit node 2 lần → vi phạm |
Top-Down vs Bottom-Up
Có 2 cách implement DP:
Top-Down (Memoization)
Đặc điểm:
- Bắt đầu từ bài toán gốc, gọi đệ quy xuống base case
- Dùng cache (thường là dictionary/array) để lưu kết quả
- Lazy computation: Chỉ tính khi cần
Bottom-Up (Tabulation)
Đặc điểm:
- Bắt đầu từ base case, tính dần lên bài toán gốc
- Dùng table (thường là array) để lưu trữ
- Eager computation: Tính tất cả subproblems
So Sánh
| Tiêu chí | Top-Down (Memoization) | Bottom-Up (Tabulation) |
|---|---|---|
| Cách tiếp cận | Đệ quy + Cache | Vòng lặp + Table |
| Tính toán | Lazy (chỉ tính khi cần) | Eager (tính tất cả) |
| Stack overflow | ⚠️ Có thể với N lớn | ✅ Không có |
| Code | Thường ngắn hơn | Thường dài hơn |
| Debug | Khó hơn | Dễ hơn |
| Space optimization | Khó | Dễ (có thể giảm từ O(N) → O(1)) |
| Khi nào dùng | Không cần tất cả subproblems | Cần tất cả subproblems |
Bài Toán Minh Họa: Fibonacci
Naive Recursion: O(2^N) ❌
python
def fib_naive(n: int) -> int:
"""
❌ ĐỪNG BAO GIỜ DÙNG TRONG PRODUCTION!
Time: O(2^N) - Exponential
Space: O(N) - Call stack
"""
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)Vấn đề: Tính fib(50) mất hàng giờ, fib(100) mất hàng triệu năm.
Top-Down với lru_cache: O(N) ✅
python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memoized(n: int) -> int:
"""
✅ PYTHONIC WAY - Sử dụng decorator của Python.
Time: O(N)
Space: O(N) - Cache + Call stack
lru_cache tự động lưu kết quả đã tính.
"""
if n <= 1:
return n
return fib_memoized(n - 1) + fib_memoized(n - 2)Bottom-Up Tabulation: O(N) ✅
python
def fib_tabulation(n: int) -> int:
"""
✅ CLASSIC DP - Dễ hiểu, dễ debug.
Time: O(N)
Space: O(N) - Array lưu kết quả
"""
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]Space-Optimized: O(1) ✅✅
python
def fib_optimized(n: int) -> int:
"""
✅✅ PRODUCTION-READY - Tối ưu space.
Time: O(N)
Space: O(1) - Chỉ cần 2 biến!
Nhận xét: Ta chỉ cần 2 giá trị trước đó.
"""
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1Complexity Comparison
| Approach | Time | Space | fib(50) thực tế |
|---|---|---|---|
| Naive Recursion | $O(2^N)$ | $O(N)$ | ~1 giờ |
| Memoization | $O(N)$ | $O(N)$ | < 1ms |
| Tabulation | $O(N)$ | $O(N)$ | < 1ms |
| Space-Optimized | $O(N)$ | $O(1)$ | < 1ms |
🚀 Performance Gain
Từ $O(2^N)$ → $O(N)$: Với N=50, giảm từ ~1.1 triệu tỷ operations xuống 50 operations.
Đây là sức mạnh của Dynamic Programming!
Production Code
python
# HPN Engineering Standard
# Implementation: Fibonacci với tất cả approaches
from functools import lru_cache
from typing import Callable
import time
# ============================================
# APPROACH 1: NAIVE RECURSION (EDUCATIONAL ONLY)
# ============================================
def fib_naive(n: int) -> int:
"""
❌ Time: O(2^N) | Space: O(N)
CHỈ DÙNG ĐỂ DEMO TẠI SAO CẦN DP!
"""
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# ============================================
# APPROACH 2: TOP-DOWN MEMOIZATION
# ============================================
@lru_cache(maxsize=None)
def fib_memoized(n: int) -> int:
"""
✅ Time: O(N) | Space: O(N)
Pythonic way - Sử dụng built-in decorator.
"""
if n <= 1:
return n
return fib_memoized(n - 1) + fib_memoized(n - 2)
def fib_memoized_manual(n: int, memo: dict = None) -> int:
"""
✅ Time: O(N) | Space: O(N)
Manual implementation - Hiểu rõ cơ chế.
"""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memoized_manual(n - 1, memo) + fib_memoized_manual(n - 2, memo)
return memo[n]
# ============================================
# APPROACH 3: BOTTOM-UP TABULATION
# ============================================
def fib_tabulation(n: int) -> int:
"""
✅ Time: O(N) | Space: O(N)
Classic DP - Dễ hiểu, dễ debug, no recursion limit.
"""
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# ============================================
# APPROACH 4: SPACE-OPTIMIZED (RECOMMENDED)
# ============================================
def fib_optimized(n: int) -> int:
"""
✅✅ Time: O(N) | Space: O(1)
PRODUCTION-READY: Tối ưu cả time và space.
"""
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
# ============================================
# BENCHMARK UTILITY
# ============================================
def benchmark(func: Callable, n: int, runs: int = 100) -> float:
"""Benchmark a function and return average time in ms."""
total_time = 0
for _ in range(runs):
start = time.perf_counter()
func(n)
total_time += time.perf_counter() - start
return (total_time / runs) * 1000
# ============================================
# USAGE EXAMPLE
# ============================================
if __name__ == "__main__":
n = 35
print(f"=== Fibonacci({n}) ===\n")
# Naive (chỉ test với N nhỏ vì quá chậm)
if n <= 35:
naive_time = benchmark(fib_naive, n, runs=1)
print(f"Naive: fib({n}) = {fib_naive(n):,} | Time: {naive_time:.2f}ms")
# Memoized
fib_memoized.cache_clear()
memo_time = benchmark(fib_memoized, n)
print(f"Memoized: fib({n}) = {fib_memoized(n):,} | Time: {memo_time:.4f}ms")
# Tabulation
tab_time = benchmark(fib_tabulation, n)
print(f"Tabulation: fib({n}) = {fib_tabulation(n):,} | Time: {tab_time:.4f}ms")
# Optimized
opt_time = benchmark(fib_optimized, n)
print(f"Optimized: fib({n}) = {fib_optimized(n):,} | Time: {opt_time:.4f}ms")
print(f"\n🚀 Speed-up Naive→Optimized: {naive_time/opt_time:.0f}x faster!")Real-World Applications
DP không chỉ là bài tập interview. Nó giải quyết các vấn đề thực tế:
| Domain | Bài toán | DP Pattern |
|---|---|---|
| E-commerce | Pricing optimization, Bundle deals | Knapsack |
| Finance | Stock trading (buy/sell timing) | State Machine DP |
| Navigation | Shortest path (GPS) | Graph DP |
| Text Processing | Spell check, Diff algorithms | Edit Distance |
| Game Development | AI pathfinding | Grid DP |
| Bioinformatics | DNA sequence alignment | LCS (Longest Common Subsequence) |
⚠️ Interview Reality
80% các bài DP trong interview thuộc về:
- Fibonacci variants (Climbing Stairs, House Robber)
- Knapsack variants (0/1, Unbounded, Subset Sum)
- Grid DP (Unique Paths, Minimum Path Sum)
- String DP (LCS, Edit Distance, Palindrome)
Master 4 loại này trước!
Next Steps
- Climbing Stairs - Bài toán DP kinh điển
- Knapsack Problem - Tối ưu hóa lựa chọn
- Longest Common Subsequence - String DP
💡 HPN's Rule
"Thấy 'count ways', 'minimum/maximum', 'possible or not' → Nghĩ đến DP ngay."