Chuyển tới nội dung chính

Quy hoạch động là gì? (Dynamic Programming)

Bạn sẽ học được gì

Quy hoạch động (dynamic programming, viết tắt DP) không phải một thuật toán cụ thể, mà là một cách tư duy: khi một bài toán lớn chứa rất nhiều bài toán con lặp lại, ta tính mỗi bài con đúng một lần rồi cất kết quả lại để dùng. Bạn sẽ thấy Fibonacci từ đệ quy mũ trở thành tuyến tính chỉ nhờ một mẹo đơn giản: đừng tính lại thứ đã tính rồi.

1. Trực quan: đừng nhân hai lần cùng một phép tính​

Hãy tưởng tượng bạn được giao tính 2 + 2 + 2 + 2. Một người bạn ngồi cạnh hỏi: "Tổng của ba số 2 đầu là bao nhiêu?" Bạn nhẩm ra 6. Rồi bạn ấy lại hỏi y hệt câu đó lần nữa. Bạn có nhẩm lại từ đầu không? Tất nhiên là không — bạn nhớ kết quả 6 và trả lời ngay.

DP chính là cái phản xạ "tôi đã tính rồi, để tôi nhớ lại" đó, nhưng áp dụng cho máy tính. Vấn đề là máy tính không tự nhớ: nếu ta viết đệ quy ngây thơ, nó sẽ tính đi tính lại cùng một bài con đến hàng triệu lần.

        Cây đệ quy Fibonacci fib(5) — chú ý fib(2) bị tính TỚI 3 LẦN:

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

     => Cùng một nhánh fib(2), fib(3) bị làm lại nhiều lần => LÃNG PHÍ.

2. Hai điều kiện để dùng được DP​

Một bài toán "hợp gu" DP khi có đồng thời hai tính chất sau:

Tính chấtNghĩa là gìVí dụ Fibonacci
Bài toán con gối nhau (overlapping subproblems)Các bài con xuất hiện lặp đi lặp lạifib(2) được hỏi rất nhiều lần
Cấu trúc con tối ưu (optimal substructure)Lời giải bài lớn ghép từ lời giải bài confib(n) = fib(n-1) + fib(n-2)

Nếu các bài con không lặp lại (mỗi cái chỉ gặp một lần) thì DP vô dụng — đó là địa hạt của chia để trị. DP đúng nghĩa là chia để trị + có ghi nhớ.

3. Hai trường phái: top-down và bottom-up​

Có hai cách "ghi nhớ":

  • Memoization (top-down): vẫn viết đệ quy như thường, nhưng thêm một cuốn sổ (memo). Trước khi tính fib(n), ngó vào sổ; có rồi thì lấy ra, chưa có thì tính xong ghi vào sổ.
  • Tabulation (bottom-up): bỏ đệ quy, dùng một bảng dp. Điền từ bài nhỏ nhất (dp[0], dp[1]) lên dần tới bài lớn. Mỗi ô chỉ điền một lần.
   Bottom-up dien bang dp cho Fibonacci:

   index : 0   1   2   3   4   5
   dp    : 0   1   1   2   3   5
            \___\__/                 dp[2] = dp[1] + dp[0] = 1
                \___\__/             dp[3] = dp[2] + dp[1] = 2
                    \___\__/         dp[4] = dp[3] + dp[2] = 3
                        \___\__/     dp[5] = dp[4] + dp[3] = 5

4. Bước qua: điền bảng dp cho Fibonacci​

Theo dõi từng ô bảng được điền từ trái sang phải — không có đệ quy, không tính lại gì.

🐞 Bottom-up: điền dp cho fib(5)Bước 1/6
1dp = [0, 1, 0, 0, 0, 0]
2for i in range(2, 6):
3  dp[i] = dp[i-1] + dp[i-2]
4ket_qua = dp[5]
Biến tại bước này
dp[0, 1, 0, 0, 0, 0]
👉 Hai ô đáy: dp[0]=0, dp[1]=1 (đã biết sẵn).

5. Code chạy được: so sánh ba phiên bản​

Đang tải trình chạy code…

Chạy thử và để ý: fib_naive(30) đã chậm thấy rõ, còn fib_dp(50) ra ngay tức khắc.

6. Phân tích: vì sao nhanh đến vậy?​

CáchThời gianBộ nhớGhi chú
Đệ quy ngây thơO(2^n)O(n) (ngăn xếp)Tính lại vô số lần
MemoizationO(n)O(n)Mỗi bài con tính 1 lần + lưu sổ
TabulationO(n)O(n)Có thể tối ưu xuống O(1) — xem bài 3.4.5

Sức mạnh của DP nằm ở một câu: số bài con khác nhau là có hạn (với Fibonacci là n bài), nên nếu mỗi bài tính đúng một lần, tổng công sức chỉ là số bài con × công mỗi bài.

Bẫy thường gặp:

  • Quên ghi vào sổ memo sau khi tính → vẫn chậm như đệ quy thường.
  • Định nghĩa trạng thái (state) sai → công thức truy hồi không khớp.
  • Với memoization, đệ quy quá sâu có thể tràn ngăn xếp lời gọi; khi đó nên chuyển sang bottom-up.

7. Mẫu nhận diện​

  • Đề hỏi "đếm số cách", "tối đa/tối thiểu", "có thể đạt được không" → rất hay là DP.
  • Bạn viết được đệ quy, nhưng nhận ra cùng tham số bị gọi lại nhiều lần → thêm memo là xong.
  • Quyết định tại bước hiện tại chỉ phụ thuộc vào vài bước trước đó → định nghĩa trạng thái + truy hồi.

8. 🎮 Trò chơi: Hiểu DP​

🎮 Hiểu quy hoạch độngCâu 1/4· Điểm 0· 🔥 0

DP = chia bài toán thành bài con gối nhau, mỗi bài con tính đúng một lần rồi nhớ lại.

In ra gì? (đây là Fibonacci)

dp = [0, 1, 0, 0, 0]
for i in range(2, 5):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[4])

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Hai tính chất cần có để áp dụng DP là?
2. Tabulation (bottom-up) điền bảng theo thứ tự nào?
3. Nếu quên lưu kết quả vào memo thì sao?

10. Hoàn thành​

…

☑️ Tiếp theo: 3.4.2 — DP 1 chiều (leo cầu thang, cướp nhà, dãy con tăng dài nhất).