Từ đệ quy có nhớ đến bảng trạng thái DP

Bài chuẩn dừng lại ở việc viết đúng hàm đệ quy `fib(n) = fib(n-1) + fib(n-2)` và chạy thử với `n` nhỏ. Đề HSG cho `n` đủ lớn (ví dụ `n ≤ 10^6`) để hàm đệ quy thẳng chắc chắn TLE (Time Limit Exceeded) — em buộc phải tự chuyển sang QHĐ.

Trạng thái: `i` — cần tính `fib(i)`. Công thức truy hồi: `fib(i) = fib(i-1) + fib(i-2)`. Thứ tự tính: `i` tăng dần từ 0, vì `fib(i)` cần hai giá trị nhỏ hơn đã có sẵn. Khởi tạo: `fib(0) = 0`, `fib(1) = 1`; đáp số là `fib(n)`.

Vẫn viết hàm đệ quy đúng như bài chuẩn, chỉ thêm một `cache` để không tính lại trạng thái đã biết: ```python def fib_nho_tren_xuong(n, cache=None): """Fibonacci bang de quy co nho (memoization, top-down).""" if cache is None: cache = {} if n in cache: return cache[n] if n <= 1: return n cache[n] = fib_nho_tren_xuong(n - 1, cache) + fib_nho_tren_xuong(n - 2, cache) return cache[n] ```

Bỏ hẳn đệ quy, điền thẳng một mảng `dp[]` theo đúng thứ tự tính đã xác định ở bước 3: ```python def fib_bang_duoi_len(n): """Fibonacci bang bang dp[], duyet tu duoi len (tabulation, bottom-up).""" 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 ```

Cả hai đều `O(n)` thời gian thay vì `O(1,618^n)`. Memoization giữ nguyên tư duy đệ quy, dễ viết hơn khi trạng thái phức tạp, nhưng độ sâu ngăn xếp gọi hàm lớn bằng `n` — với `n` cỡ `10^6`, Python sẽ vượt giới hạn đệ quy mặc định. Tabulation không có ngăn xếp gọi hàm, an toàn hơn với `n` lớn, nhưng đòi hỏi em tự nghĩ ra đúng thứ tự tính trước khi viết vòng lặp — đây là lý do bước 3 trong quy trình bốn bước không thể bỏ qua.

Ta có trạng thái `dp[i] = fib(i)`. Công thức truy hồi `dp[i] = dp[i-1] + dp[i-2]` với `i ≥ 2`, khởi tạo `dp[0] = 0`, `dp[1] = 1`. Tính tăng dần `i` từ 2 đến `n`. Với `n = 10`: `dp = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]`. Vậy fib(10) = 55, tính trong `O(n)` thời gian và `O(n)` bộ nhớ (có thể nén xuống `O(1)` vì mỗi bước chỉ cần hai giá trị liền trước).

Bài chuẩn cho lưới trống hoàn toàn, và đáp số tính thẳng bằng công thức tổ hợp $C_{m+n-2}^{m-1}$ — chọn `m-1` bước xuống trong tổng `m+n-2` bước. Đề HSG thường thêm chướng ngại vật: khi đó công thức tổ hợp không còn dùng được, vì không phải mọi đường đi hình học đều hợp lệ. Quy hoạch động vẫn giải được, công thức tổ hợp thì không.

Trạng thái: `(i, j)` — vị trí trên lưới. Công thức truy hồi: `dp[i][j] = dp[i-1][j] + dp[i][j-1]` — đến ô `(i, j)` chỉ có thể đi từ ô trên hoặc ô trái. Thứ tự tính: hàng tăng dần, trong mỗi hàng cột tăng dần (mọi ô lân cận trái/trên đã tính trước). Khởi tạo: hàng 0 và cột 0 chỉ có một cách đi tới (đi thẳng một chiều), nên `dp[0][j] = dp[i][0] = 1`; đáp số là `dp[m-1][n-1]`.

Với lưới `3 × 4` không chướng ngại vật: ```python def dem_duong_di(m, n): """So duong di tu (0,0) den (m-1,n-1) tren luoi m x n, chi di phai/xuong. dp[i][j] = dp[i-1][j] + dp[i][j-1]; hang 0 va cot 0 la bien (= 1).""" dp = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): if i == 0 or j == 0: dp[i][j] = 1 else: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp ```

Đề HSG thường đặt thêm một số ô "vật cản" mà đường đi không được phép bước qua. Chỉ cần sửa một dòng trong công thức truy hồi: ô vật cản luôn có `dp[i][j] = 0`, kể cả khi nó nằm trên hàng 0 hoặc cột 0 (một vật cản ở cột 0 chặn đứng toàn bộ phần lưới phía dưới nó trên cùng cột): ```python def dem_duong_di_co_vat_can(luoi): """Giong dem_duong_di nhung o vat can (gia tri 1) luon co dp = 0.""" m, n = len(luoi), len(luoi[0]) dp = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): if luoi[i][j] == 1: dp[i][j] = 0 elif i == 0 and j == 0: dp[i][j] = 1 else: tu_trai = dp[i][j - 1] if j > 0 else 0 tu_tren = dp[i - 1][j] if i > 0 else 0 dp[i][j] = tu_trai + tu_tren return dp ```

Với lưới không vật cản `3 × 4`, áp dụng công thức truy hồi theo đúng thứ tự hàng tăng dần, ta được `dp[2][3] = 10` — khớp với công thức tổ hợp $C_5^2 = 10$ (kiểm tra chéo hai cách). Khi thêm vật cản tại ô `(1, 2)`, số đường đi giảm còn `dp[2][3] = 4`, vì mọi đường đi buộc phải né ô đó. Vậy đáp số phụ thuộc hoàn toàn vào cách lưới được cho, và chỉ QHĐ mới xử lý được trường hợp tổng quát này.

Trạng thái: `(i, j)`. Công thức truy hồi: `dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + luoi[i][j]` — đến ô `(i, j)` bằng đường tốt hơn trong hai đường khả dĩ, cộng chi phí ô hiện tại. Thứ tự tính: hàng tăng dần, cột tăng dần, giống Ví dụ 2. Khởi tạo: `dp[0][0] = luoi[0][0]`; hàng 0 và cột 0 chỉ có một đường đi duy nhất nên cộng dồn thẳng.

Giả sử đường đi tối ưu đến `(i, j)` đi qua ô trên `(i-1, j)`. Khi đó đoạn đường từ điểm xuất phát đến `(i-1, j)` PHẢI là đường tối ưu đến `(i-1, j)` — nếu không, thay đoạn đó bằng đường tốt hơn sẽ cho một đường đến `(i, j)` tốt hơn nữa, mâu thuẫn với giả thiết tối ưu. Đây gọi là tính chất cấu trúc con tối ưu (optimal substructure): lời giải tối ưu của bài toán lớn được ghép từ lời giải tối ưu của các bài toán con. Chính tính chất này cho phép công thức `min` hoạt động đúng.

Lưu thêm mảng `cha[i][j]` — ô nào dẫn tới `(i, j)` trong đường tối ưu — song song với bảng `dp`, rồi đi ngược từ đáp số về điểm xuất phát: ```python def duong_di_tong_nho_nhat(luoi): """dp[i][j] = tong nho nhat tu (0,0) den (i,j); tra ve ca bang dp va duong di cu the (truy vet bang mang cha).""" m, n = len(luoi), len(luoi[0]) dp = [[0] * n for _ in range(m)] cha = [[None] * n for _ in range(m)] for i in range(m): for j in range(n): if i == 0 and j == 0: dp[i][j] = luoi[i][j] elif i == 0: dp[i][j] = dp[i][j - 1] + luoi[i][j] cha[i][j] = (i, j - 1) elif j == 0: dp[i][j] = dp[i - 1][j] + luoi[i][j] cha[i][j] = (i - 1, j) else: if dp[i - 1][j] <= dp[i][j - 1]: dp[i][j] = dp[i - 1][j] + luoi[i][j] cha[i][j] = (i - 1, j) else: dp[i][j] = dp[i][j - 1] + luoi[i][j] cha[i][j] = (i, j - 1) duong_di = [(m - 1, n - 1)] hien_tai = (m - 1, n - 1) while cha[hien_tai[0]][hien_tai[1]] is not None: hien_tai = cha[hien_tai[0]][hien_tai[1]] duong_di.append(hien_tai) duong_di.reverse() return dp, duong_di ```

Với lưới chi phí `[[1,3,1,2],[1,5,1,3],[4,2,1,2]]`, áp dụng công thức truy hồi theo thứ tự hàng tăng dần, cột tăng dần, ta được `dp[2][3] = 9`. Truy vết ngược từ `(2,3)` theo mảng cha cho đường đi cụ thể `(0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,3)`, với tổng `1+3+1+1+1+2 = 9` — khớp giá trị `dp[2][3]`. Vậy tổng chi phí nhỏ nhất bằng 9, đạt được theo đúng đường đi vừa truy vết.