Quy hoạch động, hay vì sao đừng tính lại cùng một thứ

Đếm lời gọi thậtBa con số cùng lúcCó mốc sai âm thầm

Quy hoạch động, hay vì sao đừng tính lại cùng một thứ

Cùng một công thức, cùng một đáp số, mà cách này gọi 2.692.537 lần còn cách kia gọi 59 lần. Bài này bắt bạn đếm cả ba con số cùng lúc: lời gọi, ô nhớ, phép cộng. Vì chỉ đọc một con số thì bạn sẽ tin rằng có bữa trưa miễn phí.

Có một đoạn mã bốn dòng mà hầu như ai học lập trình cũng viết: hàm Fibonacci đệ quy. fib(n) gọi fib(n-1) và fib(n-2), hai ca cơ sở là fib(0) = 0 và fib(1) = 1. Nó đúng, nó ngắn, nó khớp từng chữ với định nghĩa toán học. Và nó là một trong những đoạn mã tệ nhất bạn có thể viết.

Tệ tới mức nào thì phải đếm mới biết, nên sim dưới đây đếm. Không phải đếm theo công thức tăng trưởng, mà chạy hàm đó thật rồi ghi lại từng lời gọi. Ở n = 30 nó cần 2.692.537 lời gọi hàm để trả về một con số nhỏ xíu là 832.040. Cùng bài toán ấy, thêm một bảng ghi nhớ vào, còn 59 lời gọi.

Nhưng bài này không phải chỗ để ca ngợi quy hoạch động. Nó là chỗ để bạn nhìn thấy cái giá. Con số 59 kia mua bằng 31 ô bảng cộng một ngăn xếp đệ quy sâu 30 khung, tức 61 ô nhớ, trong khi một vòng lặp làm đúng cùng việc chỉ cần 2 ô. Cho nên câu đúng không phải là "quy hoạch động nhanh hơn". Câu đúng là: nó đổi bộ nhớ lấy thời gian, và bạn phải nhìn cả hai cột mới biết mình vừa đổi được gì.

Quy hoạch động · đếm lời gọi, ô nhớ và phép cộng cùng một lúc

Chỉ số n của Fibonacci

Đệ quy thuần 2.692.537 lời gọiGhi nhớ 59 lời gọiLập bảng cuộn 2 ô nhớ

1 · Bốn cách tính fib(30) ✎ kéo núm n ở trên

cách làm	số lời gọi	số phép cộng	ô nhớ bảng	khung ngăn xếp	tổng ô nhớ	kết quả
đệ quy thuần	2.692.537	1.346.268	0	30	30	832.040
ghi nhớ, từ trên xuống	59	29	31	30	61	832.040
lập bảng, từ dưới lên	0 · 31 bước lặp	29	31	0	31	832.040
lập bảng cuộn, hai ô nhớ	0 · 31 bước lặp	29	2	0	2	832.040

Ở n = 30, đệ quy thuần gọi 2.692.537 lần còn ghi nhớ chỉ gọi 59 lần, tức ít hơn 45.636,22 lần. Nhưng hãy đọc tiếp hai cột bên phải: ghi nhớ giữ 31 ô bảng và vẫn xếp 30 khung ngăn xếp, tổng 61 ô, trong khi lập bảng cuộn chỉ cần 2 ô và không có khung nào. Chênh lệch bộ nhớ là 59 ô. Và số phép cộng của ghi nhớ với lập bảng bằng nhau khít, 29 cả hai: cái ghi nhớ tiết kiệm là lời gọi, không phải phép tính.

Ở n = 30 kết quả còn đúng tuyệt đối: 832.040 khớp từng chữ số với giá trị tính bằng số nguyên chính xác. Kéo n lên tới 79 thì hộp này đổi thành cảnh báo.

2 · Cây gọi, và những nhánh ghi nhớ cắt đi ✎ sửa được

n của cây được vẽ

Cây dưới đây là cây gọi đầy đủ của đệ quy thuần trên fib(6): 25 nút, mỗi nút đúng một lời gọi, 13 lá, 6 tầng. Màu cho biết lượt chạy có ghi nhớ làm gì với nút đó.

✓ tính thật↺ lấy lại từ bảng nhớ✗ không bao giờ được gọi

Lượt ghi nhớ chỉ đi vào 11 trong 25 nút: 7 nút phải tính thật (đúng bằng số bài con khác nhau, tức 7 giá trị từ 0 tới 6), 4 nút chỉ tra bảng rồi trả về ngay, và 14 nút không bao giờ được gọi. Những nút bị cắt không phải là nút rẻ: mỗi nút bị cắt mang theo cả cây con dưới nó. Đó là chỗ 45.636,22 lần ở mục 1 sinh ra, chỉ là ở đây bạn đếm được từng nút.

3 · Mốc mà kết quả sai nhưng không ai báo đo được, không phải nhớ được

Số nguyên an toàn lớn nhất của JavaScript là 2⁵³ - 1, tức 9.007.199.254.740.991. Bảng dưới đây so từng bước: cột máy in ra là kết quả của vòng lặp viết bằng số thường, cột giá trị đúng tính bằng số nguyên chính xác. Mốc không phải do tôi gõ vào: phần tính đi từ n = 0 lên và tìm chỗ hai cột rời nhau.

n	máy in ra	giá trị đúng	lệch	vượt 2^53 - 1 chưa	kết luận
75	2.111.485.077.978.050	2.111.485.077.978.050	0	chưa	✓ đúng
76	3.416.454.622.906.707	3.416.454.622.906.707	0	chưa	✓ đúng
77	5.527.939.700.884.757	5.527.939.700.884.757	0	chưa	✓ đúng
78	8.944.394.323.791.464	8.944.394.323.791.464	0	chưa	✓ đúng
79	14.472.334.024.676.220	14.472.334.024.676.221	-1	đã vượt	✗ SAI, không báo lỗi
80	23.416.728.348.467.684	23.416.728.348.467.685	-1	đã vượt	✗ SAI, không báo lỗi
81	37.889.062.373.143.900	37.889.062.373.143.906	-2	đã vượt	✗ SAI, không báo lỗi
82	61.305.790.721.611.580	61.305.790.721.611.591	-7	đã vượt	✗ SAI, không báo lỗi

fib(78) là số Fibonacci cuối cùng còn đúng: 8.944.394.323.791.464, vẫn nhỏ hơn 9.007.199.254.740.991. Từ fib(79) trở đi kết quả sai, và cái đáng sợ không phải là sai nhiều: nó lệch đúng 1 đơn vị, không ngoại lệ, không cảnh báo, không nhật ký. Một chương trình như thế chạy được, in ra một con số dài trông rất đáng tin, và không ai biết. Ba cách tính ở mục 1 đều chịu chung mốc này, vì cả ba đều cộng những số thực dấu phẩy động y như nhau.

4 · Đổi tiền, và O(n·m) là một con số cụ thể ✎ sửa được

Mệnh giá, cách nhau bằng dấu cáchSố tiền cần đổiĐã điền tới ô thứ

Ô ở hàng i cột a là số cách đổi đúng a đồng khi chỉ được dùng i mệnh giá đầu tiên. Bảng có 5 hàng nhân 21 cột = 105 ô, và phần tính đã điền đúng 105 ô. Đang hiện 105 ô đầu theo thứ tự điền. Nhấp một ô để xem nó lấy số từ đâu.

mệnh giá được dùng	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
chưa đồng nào	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
thêm đồng 1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
thêm đồng 2	1	1	2	2	3	3	4	4	5	5	6	6	7	7	8	8	9	9	10	10	11
thêm đồng 5	1	1	2	2	3	4	5	6	7	8	10	11	13	14	16	18	20	22	24	26	29
thêm đồng 10	1	1	2	2	3	4	5	6	7	8	11	12	15	16	19	22	25	28	31	34	40

Ô đang chọn là hàng 4, cột 20, ô thứ 105 theo thứ tự điền, giá trị 40. Nó bằng 29 (ô ngay trên, tức không dùng đồng 10 lần nào nữa) cộng 11 (ô cách 10 cột về bên trái, tức dùng thêm một đồng 10), ra 40.

Đáp số là ô góc dưới bên phải: có 40 cách đổi 20 bằng các mệnh giá 1, 2, 5, 10. Đệ quy thuần cho đúng cùng đáp số nhưng phải gọi 586 lần (đếm bằng cách chạy thật), tức 5,58 lần số ô của bảng. Chú ý điều mà bài Fibonacci chưa cho thấy: ở đây quy hoạch động không tối ưu hoá một hàm đệ quy có sẵn, nó là cách duy nhất khiến bài toán chạy được ở số tiền lớn.

số tiền	số cách đổi	ô bảng phải điền	lời gọi của đệ quy thuần	đắt hơn bảng bao nhiêu
10	11	55	100	1,82 lần
20	40	105	586	5,58 lần
40	195	205	4.879	23,80 lần
60	546	305	19.200	62,95 lần
80	1.173	405	53.069	131,03 lần
100	2.156	505	119.206	236,05 lần

Cột ô bảng tăng theo đường thẳng, đúng (5) × (số tiền + 1). Cột lời gọi thì không. Đó là toàn bộ nội dung của câu “O(n·m) thay vì hàm mũ”, chỉ là ở dạng những con số bạn đếm được. Vùng quét cố định ở 10, 20, 40, 60, 80, 100 và dùng đúng bộ mệnh giá bạn đang gõ.

5 · Hai điều kiện, một đo được và một bị phá vỡ

Điều kiện thứ nhất: bài con phải gối nhau. Đo nó bằng cách lấy số lời gọi chia cho số bài con khác nhau. Bằng 1 nghĩa là mỗi bài con chỉ được giải một lần, và khi ấy một bảng ghi nhớ chẳng có gì để nhớ.

bài toán	số lời gọi	bài con khác nhau	mỗi bài con bị giải lại	ghi nhớ có cứu được không
fib(30) bằng đệ quy thuần	2.692.537	31	86.856,03 lần	✓ có, rất nhiều
sắp xếp trộn trên 30 phần tử	59	59	1,00 lần	✗ không, gối nhau bằng 0

Sắp xếp trộn cũng là chia bài lớn thành bài con, cũng đệ quy, cũng “chia để trị”. Nhưng hai nửa của nó không dùng chung một phần tử nào, nên mỗi đoạn chỉ bị sắp một lần và tỉ lệ giải lại đứng ở đúng 1,00. Ghi nhớ nó chỉ tốn bộ nhớ mà không cắt được một lời gọi nào. Đây là chỗ phân biệt chia để trị với quy hoạch động: cùng là đệ quy trên bài con, khác nhau ở chỗ bài con có gặp lại nhau hay không.

Điều kiện thứ hai: cấu trúc con tối ưu. Lời giải tối ưu của bài lớn phải được lắp từ lời giải tối ưu của bài con. Nghe hiển nhiên tới mức người ta bỏ qua không kiểm, nên đây là một đồ thị nhỏ mà nó sai. Bài toán: tìm đường đi dài nhất từ s tới t, không được lặp lại đỉnh nào.

đường đi	trọng số	hợp lệ không
dài nhất từ s tới u: s → t → u	101	✓ đường đi, không lặp đỉnh
công thức gộp: s → t → u → t	102	✗ KHÔNG phải đường đi: đỉnh t đi qua hai lần
cả 2 đường đi thật từ s tới t: s → x → u → t	3	✓ đường đi
và: s → t	1	✓ đường đi

Đường dài nhất từ s tới u là s → t → u, trọng số 101. Công thức truy hồi tự nhiên nói: đường dài nhất tới t bằng đường dài nhất tới một đỉnh liền trước cộng cung cuối, tức 101 + 1 = 102. Nhưng phần tính đã liệt kê hết đường đi từ s tới t, và đường nặng nhất chỉ được 3. Không có đường nào nặng 102, vì lối mà công thức mô tả là s → t → u → t, đi qua đỉnh t hai lần. Lời giải tối ưu của bài con đã tiêu mất chính cái đỉnh mà bài lớn còn cần, nên nó không lắp vào được. Với đường đi ngắn nhất thì công thức ấy đúng, và đó mới là điều đáng nhớ: cấu trúc con tối ưu là một tính chất của bài toán, phải kiểm từng bài, không phải một đặc tính của kỹ thuật.

Sim này không làm được gì

• Nó đếm lời gọi, ô nhớ và phép cộng, nó không đo giây. Và một lời gọi hàm đắt hơn một vòng lặp thật sự: nó phải đẩy tham số, lưu địa chỉ trở về, cấp khung mới. Nên khoảng cách giữa đệ quy và lập bảng ngoài đời còn xa hơn con số ở đây, chứ không gần hơn.
• Cột tổng ô nhớ cộng ô bảng với khung ngăn xếp như thể chúng bằng giá. Đó là một quy ước của bài này, và là quy ước rộng tay với đệ quy: một khung ngăn xếp chứa cả tham số, biến cục bộ và địa chỉ trở về, nên nó đắt hơn một ô số nguyên.
• Ở n > 30 thì ba con số của hàng đệ quy thuần không đến từ một lượt chạy thật, vì chạy thật sẽ treo trang. Chúng đến từ công thức đóng calls = 2·fib(n+1) - 1 và adds = fib(n+1) - 1, mà cổng kiểm đã đối chiếu với lượt chạy thật ở cả 31 giá trị n từ 0 tới 30. Hàng đó cũng không in ra kết quả, vì không có lượt chạy nào để lấy.
• Mốc sai ở n = 79 là mốc của số thực dấu phẩy động 64 bit, không phải của bài toán Fibonacci. Cùng đoạn mã ấy viết bằng long long của C++ còn đúng tới fib(92), còn Python thì số nguyên không tràn nên nó đúng mãi. Đổi kiểu dữ liệu là đổi mốc.
• Bài đổi tiền ở đây đếm số cách đổi, không tìm cách dùng ít đồng nhất. Hai bài khác nhau, hai bảng khác nhau, chỉ trùng nhau ở chỗ đều lấp bảng.
• Cây gọi chỉ vẽ tới n = 9. Ở n = 30 nó có 2.692.537 nút, không màn hình nào vẽ nổi, nên đừng đọc cái cây nhỏ như thể nó là cây thật ở n lớn.
• Phản ví dụ đường đi dài nhất chỉ chứng minh một điều: công thức gộp ấy sai trên đồ thị ấy. Nó không nói gì về việc bài đường đi dài nhất khó tới đâu, cũng không nói mọi bài tối đa hoá đều hỏng.
• Số ngẫu nhiên: không có. Không một lời gọi Math.random nào trong phần tính, nên cùng cấu hình luôn cho cùng con số, và bạn kiểm lại được bằng tay.

Kéo núm n ở trên và nhìn ba con số cùng lúc: số lời gọi, số ô nhớ, số phép cộng. Quy hoạch động không miễn phí, nó đổi bộ nhớ lấy thời gian, và cột ô nhớ là chỗ trả tiền. Mọi con số dưới đây là kết quả của một lượt chạy thật, trừ những chỗ có ghi rõ là suy từ công thức đã đối chiếu.

Ba con số, và vì sao không được đọc rời

Ở trạng thái mở bài, n = 30, và bảng ở mục 1 nói bốn chuyện khác nhau về đúng một phép tính.

Đệ quy thuần gọi 2.692.537 lần, cộng 1.346.268 lần, giữ 0 ô bảng, xếp 30 khung ngăn xếp. Hai con số đầu không phải trùng hợp: cây gọi của nó là một cây nhị phân đầy, mỗi nút trong ứng với đúng một phép cộng, nên số lời gọi luôn bằng hai lần số phép cộng cộng một. Bạn kiểm lại được ngay: 2 × 1.346.268 + 1 = 2.692.537.

Ghi nhớ gọi 59 lần. Trong 59 lời gọi ấy, 31 lần phải tính thật, đúng bằng số bài con khác nhau, tức 31 giá trị từ fib(0) tới fib(30); 28 lần còn lại chỉ tra bảng rồi trả về ngay. Nó cộng 29 lần, giữ 31 ô bảng, và vẫn xếp 30 khung ngăn xếp, vì nó vẫn là đệ quy. Tổng bộ nhớ 61 ô.

Lập bảng không gọi hàm lần nào. Nó đi 31 bước lặp, cộng 29 lần, giữ 31 ô, ngăn xếp 0 khung.

Lập bảng cuộn đi đúng 31 bước lặp như trên, cộng đúng 29 lần như trên, và giữ 2 ô. Hai ô, ở mọi n từ 1 tới 90, không phải chỉ ở n = 30.

Ba điều đáng dừng lại.

Thứ nhất, ghi nhớ tiết kiệm lời gọi, không tiết kiệm phép tính. Số phép cộng của ghi nhớ và của lập bảng bằng nhau khít, 29 cả hai, và điều đó đúng ở mọi n. Việc thật sự phải làm là 29 phép cộng; 2.692.537 lời gọi kia chỉ là 2.692.478 lần đi lại vô ích.

Thứ hai, ghi nhớ trả tiền bằng bộ nhớ, và trả hai lần: một lần cho bảng, một lần cho ngăn xếp. So với lập bảng cuộn nó tốn thêm 59 ô. Con số 59 đó bằng đúng số lời gọi của nó, và đây là một đẳng thức chứ không phải trùng hợp: bảng n + 1 ô cộng ngăn xếp n khung trừ đi 2 ô của bản cuộn ra 2n - 1, mà 2n - 1 chính là số lời gọi của ghi nhớ.

Thứ ba, hãy để ý cột cuối. Cả bốn cách đều ra 832.040. Nếu chỉ nhìn cột đó thì bốn cách này giống nhau hoàn toàn. Mọi thứ khiến bạn phải chọn đều nằm ở bốn cột giữa.

Cây gọi, và những nhánh không bao giờ tới lượt

Mục 2 vẽ cây gọi đầy đủ. Ở n = 6 nó có 25 nút, 13 lá, 6 tầng. Với ghi nhớ bật lên, chỉ 11 nút được đi vào: 7 nút tính thật, 4 nút chỉ tra bảng rồi trả về, và 14 nút bị cắt hẳn.

Con số 14 mới là chỗ đáng nhìn. Những nút bị cắt không phải nút rẻ. Khi ghi nhớ tra bảng ở một nút, nó không cắt một lời gọi, nó cắt cả cây con treo dưới nút đó. Đấy là lý do 2.692.537 rút được về 59: mỗi lần tra bảng thành công là một lần khỏi phải đi cả một nhánh, và nhánh thì lớn theo hàm mũ.

Hai mốc trong sim đáng thử, vì chúng cho thấy chuyện này không xảy ra ngay từ đầu.

• Ở n = 3, cây có 5 nút, ghi nhớ đã có một lần tra bảng, nhưng chưa nút nào bị cắt. Lý do: nút được tra bảng là fib(1), mà fib(1) là lá, dưới nó chẳng có gì để cắt.
• n = 4 mới là mốc đầu tiên có nút bị cắt, và cắt đúng 2 nút.

Nếu bạn định nhớ một câu về ghi nhớ, hãy nhớ câu này: nó chỉ có tác dụng khi cái được nhớ lại có cây con phía dưới.

Mốc mà kết quả sai nhưng không ai báo

Mục 3 là chỗ tôi muốn bạn cẩn thận nhất trong cả bài, vì nó không nói về thuật toán, nó nói về một cái bẫy sẽ đi theo bạn suốt nghề.

Số nguyên an toàn lớn nhất mà JavaScript giữ được đúng là 2^53 - 1, tức 9.007.199.254.740.991. Sim so từng bước hai đường tính: một vòng lặp viết bằng số thường như mọi người vẫn viết, và một đường tính bằng số nguyên chính xác. Mốc không phải do tôi gõ vào bài: phần tính đi từ n = 0 lên và tìm chỗ hai đường rời nhau.

Chỗ đó là n = 79.

• fib(78) là số Fibonacci cuối cùng còn đúng: 8.944.394.323.791.464, vẫn nhỏ hơn 2^53 - 1.
• Ở fib(79), giá trị đúng là 14.472.334.024.676.221 còn máy in ra 14.472.334.024.676.220.

Lệch đúng 1 đơn vị. Không ngoại lệ, không cảnh báo, không nhật ký, không một dấu hiệu nào. Chương trình chạy xong, in ra một con số mười bảy chữ số trông cực kỳ đáng tin, và nó sai. Đây là loại lỗi tệ nhất trong nghề: lỗi im lặng. Một lỗi làm chương trình chết thì bạn sửa trong mười phút; một lỗi làm chương trình trả về số sai thì có thể sống nhiều năm.

Một chi tiết nữa mà tôi đã đoán sai rồi phải đo lại, nên nói thẳng ra đây: sai số không lớn dần đều. Ở n = 85 nó lệch 25, rồi ở n = 86 chỉ còn lệch 9. Từ n = 91 nó còn đổi dấu, và đây là chỗ phải tính bằng công thức chứ không kéo núm tới được vì núm chặn ở 90, tức máy bắt đầu in ra số lớn hơn giá trị đúng. Cho nên đừng viết một phép kiểm kiểu "kết quả nhỏ hơn giá trị đúng thì báo lỗi": nó sẽ bỏ sót nửa số ca. Phép kiểm đúng là so khác nhau, không phải so nhỏ hơn.

Và đừng nhớ con số 79 như một tính chất của Fibonacci. Nó là tính chất của kiểu dữ liệu. Cùng đoạn mã ấy viết bằng long long của C++ còn đúng tới fib(92), vì fib(92) vừa khít 2^63 - 1 còn fib(93) thì vượt. Còn Python thì số nguyên không tràn, nên nó đúng mãi cho tới khi hết bộ nhớ. Đổi kiểu là đổi mốc.

Đổi tiền: O(n·m) là một con số bạn đếm được

Fibonacci dễ làm người ta hiểu sai một chuyện: rằng quy hoạch động là mẹo để chữa một hàm đệ quy viết ngây thơ. Không phải. Mục 4 đưa một bài mà bảng là cách làm chính, không phải bản vá.

Bài toán: có bao nhiêu cách đổi một số tiền bằng những mệnh giá cho trước. Ô ở hàng i cột a là số cách đổi đúng a đồng khi chỉ được dùng i mệnh giá đầu tiên. Công thức truy hồi rất đời thường: mỗi ô bằng ô ngay trên (không dùng mệnh giá thứ i thêm lần nào nữa) cộng ô cách nó đúng một mệnh giá về bên trái (dùng thêm một đồng nữa). Hai biên: cột 0 luôn bằng 1, vì đổi 0 đồng có đúng một cách là không lấy đồng nào; hàng 0 với số tiền dương luôn bằng 0.

Ở trạng thái mở bài, mệnh giá 1, 2, 5, 10 và số tiền 20:

• bảng có 5 hàng × 21 cột = 105 ô, và phần tính điền đúng 105 ô;
• đáp số là 40 cách;
• đệ quy thuần cho đúng cùng đáp số ấy nhưng phải gọi 586 lần, tức 5,58 lần số ô của bảng.

Ở đây O(n·m) không còn là một ký hiệu. Nó là con số 105. Bạn kéo núm bước điền và đếm từng ô một nếu muốn.

Bảng quét ở cuối mục 4 mới là chỗ hai đường tách hẳn nhau. Cột ô bảng tăng theo đường thẳng, đúng 5 ô mỗi đồng thêm vào, vì bảng có 5 hàng. Cột lời gọi thì không:

số tiền	ô bảng phải điền	lời gọi của đệ quy thuần	đắt hơn bảng
20	105	586	5,58 lần
100	505	119.206	236,05 lần

Ô bảng nhân 4,81 lần thì lời gọi nhân hơn 200 lần. Và ở số tiền 100 đáp số là 2.156 cách, một con số mà không ai muốn chờ đệ quy thuần trả về.

Một chuyện nữa, nhỏ mà nhiều người mất điểm vì nó: cách điền bảng này đếm tổ hợp, không đếm thứ tự. Đổi 3 đồng bằng mệnh giá 1 và 2 cho 2 cách, chứ không phải 3, vì 1 + 2 và 2 + 1 là cùng một cách. Cái quyết định điều đó là chỉ số hàng chỉ đi lên chứ không lùi. Đảo hai vòng lặp cho nhau thì bạn đếm thành 3 và không có gì báo lỗi cả. Lại một lỗi im lặng nữa, và lần này là lỗi của cách viết chứ không phải của kiểu dữ liệu.

Hai điều kiện, và đừng tin bài nào chưa kiểm

Quy hoạch động không dùng được ở mọi nơi. Nó cần đúng hai điều kiện, và mục 5 xử lý cả hai bằng cách đo chứ không bằng cách khẳng định.

Điều kiện thứ nhất: bài con phải gối nhau

Đo nó rất gọn: lấy số lời gọi chia cho số bài con khác nhau. Bằng 1 nghĩa là mỗi bài con chỉ được giải một lần, và khi ấy một bảng ghi nhớ chẳng có gì để nhớ.

• fib(30) đệ quy thuần: 2.692.537 lời gọi trên 31 bài con khác nhau, tức mỗi bài con bị giải lại 86.856,03 lần.
• Sắp xếp trộn trên 30 phần tử: 59 lời gọi trên 59 bài con khác nhau, tỉ lệ đúng 1,00.

Sắp xếp trộn cũng đệ quy, cũng chia bài lớn thành bài con, cũng được gọi là chia để trị. Nhưng hai nửa của nó không dùng chung một phần tử nào, nên mỗi đoạn chỉ bị sắp đúng một lần. Ghi nhớ nó chỉ tốn bộ nhớ mà không cắt được lấy một lời gọi. Đây chính là chỗ phân biệt chia để trị với quy hoạch động: cùng là đệ quy trên bài con, khác nhau ở chỗ bài con có gặp lại nhau hay không.

Và cái gối nhau ấy không có ngay từ n nhỏ. Ở n = 2, fib có 3 lời gọi trên 3 bài con, tỉ lệ đúng 1: chưa gối nhau. n = 3 mới là mốc đầu tiên, 5 lời gọi trên 4 bài con, tỉ lệ 1,25. Tôi đã đoán mốc này là n = 2, đo lại thì sai, nên nó nằm ở đây đúng như đo được.

Điều kiện thứ hai: cấu trúc con tối ưu

Lời giải tối ưu của bài lớn phải lắp được từ lời giải tối ưu của bài con. Nghe hiển nhiên tới mức không ai kiểm, nên sim đưa một đồ thị bốn đỉnh, năm cung mà nó sai hẳn.

Bài toán: tìm đường đi dài nhất từ s tới t, không được đi qua đỉnh nào hai lần.

• Đường dài nhất từ s tới u là s → t → u, trọng số 101.
• Công thức truy hồi tự nhiên nói: đường dài nhất tới t bằng đường dài nhất tới một đỉnh liền trước, cộng cung cuối. Tức 101 + 1 = 102.
• Nhưng phần tính đã liệt kê hết đường đi từ s tới t, và chỉ có hai đường: s → x → u → t nặng 3, và s → t nặng 1. Đường nặng nhất được 3.

Không có đường nào nặng 102, vì lối mà công thức mô tả là s → t → u → t, đi qua t hai lần. Đó không phải đường đi, đó là một lối đi lặp đỉnh.

Chỗ hỏng nằm ở đây: lời giải tối ưu của bài con đã tiêu mất chính cái đỉnh mà bài lớn còn cần. Muốn tới u cho thật xa thì phải đi qua t trước, mà đi qua t rồi thì không quay lại t được nữa. Bài con không độc lập với phần còn lại của lời giải, nên nó không lắp vào được.

Điều đáng nhớ không phải là "quy hoạch động hỏng với đường đi dài nhất". Điều đáng nhớ là: với đường đi ngắn nhất, đúng công thức ấy lại đúng, và đó là nền của Dijkstra với Floyd. Cùng một đồ thị, đổi chữ "ngắn nhất" thành "dài nhất" là công thức sụp. Cho nên cấu trúc con tối ưu là tính chất của bài toán, không phải đặc tính của kỹ thuật, và phải kiểm từng bài. Cổng kiểm số có phần đối chứng cho chính phép kiểm này, dù sim không bày ra thành núm bấm: bỏ đúng một cung để đồ thị không còn chu trình thì công thức cho 2 + 1 = 3, khít với đáp số thật, và cờ "hỏng" tắt. Tức phép kiểm biết phân biệt hai đồ thị chứ không phải lúc nào cũng kêu hỏng.

Đếm lời gọi không phải đo thời gian

Chỗ này phải nói rõ, vì đây là hiểu nhầm dễ mắc nhất sau một bài như bài này. Cùng tinh thần với bài đếm chi phí: sim đếm việc, không đo giây.

• Một lời gọi hàm đắt hơn một vòng lặp thật sự. Nó phải đẩy tham số, lưu địa chỉ trở về, cấp khung mới, rồi tháo tất cả ra lúc trả về. Nên khoảng cách giữa 2.692.537 lời gọi và 31 bước lặp ngoài đời còn xa hơn con số ở đây, chứ không gần hơn.
• Cột tổng ô nhớ cộng ô bảng với khung ngăn xếp như thể chúng bằng giá. Đó là quy ước của bài này, và là quy ước rộng tay với đệ quy: một khung ngăn xếp chứa cả tham số, biến cục bộ và địa chỉ trở về, nên nó đắt hơn một ô số nguyên.
• Ngăn xếp còn có trần. Ghi nhớ ở n = 90 xếp 90 khung, chưa sao. Nhưng cùng cách viết ấy trên một bài có độ sâu vài trăm nghìn thì nó không chậm, nó chết, với đúng một dòng thông báo là tràn ngăn xếp. Lập bảng từ dưới lên không có rủi ro đó, và đấy là lý do thật sự để nhiều người chọn nó chứ không phải vì nó nhanh hơn vài phần trăm.
• Ở n lớn hơn 30 thì hàng đệ quy thuần không đến từ một lượt chạy thật, vì chạy thật sẽ treo trang. Nó đến từ công thức 2·fib(n+1) - 1, và cổng kiểm đã đối chiếu công thức ấy với lượt chạy thật ở cả 31 giá trị n từ 0 tới 30. Hàng đó cũng không in ra kết quả, vì không có lượt chạy nào để lấy.

Vậy đếm để làm gì, nếu nó không cho biết thời gian? Để bạn có một con số kiểm chứng được thay cho một cảm giác. Không cảm giác nào cho bạn biết mốc gối nhau nằm ở n = 3 chứ không phải n = 2, rằng ghi nhớ tốn thêm đúng 59 ô, hay rằng fib(79) sai một đơn vị mà không ai báo.

Điều rút ra

Quy hoạch động là một phép đổi, không phải một bữa trưa miễn phí: ở n = 30 nó cắt lời gọi từ 2.692.537 xuống 59, tức 45.636,22 lần, nhưng số phép cộng thì y nguyên 29 và bộ nhớ đội thêm 59 ô so với vòng lặp hai ô. Nên luôn đọc ba con số cùng lúc, đừng đọc một. Ghi nhớ chỉ ăn tiền khi cái được nhớ lại có cây con phía dưới, và ở n = 3 thì nó chưa cắt được nút nào. Trước khi áp bảng vào một bài mới, hãy kiểm hai điều kiện bằng cách đo: chia số lời gọi cho số bài con khác nhau, và thử tìm một phản ví dụ cho việc lắp lời giải tối ưu, vì đường đi dài nhất chỉ cần bốn đỉnh là làm công thức nói 102 trong khi đáp số thật là 3. Cuối cùng, một đáp số đúng chưa chắc là một đáp số đúng: từ fib(79) trở đi máy in ra số sai mà không cảnh báo gì, và mốc ấy là mốc của kiểu dữ liệu chứ không phải của bài toán.

Đọc thêm để nối bài này vào phần còn lại của môn: bậc tăng trưởng giải thích vì sao O(2^n) với O(n) là hai thế giới khác nhau và vì sao ký hiệu ấy không nói cho bạn mốc cụ thể; đệ quy trong C là chỗ bạn viết ra chính hàm fib đang bị mổ ở đây; còn ngăn xếp và hàng đợi cho biết cái "30 khung ngăn xếp" trong bảng thật ra là cấu trúc gì và vì sao nó có trần.

Câu hỏi tự kiểm0/3 đúngchưa trả lời

1. 1Ở n = 30, ghi nhớ gọi 59 lần còn lập bảng cuộn không gọi lần nào và chỉ dùng 2 ô nhớ. Kết luận nào đúng nhất?
2. 2Sim cho thấy fib(78) còn đúng nhưng fib(79) thì máy in ra 14.472.334.024.676.220 trong khi giá trị đúng là 14.472.334.024.676.221. Cách phản ứng nào đúng?
3. 3Trên đồ thị bốn đỉnh của mục 5, đường đi dài nhất không lặp đỉnh từ s tới u nặng 101, còn từ s tới t chỉ nặng 3. Vì sao công thức "lấy đường dài nhất tới đỉnh liền trước rồi cộng cung cuối" lại cho 102?