Đây là bản xem thử. Phiên bản đầy đủ trong ứng dụng có bài tập, AI chấm ngay và theo dõi tiến độ học.
Bài học
DP trên đoạn — nhân chuỗi ma trận và ghép xâu thành palindrome
Mục tiêu bài học
Sau bài này, em giải được một lớp bài toán tối ưu trên **một đoạn liên tục** bằng quy hoạch động hai chiều $dp[l][r]$ — trong đó lời giải của cả đoạn được ghép lại từ lời giải của các đoạn con nằm bên trong nó, qua một điểm chia $k$ thử mọi vị trí có thể. Ba bài toán kinh điển dưới đây — nhân chuỗi ma trận, ghép xâu thành palindrome, và (phần mở rộng) chia đa giác thành tam giác — dùng chung một khung quy hoạch động trên đoạn, chỉ khác nhau ở cách tính chi phí ghép hai đoạn con.
Cần nhớ trước
Em cần nhớ: quy hoạch động hai chiều $dp[i][j]$ (đã gặp ở bài dãy con chung dài nhất, khóa Nền tảng), cách chuyển một hàm đệ quy có nhớ thành bảng tính xuôi, và độ phức tạp tính theo (số trạng thái) × (chi phí mỗi lần chuyển). Bài này không cần kiến thức đồ thị.
**So với mức chuẩn:** ở khóa Nền tảng, $dp[i][j]$ luôn mang một nghĩa cố định — tiền tố $i$ ký tự ghép với tiền tố $j$ ký tự, như trong LCS — và bảng lấp đầy theo một chiều duyệt đơn giản (hàng hoặc cột tăng dần). Ở đây $dp[l][r]$ mang nghĩa "lời giải tối ưu ngay trên đoạn con $[l,r]$", và để tính nó em cần thử **mọi cách chia đoạn** thành hai nửa tại một điểm $k$ nằm giữa $l$ và $r$ — không chỉ nhìn sang một ô liền kề. Chính vòng lặp thử $k$ này đẩy độ phức tạp từ $O(n^2)$ lên $O(n^3)$: $n^2$ trạng thái $(l,r)$, mỗi trạng thái tốn $O(n)$ để thử hết các điểm chia.
Bài toán mở đầu — nhân bốn ma trận theo thứ tự nào là rẻ nhất?
Cho bốn ma trận cần nhân liên tiếp $A_1 A_2 A_3 A_4$ với kích thước lần lượt $10\times20$, $20\times50$, $50\times1$, $1\times100$ (mảng kích thước $p = [10, 20, 50, 1, 100]$, trong đó ma trận thứ $i$ có kích thước $p[i-1]\times p[i]$). Phép nhân ma trận có tính kết hợp — kết quả cuối cùng giống hệt nhau dù đặt ngoặc kiểu gì — nhưng **số phép nhân vô hướng cần thực hiện** lại khác nhau rất nhiều tùy cách đặt ngoặc. Với 4 ma trận có đúng 5 cách đặt ngoặc khác nhau; với 10 ma trận đã có tới 4862 cách. Đề bài hỏi: đặt ngoặc kiểu nào tốn ít phép nhân nhất — không phải nhân theo đúng thứ tự viết sẵn.
Ý tưởng cốt lõi — thử mọi điểm chia, tính theo độ dài tăng dần
Gọi $dp[l][r]$ là số phép nhân vô hướng ít nhất để gộp các ma trận từ vị trí $l$ đến $r$ (chỉ số mảng $p$, 0-based). Nếu điểm chia cuối cùng là $k$ — nghĩa là nhóm thành $(A_{l+1}\ldots A_{k+1})\times(A_{k+2}\ldots A_{r+1})$ — thì chi phí gồm ba phần: chi phí nhân nửa trái, chi phí nhân nửa phải, và chi phí nhân hai ma trận kết quả với nhau:
$$dp[l][r] = \min_{l \le k < r} \Big( dp[l][k] + dp[k+1][r] + p[l]\cdot p[k+1]\cdot p[r+1] \Big)$$
Vì không biết trước điểm chia nào tối ưu, em thử **tất cả** $k$ trong đoạn rồi lấy giá trị nhỏ nhất — đây là lý do cần thêm một vòng lặp so với DP hai chiều thông thường. Điều bắt buộc: để tính $dp[l][r]$, em cần $dp$ của MỌI đoạn con ngắn hơn nằm bên trong nó, nên phải tính theo thứ tự **độ dài đoạn tăng dần** — đoạn dài 1 (một ma trận, chi phí 0) trước, rồi đến đoạn dài 2, 3, ..., cho tới đoạn dài bằng cả dãy.
Ví dụ
Ví dụ 1 — Thứ tự nhân rẻ nhất cho bốn ma trận
1
Ở lớp dưới em chỉ nhân hai ma trận, không có lựa chọn thứ tự nào cả. Từ ba ma trận trở lên, số cách đặt ngoặc tăng theo dãy Catalan — thử hết bằng tay là bất khả thi ngay khi đề có trên 5-6 ma trận.
2
Áp dụng công thức $dp[l][r] = \min_k(dp[l][k]+dp[k+1][r]+p[l]p[k+1]p[r+1])$, tính theo độ dài đoạn tăng dần. Cài đặt bằng Python:
```python
def matrix_chain(p):
n = len(p) - 1 # so ma tran
dp = [[0] * n for _ in range(n)]
split = [[-1] * n for _ in range(n)]
for length in range(2, n + 1):
for l in range(0, n - length + 1):
r = l + length - 1
dp[l][r] = float('inf')
for k in range(l, r):
cost = (dp[l][k] + dp[k + 1][r]
+ p[l] * p[k + 1] * p[r + 1])
if cost < dp[l][r]:
dp[l][r] = cost
split[l][r] = k
return dp, split
```
3
Đoạn dài 2 (hai ma trận liền nhau) không cần thử điểm chia — chỉ có đúng một cách nhân. Đoạn dài 3 trở lên mới thật sự cần vòng lặp $k$, và vòng lặp đó CHỈ dùng được nếu mọi đoạn con ngắn hơn đã có sẵn giá trị — đúng là điều thứ tự "độ dài tăng dần" đảm bảo.
4
Với $p = [10, 20, 50, 1, 100]$, chạy hàm trên cho bảng $dp[l][r]$ (0-based, $l\le r$):
$dp[0][1]=10000$, $dp[1][2]=1000$, $dp[2][3]=5000$ (các đoạn dài 2) — rồi $dp[0][2]=1200$, $dp[1][3]=3000$ (đoạn dài 3) — và cuối cùng $dp[0][3]=2200$ (đoạn dài 4, đáp số). Đáng chú ý: $dp[0][2]=1200$ nhỏ hơn nhiều so với $dp[0][1]=10000$ + chi phí ghép trực tiếp — vì điểm chia $k=1$ (giữa $A_2$ và $A_3$) rẻ hơn hẳn $k=0$.
5
Bảng `split[l][r]` lưu điểm chia tối ưu tại mỗi bước, cho phép dựng lại cách đặt ngoặc bằng đệ quy: `split[0][3]=2` nghĩa là tách thành $(A_1..A_3)$ và $(A_4..A_4)$. Đệ quy tiếp tục trên từng nửa, ra kết quả cuối: $((A_1\times(A_2\times A_3))\times A_4)$ — nhóm $A_2, A_3$ (hai ma trận $20\times50$ và $50\times1$) lại với nhau TRƯỚC tiên, dù chúng không phải cặp đầu tiên trong dãy viết sẵn.
6
Đặt $dp[l][r]$ là số phép nhân vô hướng nhỏ nhất để gộp các ma trận từ vị trí $l$ đến $r$. Ta có $dp[l][l]=0$ với mọi $l$ (một ma trận không cần nhân). Xét đoạn dài 2: $dp[0][1]=p[0]p[1]p[2]=10\cdot20\cdot50=10000$, tương tự $dp[1][2]=1000$, $dp[2][3]=5000$. Xét đoạn dài 3: $dp[0][2]=\min(dp[0][0]+dp[1][2]+p[0]p[1]p[3],\; dp[0][1]+dp[2][2]+p[0]p[2]p[3])=1200$ (đạt tại $k=1$), $dp[1][3]=3000$ (đạt tại $k=1$). Xét đoạn dài 4: $dp[0][3]=\min_{k=0,1,2}(dp[0][k]+dp[k+1][3]+p[0]p[k+1]p[4])=2200$, đạt tại $k=2$. Vậy số phép nhân vô hướng nhỏ nhất là $dp[0][3]=2200$, ứng với cách đặt ngoặc $((A_1(A_2A_3))A_4)$.
7
Khung chung: trạng thái là một đoạn $[l,r]$, công thức truy hồi thử mọi điểm chia $k$, thứ tự tính theo độ dài đoạn tăng dần. Biến thể hay gặp: đổi hàm chi phí ghép (không phải luôn là tích ba số) — bài tiếp theo dùng cùng khung nhưng chi phí ghép khác hẳn.
Cả ba bài toán trong bài này — nhân chuỗi ma trận, palindrome, và đa giác — đều đi theo đúng bốn bước này, chỉ khác công thức ghép.Bước 1: mới điền xong đường chéo (một ma trận, chi phí 0) và các đoạn độ dài 2 — 10000, 1000, 5000. Các đoạn dài hơn còn để trống.Bước 2: bảng hoàn chỉnh sau khi tính hết đoạn dài 3 rồi đoạn dài 4 — đáp số nằm ở dp[0][3] = 2200.
Bài toán ghép xâu thành palindrome dùng đúng khung này, nhưng ý nghĩa của $dp[l][r]$ và công thức ghép hai đoạn con lại khác hẳn — một dấu hiệu cho thấy đây thật sự là một KHUNG chung, không phải một công thức chỉ dùng được cho ma trận.
Ví dụ
Ví dụ 2 — Ít nhất bao nhiêu ký tự cần chèn để một xâu thành palindrome
1
Đề chuẩn chỉ hỏi "xâu này có phải palindrome không" — kiểm tra bằng hai con trỏ đầu-cuối là xong. Đề này hỏi khác: nếu xâu $s="abcbda"$ CHƯA phải palindrome, cần chèn **ít nhất bao nhiêu ký tự** (chèn ở vị trí bất kỳ) để biến nó thành palindrome?
2
Gọi $dp[l][r]$ là số ký tự cần chèn ít nhất để đoạn $s[l..r]$ thành palindrome. Nếu $s[l]=s[r]$, hai đầu đã đối xứng sẵn, không cần chèn gì cho riêng cặp này — bài toán thu về đoạn con ở giữa: $dp[l][r]=dp[l+1][r-1]$. Nếu $s[l]\ne s[r]$, phải chèn thêm một ký tự để một trong hai đầu "khớp" đầu kia — chọn phương án rẻ hơn giữa chèn khớp với $s[l]$ (thu về $dp[l][r-1]$) hoặc khớp với $s[r]$ (thu về $dp[l+1][r]$):
$$dp[l][r] = \begin{cases} dp[l+1][r-1] & \text{nếu } s[l]=s[r] \\ 1 + \min(dp[l+1][r],\, dp[l][r-1]) & \text{nếu } s[l]\ne s[r]\end{cases}$$
3
Đây vẫn là dp trên đoạn: để tính $dp[l][r]$ cần $dp$ của đoạn con ngắn hơn NẰM NGAY BÊN TRONG (bớt một hoặc hai ký tự ở hai đầu), nên vẫn tính theo độ dài tăng dần. Khác nhân chuỗi ma trận ở chỗ đây KHÔNG cần thử điểm chia $k$ — chỉ có đúng một cách thu hẹp cho mỗi nhánh, nên độ phức tạp chỉ $O(n^2)$ chứ không phải $O(n^3)$.
4
Với $s="abcbda"$ (độ dài 6), bảng cho $dp[0][5]=1$ — chỉ cần chèn 1 ký tự. Cụ thể: $s[0]='a'$ và $s[5]='a'$ — hai đầu ĐÃ khớp, nên $dp[0][5]=dp[1][4]$; đoạn giữa $s[1..4]="bcbd"$ có $s[1]='b'\ne s[4]='d'$, lệch nhau nên cộng thêm 1 và lấy $\min(dp[2][4], dp[1][3])$.
5
Một cách tính độc lập: số ký tự cần chèn tối thiểu để $s$ thành palindrome LUÔN bằng $n - \text{LCS}(s, \text{đảo ngược}(s))$ — phần không thuộc dãy con chung dài nhất giữa $s$ và $s$ đảo ngược chính là phần "lệch" cần chèn để đối xứng. Với $s="abcbda"$, đảo ngược là "adbcba", LCS của hai xâu này dài $5$, nên số ký tự cần chèn là $6-5=1$ — khớp với bảng dp trên đoạn.
6
Xét $s="abcbda"$. Vì $s[0]=s[5]='a'$, ta có $dp[0][5]=dp[1][4]$. (1) Xét đoạn $[1,4]="bcbd"$: vì $s[1]\ne s[4]$, $dp[1][4]=1+\min(dp[2][4],dp[1][3])$. (2) Tính tiếp các đoạn ngắn hơn theo đúng công thức truy hồi ở trên; thay ngược vào (1) và (2) ta được $dp[1][4]=1$, do đó $dp[0][5]=1$. Kiểm tra chéo bằng công thức $n-\text{LCS}(s,s^R)$ cho cùng kết quả 1. Vậy chỉ cần chèn **1 ký tự** để "abcbda" thành palindrome.
7
Cùng khung dp trên đoạn nhưng công thức ghép khác hẳn: không có điểm chia $k$, chỉ có "thu hẹp từ hai đầu". Biến thể quen thuộc: "xâu con chung dài nhất liên tục" (longest common substring) cũng dùng dp hai chiều nhưng lấy giá trị LỚN NHẤT TRONG TOÀN BẢNG chứ không phải một góc cố định — khác một chi tiết nhỏ nhưng dễ nhầm.
Bước 1: xâu "abcbda" — đường chéo là 0 (một ký tự luôn là palindrome), các cặp liền kề (độ dài 2) đã điền xong.Bước 2: bảng hoàn chỉnh — đáp số nằm ở dp[0][5] = 1 ký tự cần chèn.
Mở rộng dành cho HSG — chia đa giác thành tam giác với chi phí nhỏ nhất
Kỹ thuật vượt chương trình
**Mở rộng dành cho HSG:** bài toán chia một đa giác lồi thành các tam giác sao cho tổng "chi phí" các đường chéo nhỏ nhất KHÔNG nằm trong yêu cầu chuẩn của Lớp 12. Ta giới thiệu vì nó là một biến thể rất tự nhiên của dp trên đoạn — chỉ cần đánh số đỉnh đa giác theo vòng thay vì vẽ hình, mọi thứ quy về đúng khung $dp[i][j]$ đã học ở Ví dụ 1 và 2. Tiên quyết: nắm chắc cách dp trên đoạn thử điểm chia $k$ ở Ví dụ 1.
Ví dụ
Ví dụ 3 — Chia đa giác lồi thành tam giác, chi phí nhỏ nhất
1
Một đa giác lồi có 5 đỉnh, đánh số $0,1,\ldots,4$ theo vòng, mỗi đỉnh $i$ mang một trọng số $w[i]$ (với $w = [1, 2, 3, 4, 5]$). Chia đa giác thành các tam giác bằng các đường chéo không cắt nhau, sao cho tổng "chi phí" của các tam giác nhỏ nhất — chi phí một tam giác có ba đỉnh $i,k,j$ là $w[i]\cdot w[k]\cdot w[j]$.
2
Gọi $dp[i][j]$ là chi phí nhỏ nhất để tam giác hóa phần đa giác giới hạn bởi cạnh $(i,j)$ và các đỉnh $i, i+1, \ldots, j$ (một "quạt" đỉnh liên tiếp). Với mỗi cách chọn đỉnh $k$ nằm giữa $i$ và $j$ để tạo tam giác $(i,k,j)$, phần còn lại tách thành hai đa giác con nhỏ hơn:
$$dp[i][j] = \min_{i<k<j}\Big(dp[i][k] + dp[k][j] + w[i]\cdot w[k]\cdot w[j]\Big)$$
với cơ sở $dp[i][j]=0$ khi $j-i<2$ (cạnh kề hoặc trùng đỉnh, chưa đủ ba đỉnh để tạo tam giác).
3
So với Ví dụ 1, vai trò của "đoạn $[l,r]$" nay là "cung đỉnh $[i,j]$", và vai trò của "ghép hai nửa dãy ma trận" nay là "ghép hai đa giác con quanh tam giác $(i,k,j)$" — cùng một khung tư duy, chỉ thay công thức chi phí ghép và điều kiện cơ sở.
4
Với $w=[1, 2, 3, 4, 5]$, bảng cho $dp[0][4]=38$ — chi phí tam giác hóa nhỏ nhất.
5
Ta có $dp[i][j]=0$ với $j-i<2$. Với $j-i=2$: $dp[0][2]=w[0]w[1]w[2]=6$, $dp[1][3]=w[1]w[2]w[3]=24$, $dp[2][4]=w[2]w[3]w[4]=60$. Với $j-i=3$: $dp[0][3]=\min_{k=1,2}(dp[0][k]+dp[k][3]+w[0]w[k]w[3])=18$, tương tự $dp[1][4]=64$. Với $j-i=4$: $dp[0][4]=\min_{k=1,2,3}(dp[0][k]+dp[k][4]+w[0]w[k]w[4])=38$. Vậy chi phí tam giác hóa nhỏ nhất là $dp[0][4]=38$.
6
Nhận ra một bài toán là dp trên đoạn qua ba dấu hiệu: (1) đối tượng có thể đánh số tuần tự (chỉ số mảng, đỉnh đa giác, ký tự trong xâu), (2) lời giải trên một đoạn/cung phụ thuộc vào lời giải các đoạn con bên trong, (3) có một "điểm chia" hoặc "điểm thu hẹp" tạo ra hai bài toán con độc lập.
Bước áp dụng: cùng khung dp trên đoạn như Ví dụ 1, chỉ đổi công thức ghép — đáp số dp[0][4] = 38.
Bẫy thường gặp
Ba bẫy hay gặp: (1) tính bảng theo thứ tự $l$ hoặc $r$ tăng dần thay vì theo ĐỘ DÀI đoạn tăng dần — sẽ đọc phải ô chưa được tính, cho kết quả sai hoặc lỗi; (2) quên thử ĐỦ mọi điểm chia $k$, chỉ thử một vài điểm "có vẻ hợp lý" — bài toán dp trên đoạn không có tính tham lam, phải thử hết; (3) nhầm chỉ số 0-based và 1-based khi ánh xạ từ đề bài (ma trận $A_1,\ldots,A_n$) sang mảng $p[0..n]$ trong code — sai một chỉ số làm lệch toàn bộ công thức $p[l]\cdot p[k+1]\cdot p[r+1]$.
Đo trên máy thật: n=30 mất 0,43 ms, n=60 mất 3,12 ms (tăng ×7,3 khi n tăng ×2 — gần đúng $2^3=8$ lần theo $O(n^3)$), n=150 mất 46,66 ms.
Luyện tập có hướng dẫn
Luyện tập độc lập
Thử thách
Tóm tắt
Quy hoạch động trên đoạn dùng trạng thái $dp[l][r]$ — lời giải tối ưu ngay trên đoạn con $[l,r]$ — và một công thức truy hồi thử mọi điểm chia (hoặc thu hẹp từ hai đầu), luôn tính theo thứ tự **độ dài đoạn tăng dần**. Ba bài toán hôm nay — nhân chuỗi ma trận ($O(n^3)$, có điểm chia), ghép xâu thành palindrome ($O(n^2)$, thu hẹp hai đầu), và chia đa giác thành tam giác (cùng khung với nhân chuỗi ma trận, chỉ đổi công thức chi phí) — đều là ứng dụng của cùng một khung tư duy.
Bài sau giữ nguyên tinh thần "trạng thái là một tập" nhưng đổi hẳn cách biểu diễn: thay vì một đoạn liên tục $[l,r]$, trạng thái trở thành một TẬP CON bất kỳ của các phần tử — mã hóa bằng một số nguyên nhị phân gọi là bitmask.
Sau bài này, em giải được một lớp bài toán tối ưu trên một đoạn liên tục bằng quy hoạch động hai chiều dp[l][r] — trong đó lời giải của cả đoạn được ghép lại từ lời giải của các đoạn con nằm bên trong nó, qua một điểm chia k thử mọi vị trí có thể. Ba bài toán kinh điển dưới đây — nhân chuỗi ma trận, ghép xâu thành palindrome, và (phần mở rộng) chia đa giác thành tam giác — dùng chung một khung quy hoạch động trên đoạn, chỉ khác nhau ở cách tính chi phí ghép hai đoạn con.
Em cần nhớ: quy hoạch động hai chiều dp[i][j] (đã gặp ở bài dãy con chung dài nhất, khóa Nền tảng), cách chuyển một hàm đệ quy có nhớ thành bảng tính xuôi, và độ phức tạp tính theo (số trạng thái) × (chi phí mỗi lần chuyển). Bài này không cần kiến thức đồ thị.
So với mức chuẩn: ở khóa Nền tảng, dp[i][j] luôn mang một nghĩa cố định — tiền tố i ký tự ghép với tiền tố j ký tự, như trong LCS — và bảng lấp đầy theo một chiều duyệt đơn giản (hàng hoặc cột tăng dần). Ở đây dp[l][r] mang nghĩa "lời giải tối ưu ngay trên đoạn con [l,r]", và để tính nó em cần thử mọi cách chia đoạn thành hai nửa tại một điểm k nằm giữa l và r — không chỉ nhìn sang một ô liền kề. Chính vòng lặp thử k này đẩy độ phức tạp từ O(n2) lên O(n3): n2 trạng thái (l,r), mỗi trạng thái tốn O(n) để thử hết các điểm chia.
Cho bốn ma trận cần nhân liên tiếp A1A2A3A4 với kích thước lần lượt 10×20, 20×50, 50×1, 1×100 (mảng kích thước p=[10,20,50,1,100], trong đó ma trận thứ i có kích thước p[i−1]×p[i]). Phép nhân ma trận có tính kết hợp — kết quả cuối cùng giống hệt nhau dù đặt ngoặc kiểu gì — nhưng số phép nhân vô hướng cần thực hiện lại khác nhau rất nhiều tùy cách đặt ngoặc. Với 4 ma trận có đúng 5 cách đặt ngoặc khác nhau; với 10 ma trận đã có tới 4862 cách. Đề bài hỏi: đặt ngoặc kiểu nào tốn ít phép nhân nhất — không phải nhân theo đúng thứ tự viết sẵn.
Gọi dp[l][r] là số phép nhân vô hướng ít nhất để gộp các ma trận từ vị trí l đến r (chỉ số mảng p, 0-based). Nếu điểm chia cuối cùng là k — nghĩa là nhóm thành (Al+1…Ak+1)×(Ak+2…Ar+1) — thì chi phí gồm ba phần: chi phí nhân nửa trái, chi phí nhân nửa phải, và chi phí nhân hai ma trận kết quả với nhau:
Vì không biết trước điểm chia nào tối ưu, em thử tất cảk trong đoạn rồi lấy giá trị nhỏ nhất — đây là lý do cần thêm một vòng lặp so với DP hai chiều thông thường. Điều bắt buộc: để tính dp[l][r], em cần dp của MỌI đoạn con ngắn hơn nằm bên trong nó, nên phải tính theo thứ tự độ dài đoạn tăng dần — đoạn dài 1 (một ma trận, chi phí 0) trước, rồi đến đoạn dài 2, 3, ..., cho tới đoạn dài bằng cả dãy.
Áp dụng công thức dp[l][r]=mink(dp[l][k]+dp[k+1][r]+p[l]p[k+1]p[r+1]), tính theo độ dài đoạn tăng dần. Cài đặt bằng Python:
def matrix_chain(p):
n = len(p) - 1 # so ma tran
dp = [[0] * n for _ in range(n)]
split = [[-1] * n for _ in range(n)]
for length in range(2, n + 1):
for l in range(0, n - length + 1):
r = l + length - 1
dp[l][r] = float('inf')
for k in range(l, r):
cost = (dp[l][k] + dp[k + 1][r]
+ p[l] * p[k + 1] * p[r + 1])
if cost < dp[l][r]:
dp[l][r] = cost
split[l][r] = k
return dp, split
Đoạn dài 2 (hai ma trận liền nhau) không cần thử điểm chia — chỉ có đúng một cách nhân. Đoạn dài 3 trở lên mới thật sự cần vòng lặp k, và vòng lặp đó CHỈ dùng được nếu mọi đoạn con ngắn hơn đã có sẵn giá trị — đúng là điều thứ tự "độ dài tăng dần" đảm bảo.
Với p=[10,20,50,1,100], chạy hàm trên cho bảng dp[l][r] (0-based, l≤r):
dp[0][1]=10000, dp[1][2]=1000, dp[2][3]=5000 (các đoạn dài 2) — rồi dp[0][2]=1200, dp[1][3]=3000 (đoạn dài 3) — và cuối cùng dp[0][3]=2200 (đoạn dài 4, đáp số). Đáng chú ý: dp[0][2]=1200 nhỏ hơn nhiều so với dp[0][1]=10000 + chi phí ghép trực tiếp — vì điểm chia k=1 (giữa A2 và A3) rẻ hơn hẳn k=0.
Bảng split[l][r] lưu điểm chia tối ưu tại mỗi bước, cho phép dựng lại cách đặt ngoặc bằng đệ quy: split[0][3]=2 nghĩa là tách thành (A1..A3) và (A4..A4). Đệ quy tiếp tục trên từng nửa, ra kết quả cuối: ((A1×(A2×A3))×A4) — nhóm A2,A3 (hai ma trận 20×50 và 50×1) lại với nhau TRƯỚC tiên, dù chúng không phải cặp đầu tiên trong dãy viết sẵn.
Đặt dp[l][r] là số phép nhân vô hướng nhỏ nhất để gộp các ma trận từ vị trí l đến r. Ta có dp[l][l]=0 với mọi l (một ma trận không cần nhân). Xét đoạn dài 2: dp[0][1]=p[0]p[1]p[2]=10⋅20⋅50=10000, tương tự dp[1][2]=1000, dp[2][3]=5000. Xét đoạn dài 3: dp[0][2]=min(dp[0][0]+dp[1][2]+p[0]p[1]p[3],dp[0][1]+dp[2][2]+p[0]p[2]p[3])=1200 (đạt tại k=1), dp[1][3]=3000 (đạt tại k=1). Xét đoạn dài 4: dp[0][3]=mink=0,1,2(dp[0][k]+dp[k+1][3]+p[0]p[k+1]p[4])=2200, đạt tại k=2. Vậy số phép nhân vô hướng nhỏ nhất là dp[0][3]=2200, ứng với cách đặt ngoặc ((A1(A2A3))A4).
Khung chung: trạng thái là một đoạn [l,r], công thức truy hồi thử mọi điểm chia k, thứ tự tính theo độ dài đoạn tăng dần. Biến thể hay gặp: đổi hàm chi phí ghép (không phải luôn là tích ba số) — bài tiếp theo dùng cùng khung nhưng chi phí ghép khác hẳn.
Bài toán ghép xâu thành palindrome dùng đúng khung này, nhưng ý nghĩa của dp[l][r] và công thức ghép hai đoạn con lại khác hẳn — một dấu hiệu cho thấy đây thật sự là một KHUNG chung, không phải một công thức chỉ dùng được cho ma trận.
Đề chuẩn chỉ hỏi "xâu này có phải palindrome không" — kiểm tra bằng hai con trỏ đầu-cuối là xong. Đề này hỏi khác: nếu xâu s="abcbda" CHƯA phải palindrome, cần chèn ít nhất bao nhiêu ký tự (chèn ở vị trí bất kỳ) để biến nó thành palindrome?
Gọi dp[l][r] là số ký tự cần chèn ít nhất để đoạn s[l..r] thành palindrome. Nếu s[l]=s[r], hai đầu đã đối xứng sẵn, không cần chèn gì cho riêng cặp này — bài toán thu về đoạn con ở giữa: dp[l][r]=dp[l+1][r−1]. Nếu s[l]=s[r], phải chèn thêm một ký tự để một trong hai đầu "khớp" đầu kia — chọn phương án rẻ hơn giữa chèn khớp với s[l] (thu về dp[l][r−1]) hoặc khớp với s[r] (thu về dp[l+1][r]):
Đây vẫn là dp trên đoạn: để tính dp[l][r] cần dp của đoạn con ngắn hơn NẰM NGAY BÊN TRONG (bớt một hoặc hai ký tự ở hai đầu), nên vẫn tính theo độ dài tăng dần. Khác nhân chuỗi ma trận ở chỗ đây KHÔNG cần thử điểm chia k — chỉ có đúng một cách thu hẹp cho mỗi nhánh, nên độ phức tạp chỉ O(n2) chứ không phải O(n3).
Với s="abcbda" (độ dài 6), bảng cho dp[0][5]=1 — chỉ cần chèn 1 ký tự. Cụ thể: s[0]=′a′ và s[5]=′a′ — hai đầu ĐÃ khớp, nên dp[0][5]=dp[1][4]; đoạn giữa s[1..4]="bcbd" có s[1]=′b′=s[4]=′d′, lệch nhau nên cộng thêm 1 và lấy min(dp[2][4],dp[1][3]).
Một cách tính độc lập: số ký tự cần chèn tối thiểu để s thành palindrome LUÔN bằng n−LCS(s,đảo ngược(s)) — phần không thuộc dãy con chung dài nhất giữa s và s đảo ngược chính là phần "lệch" cần chèn để đối xứng. Với s="abcbda", đảo ngược là "adbcba", LCS của hai xâu này dài 5, nên số ký tự cần chèn là 6−5=1 — khớp với bảng dp trên đoạn.
Xét s="abcbda". Vì s[0]=s[5]=′a′, ta có dp[0][5]=dp[1][4]. (1) Xét đoạn [1,4]="bcbd": vì s[1]=s[4], dp[1][4]=1+min(dp[2][4],dp[1][3]). (2) Tính tiếp các đoạn ngắn hơn theo đúng công thức truy hồi ở trên; thay ngược vào (1) và (2) ta được dp[1][4]=1, do đó dp[0][5]=1. Kiểm tra chéo bằng công thức n−LCS(s,sR) cho cùng kết quả 1. Vậy chỉ cần chèn 1 ký tự để "abcbda" thành palindrome.
Cùng khung dp trên đoạn nhưng công thức ghép khác hẳn: không có điểm chia k, chỉ có "thu hẹp từ hai đầu". Biến thể quen thuộc: "xâu con chung dài nhất liên tục" (longest common substring) cũng dùng dp hai chiều nhưng lấy giá trị LỚN NHẤT TRONG TOÀN BẢNG chứ không phải một góc cố định — khác một chi tiết nhỏ nhưng dễ nhầm.
Mở rộng dành cho HSG: bài toán chia một đa giác lồi thành các tam giác sao cho tổng "chi phí" các đường chéo nhỏ nhất KHÔNG nằm trong yêu cầu chuẩn của Lớp 12. Ta giới thiệu vì nó là một biến thể rất tự nhiên của dp trên đoạn — chỉ cần đánh số đỉnh đa giác theo vòng thay vì vẽ hình, mọi thứ quy về đúng khung dp[i][j] đã học ở Ví dụ 1 và 2. Tiên quyết: nắm chắc cách dp trên đoạn thử điểm chia k ở Ví dụ 1.
Một đa giác lồi có 5 đỉnh, đánh số 0,1,…,4 theo vòng, mỗi đỉnh i mang một trọng số w[i] (với w=[1,2,3,4,5]). Chia đa giác thành các tam giác bằng các đường chéo không cắt nhau, sao cho tổng "chi phí" của các tam giác nhỏ nhất — chi phí một tam giác có ba đỉnh i,k,j là w[i]⋅w[k]⋅w[j].
Gọi dp[i][j] là chi phí nhỏ nhất để tam giác hóa phần đa giác giới hạn bởi cạnh (i,j) và các đỉnh i,i+1,…,j (một "quạt" đỉnh liên tiếp). Với mỗi cách chọn đỉnh k nằm giữa i và j để tạo tam giác (i,k,j), phần còn lại tách thành hai đa giác con nhỏ hơn:
với cơ sở dp[i][j]=0 khi j−i<2 (cạnh kề hoặc trùng đỉnh, chưa đủ ba đỉnh để tạo tam giác).
So với Ví dụ 1, vai trò của "đoạn [l,r]" nay là "cung đỉnh [i,j]", và vai trò của "ghép hai nửa dãy ma trận" nay là "ghép hai đa giác con quanh tam giác (i,k,j)" — cùng một khung tư duy, chỉ thay công thức chi phí ghép và điều kiện cơ sở.
Với w=[1,2,3,4,5], bảng cho dp[0][4]=38 — chi phí tam giác hóa nhỏ nhất.
Ta có dp[i][j]=0 với j−i<2. Với j−i=2: dp[0][2]=w[0]w[1]w[2]=6, dp[1][3]=w[1]w[2]w[3]=24, dp[2][4]=w[2]w[3]w[4]=60. Với j−i=3: dp[0][3]=mink=1,2(dp[0][k]+dp[k][3]+w[0]w[k]w[3])=18, tương tự dp[1][4]=64. Với j−i=4: dp[0][4]=mink=1,2,3(dp[0][k]+dp[k][4]+w[0]w[k]w[4])=38. Vậy chi phí tam giác hóa nhỏ nhất là dp[0][4]=38.
Ba bẫy hay gặp: (1) tính bảng theo thứ tự l hoặc r tăng dần thay vì theo ĐỘ DÀI đoạn tăng dần — sẽ đọc phải ô chưa được tính, cho kết quả sai hoặc lỗi; (2) quên thử ĐỦ mọi điểm chia k, chỉ thử một vài điểm "có vẻ hợp lý" — bài toán dp trên đoạn không có tính tham lam, phải thử hết; (3) nhầm chỉ số 0-based và 1-based khi ánh xạ từ đề bài (ma trận A1,…,An) sang mảng p[0..n] trong code — sai một chỉ số làm lệch toàn bộ công thức p[l]⋅p[k+1]⋅p[r+1].
Đo trên máy thật: n=30 mất 0,43 ms, n=60 mất 3,12 ms (tăng ×7,3 khi n tăng ×2 — gần đúng 23=8 lần theo O(n3)), n=150 mất 46,66 ms.
Quy hoạch động trên đoạn dùng trạng thái dp[l][r] — lời giải tối ưu ngay trên đoạn con [l,r] — và một công thức truy hồi thử mọi điểm chia (hoặc thu hẹp từ hai đầu), luôn tính theo thứ tự độ dài đoạn tăng dần. Ba bài toán hôm nay — nhân chuỗi ma trận (O(n3), có điểm chia), ghép xâu thành palindrome (O(n2), thu hẹp hai đầu), và chia đa giác thành tam giác (cùng khung với nhân chuỗi ma trận, chỉ đổi công thức chi phí) — đều là ứng dụng của cùng một khung tư duy.
Bài sau giữ nguyên tinh thần "trạng thái là một tập" nhưng đổi hẳn cách biểu diễn: thay vì một đoạn liên tục [l,r], trạng thái trở thành một TẬP CON bất kỳ của các phần tử — mã hóa bằng một số nguyên nhị phân gọi là bitmask.