Tối ưu không gian DP (Space Optimization)

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

Nhiều bảng dp lưu cả lịch sử nhưng truy hồi chỉ nhìn vài hàng gần nhất. Vậy thì giữ cả bảng làm gì? Cuộn mảng (rolling array) là mẹo bỏ đi phần không cần: chỉ giữ một hoặc hai hàng, kéo bộ nhớ từ O(n·m) xuống O(m). Bạn sẽ thấy mẹo này áp dụng cho Fibonacci, LCS và knapsack — cùng một ý tưởng, ba quy mô khác nhau.

1. Trực quan: cây cầu chỉ cần hai nhịp

Hãy hình dung bạn đang xây một cây cầu rất dài, đặt từng nhịp một. Để đặt nhịp mới, bạn chỉ cần đứng trên nhịp ngay trước đó — không cần giữ lại toàn bộ những nhịp đã đi qua phía sau. DP cuộn mảng cũng vậy: nếu dp[i] chỉ phụ thuộc dp[i-1] và dp[i-2], ta không cần nhớ dp[0], dp[1], ... xa tít phía sau.

Nguyên tắc: đếm xem truy hồi nhìn bao xa về quá khứ. Nhìn lại k hàng → chỉ cần giữ k hàng.

2. Cấp 1 — Fibonacci: từ mảng xuống 2 biến

Fibonacci dp[i] = dp[i-1] + dp[i-2] chỉ nhìn hai ô liền trước. Vậy thay vì mảng n ô, ta giữ đúng hai biến và trượt chúng đi:

   Mang day du:  dp = [0,1,1,2,3,5,8,...]   ton O(n)

   Cuon lai:     a, b = 0, 1
                 lap:  a, b = b, a + b      <- truot cua so 2 phan tu
                 ton O(1) bo nho!

🐞 Fibonacci O(1) bộ nhớ: trượt hai biếnBước 1/7

1a, b = 0, 1
2for _ in range(5):
3  a, b = b, a + b
4ket_qua = a

Biến tại bước này

a	0
b	1

👉 a = fib(0), b = fib(1).

3. Cấp 2 — LCS: từ bảng 2D xuống 2 hàng

Nhớ lại LCS dùng dp[i][j] phụ thuộc dp[i-1][j-1], dp[i-1][j], dp[i][j-1] — tất cả nằm ở hàng i và hàng i-1. Không ô nào nhìn xa hơn hàng trước. Vậy chỉ cần hai hàng: prev (hàng i-1) và cur (hàng i). Xong một hàng thì prev = cur.

   Bang day du O(n*m):        Cuon 2 hang O(m):
   hang 0 [ ........ ]        prev [ ........ ]   <- hang i-1
   hang 1 [ ........ ]        cur  [ ........ ]   <- hang i dang dien
   hang 2 [ ........ ]        (xong hang -> prev = cur, lam tiep)
   ...

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

4. Cấp 3 — Knapsack: từ bảng 2D xuống 1 hàng (và mẹo duyệt ngược)

Knapsack còn gọn hơn: dp[i][c] chỉ phụ thuộc hàng i-1, nên một hàng dp[c] là đủ — ta cập nhật ngay trên chính nó. Nhưng có một cái bẫy tinh tế: vì "lấy món i" dùng dp[c - w] của hàng cũ (i-1), ta phải duyệt c từ phải sang trái. Nếu duyệt từ trái, dp[c-w] đã bị ghi đè bởi hàng mới → vô tình lấy món i nhiều lần.

   1 hang dp[c], cap nhat tai cho:
   dp[c] = max( dp[c],  v + dp[c - w] )

   DUYET c TU PHAI SANG TRAI  =>  dp[c-w] van la gia tri hang cu (i-1)
   (duyet tu trai se lam mon bi lay lap lai -> SAI cho bai 0/1)

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

5. Phân tích chung

Bài	Truy hồi nhìn lại	Bộ nhớ gốc	Sau tối ưu	Mẹo
Fibonacci	2 ô	O(n)	O(1)	2 biến trượt
LCS	hàng i-1	O(n·m)	O(m)	2 hàng prev/cur
Knapsack 0/1	hàng i-1	O(n·W)	O(W)	1 hàng, duyệt ngược

Quan trọng: tối ưu không gian không đổi độ phức tạp thời gian — vẫn từng đó phép tính, chỉ là tốn ít bộ nhớ hơn. Hãy tối ưu sau khi bản đầy đủ đã chạy đúng.

Bẫy thường gặp:

• Cuộn mảng làm mất khả năng truy vết lời giải (không còn cả bảng để dò ngược đường đi). Nếu đề cần in ra chính dãy/đường đi, hãy giữ bảng đầy đủ.
• Knapsack 1 hàng: quên duyệt ngược là lỗi kinh điển, kết quả sai mà không báo lỗi.
• Tối ưu quá sớm khi logic còn chưa đúng — sửa lỗi trên 2 biến khó hơn nhiều so với trên cả bảng.

6. Mẫu nhận diện

• Bảng dp lớn nhưng truy hồi chỉ chạm hàng liền trước → cuộn xuống 1–2 hàng.
• Truy hồi 1 chiều chỉ nhìn dp[i-1], dp[i-2] → vài biến là đủ, O(1).
• Đề giới hạn bộ nhớ chặt, hoặc n, m rất lớn → bắt buộc cuộn mảng.

7. 🎮 Trò chơi: Cuộn mảng

🎮 Tối ưu không gian DPCâu 1/4· Điểm 0· 🔥 0

Chỉ giữ đúng số hàng mà truy hồi cần nhìn lại.

LCS cuộn mảng cần giữ bao nhiêu hàng?

8. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. Ý tưởng cốt lõi của cuộn mảng (rolling array) là?

2. Fibonacci sau khi cuộn mảng tốn bao nhiêu bộ nhớ?

3. Nhược điểm của cuộn mảng là gì?

9. Hoàn thành

…

☑️ Tiếp theo: 3.5.1 — Tham lam (Greedy) (chọn tối ưu cục bộ tại mỗi bước).