Quy hoạch động

Khái niệm

Quy hoạch động (Dynamic Programming — DP) giải các bài toán bằng cách chia nhỏ thành bài toán con chồng chéo và lưu lại kết quả để tránh tính lại. Hai điều kiện nhận biết bài DP:

Cấu trúc con tối ưu — Kết quả tối ưu của bài toán lớn được xây dựng từ kết quả tối ưu của bài toán con.
Bài toán con chồng chéo — Nhiều nhánh tính toán cùng cần một bài toán con.

Hai cách tiếp cận

1. Top-down (memoization — ghi nhớ)

Viết đệ quy như bình thường, nhưng lưu kết quả vào bộ nhớ đệm.

2. Bottom-up (tabulation — lập bảng)

Tính từ bài toán con nhỏ nhất lên bài toán lớn.

Ví dụ kinh điển: dãy Fibonacci

graph TD; A["fib(5)"] --> B["fib(4)"]; A --> C["fib(3)"]; B --> D["fib(3)"]; B --> E["fib(2)"]; C --> F["fib(2)"]; C --> G["fib(1)"]; style D fill:#ffc107,color:#000 style F fill:#ffc107,color:#000 style E fill:#fd7e14,color:#fff style G fill:#20c997,color:#fff linkStyle default stroke:#888

Không có DP: fib(3) bị tính 2 lần, fib(2) bị tính 3 lần…

# Không dùng DP — O(2^n)
def fib_cham(n):
    if n <= 1:
        return n
    return fib_cham(n - 1) + fib_cham(n - 2)

# Top-down với memoization — O(n)
from functools import lru_cache

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

# Bottom-up — O(n), không dùng đệ quy
def fib_dp(n):
    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]

print(fib_dp(10))    # 55
print(fib_dp(30))    # 832040

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

Dễ — Leo cầu thang (Climbing Stairs)

Có n bậc thang. Mỗi lần có thể bước 1 hoặc 2 bậc. Có bao nhiêu cách leo lên hết?

def leo_cau_thang(n):
    """
    dp[i] = số cách leo đến bậc thứ i.
    dp[i] = dp[i-1] (bước 1) + dp[i-2] (bước 2).
    """
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1    # 1 cách leo 1 bậc
    dp[2] = 2    # 2 cách leo 2 bậc: (1+1) hoặc (2)
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(leo_cau_thang(2))   # 2
print(leo_cau_thang(3))   # 3  (1+1+1, 1+2, 2+1)
print(leo_cau_thang(5))   # 8

Trung bình — Dãy con tăng dài nhất (LIS)

Tìm độ dài dãy con tăng dần dài nhất (không cần liên tiếp).

def lis(arr):
    """
    dp[i] = độ dài LIS kết thúc tại arr[i].
    dp[i] = max(dp[j] + 1) với mọi j < i và arr[j] < arr[i].
    O(n²) — có thể tối ưu O(n log n) bằng binary search.
    """
    if not arr:
        return 0
    n = len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))   # 4 (2,3,7,18 hoặc 2,5,7,101)
print(lis([0, 1, 0, 3, 2, 3]))              # 4 (0,1,2,3)
print(lis([7, 7, 7, 7]))                    # 1

Khó — Đường đi có tổng lớn nhất trong tam giác số

Tìm tổng lớn nhất từ đỉnh xuống đáy tam giác số, mỗi bước di chuyển xuống dưới-trái hoặc dưới-phải.

def max_path_tam_giac(tam_giac):
    """
    dp[r][c] = tổng lớn nhất từ đỉnh đến tam_giac[r][c].
    Bottom-up từ dưới lên trên, không cần thêm bộ nhớ.
    """
    dp = [row[:] for row in tam_giac]   # Sao chép tam giác
    rows = len(dp)

    # Tính từ hàng áp cuối lên trên
    for r in range(rows - 2, -1, -1):
        for c in range(r + 1):
            dp[r][c] += max(dp[r+1][c], dp[r+1][c+1])

    return dp[0][0]

tam_giac = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3]
]
print(max_path_tam_giac(tam_giac))   # 20  (2→3→5→8... wait 2+4+7+8=21)
# Đường: 2 → 4 → 7 → 8 → tổng = 21? Kiểm tra lại: không 2+3+6+4=15, 2+4+7+8=21

tam_giac2 = [
    [3],
    [7, 4],
    [2, 4, 6],
    [8, 5, 9, 3]
]
print(max_path_tam_giac(tam_giac2))  # 23  (3→7→4→9)

Quy trình giải bài DP

Xác định trạng thái — dp[i] hoặc dp[i][j] nghĩa là gì?
Viết công thức chuyển tiếp — dp[i] phụ thuộc vào những dp nào trước đó?
Xác định giá trị ban đầu — dp[0], dp[1] bằng bao nhiêu?
Xác định thứ tự tính — Tính từ nhỏ đến lớn hay từ lớn đến nhỏ?
Trả về kết quả — dp[n], max(dp), hay dp[0][0]?

Kết luận

DP là kỹ thuật quan trọng nhất trong thi đấu lập trình. Hầu hết các bài DP đều có cùng cấu trúc tư duy — điểm khó là xác định được trạng thái đúng. Hãy thực hành với Bài toán cái túi — ví dụ DP kinh điển nhất.

Trong series này: