Khóa học Python từ Cơ bản đến Nâng cao

Bài 10.6 - Triển khai DP bằng tabulation với Python

Tabulation là một cách tiếp cận trong quy hoạch động (dynamic programming) mà ta xây dựng lời giải từ dưới lên trên (bottom-up), thay vì dùng đệ quy kết hợp memoization như kiểu top-down.

Khi nào nên dùng tabulation?

• Bài toán có thể chia nhỏ theo các bước/lớp đơn giản.
• Có thể định nghĩa trạng thái theo chỉ số.
• Cần tránh tràn stack do đệ quy sâu.
• Muốn tối ưu bộ nhớ dễ dàng hơn.

Ví dụ 1: Bài toán Fibonacci với tabulation

def fib_tab(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]

Thử chạy:

print(fib_tab(10))  # Output: 55

Từ dưới lên, bắt đầu từ fib(0) và fib(1), ta tính tới fib(n).

Ví dụ 2: Số cách leo cầu thang

Đề bài: Mỗi bước có thể leo 1 hoặc 2 bậc. Có bao nhiêu cách để leo lên n bậc?

def climb_tab(n):
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

Thử chạy:

print(climb_tab(5))  # Output: 8

Giống Fibonacci nhưng ý nghĩa khác: dp[i] là số cách để đến bậc i.

Ví dụ 3: Bài toán subset sum

Đề bài: Cho list nums và tổng target. Có thể chọn các phần tử (không trùng lặp) sao cho tổng đúng bằng target không?

def subset_sum(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for i in range(target, num - 1, -1):
            if dp[i - num]:
                dp[i] = True

    return dp[target]

Thử chạy:

print(subset_sum([3, 2, 7, 1], 6))  # Output: True
print(subset_sum([3, 2, 7, 1], 10)) # Output: False

Chúng ta xây dựng dãy dp[i] = True nếu tồn tại tổ hợp có tổng i.

So sánh memoization và tabulation

Tổng kết

• Tabulation là kỹ thuật hiệu quả trong các bài toán quy hoạch động.
• Giúp bạn kiểm soát được toàn bộ quá trình xây dựng lời giải.
• Là cơ sở để hiểu rõ hơn về cách hoạt động của DP, từ đó nâng cao khả năng tối ưu thuật toán.