Lesson 30 — Tối ưu Quy hoạch động (DP Optimization)

Ba module tương tác cho các kỹ thuật tăng tốc / giảm bộ nhớ DP: Space optimization (bảng 2D → rolling 1 hàng), Monotonic deque (cửa sổ trượt min/max cho transition), và Matrix exponentiation (fib bằng lũy thừa ma trận 2×2, O(log n)).

1. Space optimization — bảng 2D → rolling 1 hàng O(nW) bộ nhớ → O(W)

Knapsack 0/1: bảng đầy đủ dp[i][w] nhưng hàng i chỉ đọc hàng i-1. Bấm Bước tiếp để xem từng hàng được tính rồi hàng cũ "trôi đi", chỉ giữ lại 1 hàng đang dùng.

wt: val: W:

hàng đang dùng (giữ) hàng cũ (vứt — rolling) ô đang tính

Bấm "Bước tiếp" để bắt đầu.

Bộ nhớ bảng đầy đủ (n+1)×(W+1):

—

Bộ nhớ rolling 1×(W+1):

—

Duyệt w GIẢM dần để dp[w-wt[i]] còn là giá trị hàng cũ (chưa lấy vật i). Đây là mấu chốt của knapsack 0/1 nén 1 chiều.

2. Monotonic deque — max trong cửa sổ trượt cho DP O(nk) → O(n)

Jump Game VI: dp[i] = a[i] + max(dp[i-k..i-1]). Deque giảm dần giữ các ứng viên còn cửa thắng; front = max trong cửa sổ. Bấm Bước tiếp để xem pop front (rời cửa sổ) + pop back (vô dụng) + push i.

a: k:

i đang tính cửa sổ [i-k, i-1] front (= max)

Bấm "Bước tiếp" để bắt đầu.

Deque (chỉ số): []

Mỗi chỉ số vào/ra deque đúng 1 lần → tổng O(n) (amortized), không phải O(n·k).

3. Matrix exponentiation — fib bằng lũy thừa ma trận 2×2 O(n) → O(log n)

T = [[1,1],[1,0]], fib(n) = (T^n)[0][1]. Tính T^n bằng fast power: bình phương liên tiếp + nhân theo bit của n. Bấm Tính để xem từng vòng lặp và đếm số bước.

Nhập n rồi bấm "Tính".

Vòng	bit của n	result (T^?)	base ← base²
—

Số bước tuyến tính O(n):

—

Số bước matrix expo O(log n):

—

Kiểm chứng: T¹→f(1)=1, T²→f(2)=1, T³→f(3)=2, T⁵→f(5)=5. Mỗi nhân ma trận 2×2 là O(1).