Tháp Hà Nội: quy hoạch động là gì và dùng vào đâu?
Tháp Hà Nội 64 đĩa cần 585 tỷ năm; thêm một cọc chỉ còn 5 giờ. Đó là quy hoạch động: nhớ lại thay vì tính lại, thứ chạy trong router, điện thoại, ADN.

Mục lục
Có một trò chơi mang tên thủ đô của chúng ta mà gần như sinh viên công nghệ thông tin nào trên thế giới cũng gặp ít nhất một lần: tháp Hà Nội. Ba cái cọc, một chồng đĩa to dưới nhỏ trên, và một nhiệm vụ nghe rất đơn giản: chuyển cả chồng sang cọc khác.
Với 64 đĩa, nếu mỗi giây bạn chuyển một đĩa và không bao giờ nhầm, bạn cần khoảng 585 tỷ năm, gấp hơn 40 lần tuổi vũ trụ. Nhưng chỉ cần cho thêm một cái cọc thứ tư, con số ấy rơi xuống còn khoảng 5 giờ. Để tìm ra cách chơi 5 giờ ấy, ta cần một trong những ý tưởng hữu ích nhất của khoa học máy tính: quy hoạch động (dynamic programming).
Quy hoạch động nói gọn trong một câu: chia bài toán lớn thành các bài toán con, giải mỗi bài toán con đúng một lần, ghi kết quả vào bảng, rồi dùng lại. Cũng ý tưởng đó đang chạy khi điện thoại của bạn giải mã sóng di động, khi bộ gõ đề xuất sửa lỗi chính tả, khi các nhà sinh học so hai đoạn ADN, và khi router trên Internet chọn đường cho gói tin.
Nửa đầu bài không cần biết lập trình. Nửa sau có công thức và một đoạn code ngắn để bạn tự kiểm chứng mọi con số trong bài.
Tháp Hà Nội là gì?
Luật chơi chỉ có ba điều:
- Có ba cọc. Ban đầu mọi đĩa nằm ở cọc trái, đĩa to nhất ở dưới cùng, nhỏ dần lên trên.
- Mỗi lượt chỉ được nhấc một đĩa trên cùng của một cọc và đặt sang cọc khác.
- Không bao giờ được đặt đĩa to lên trên đĩa nhỏ.
Mục tiêu là chuyển cả chồng sang cọc phải.
Trò chơi được bán lần đầu ở Paris năm 1883, dưới tên La Tour d’Hanoï. Tác giả ký tên “Giáo sư N. Claus de Siam”, nhưng đó là tên giả: đảo chữ cái của “Lucas d’Amiens”. Người thật là Édouard Lucas, một nhà toán học Pháp nổi tiếng với dãy số Lucas và với việc chứng minh là số nguyên tố, con số nguyên tố lớn nhất từng được biết suốt 75 năm sau đó[1][2].
Lucas không giải thích vì sao lại là Hà Nội. Đầu thập niên 1880, Pháp đang đánh chiếm Bắc Kỳ (quân Pháp chiếm thành Hà Nội năm 1882), nên nhiều người cho rằng ông chọn một cái tên phương Đông đang xuất hiện dày đặc trên báo chí Pháp lúc đó để món đồ chơi thêm phần bí ẩn.
Đi kèm trò chơi là một truyền thuyết (nhiều khả năng do chính Lucas thêu dệt để quảng cáo, không phải chuyện cổ thật): trong một ngôi đền ở Ấn Độ, các thầy tu ngày đêm chuyển 64 chiếc đĩa vàng theo đúng luật trên. Khi họ chuyển xong, thế giới sẽ kết thúc. Lát nữa ta sẽ thấy vì sao không cần lo lắng.
Giải tháp Hà Nội: một ý duy nhất
Thử với 3 đĩa, đặt tên từ nhỏ đến to là 1, 2, 3. Bạn có thể mò ra lời giải 7 bước. Nhưng cách nghĩ quan trọng hơn lời giải.
Hãy nhìn vào đĩa to nhất. Để nhấc được nó, mọi đĩa khác phải rời khỏi cọc trái. Để đặt được nó xuống cọc phải, cọc phải phải trống. Vậy tại khoảnh khắc đĩa to nhất di chuyển, tất cả các đĩa còn lại phải đang nằm gọn ở cọc giữa. Không có cách nào khác.
Từ đó lời giải tự hiện ra, theo ba chặng:
- Chuyển đĩa phía trên từ cọc trái sang cọc giữa (dùng cọc phải làm chỗ trung chuyển).
- Chuyển đĩa to nhất sang cọc phải. Một bước.
- Chuyển đĩa từ cọc giữa sang cọc phải, chồng lên đĩa to nhất.
Chặng 1 và chặng 3 chính là cùng một trò chơi, chỉ với ít hơn một đĩa. Và trò chơi đĩa lại được giải bằng đúng ba chặng ấy với đĩa, cứ thế cho tới khi chỉ còn một đĩa, chuyển một bước là xong. Cách giải một bài toán bằng chính phiên bản nhỏ hơn của nó gọi là đệ quy.
Gọi là số bước ít nhất để chuyển đĩa. Ba chặng trên cho ta:
Tính lần lượt: , , , , … Mỗi lần thêm một đĩa, số bước gấp đôi rồi cộng một. Quy luật là .
Vì lập luận “đĩa to nhất bắt buộc phải đi một mình giữa hai lần dọn” không có lối thoát, không chỉ là một cách chơi mà là số bước ít nhất có thể, và lời giải tối ưu là duy nhất.
Giờ quay lại ngôi đền. Với 64 đĩa:
Mỗi giây một bước, các thầy tu cần khoảng năm, tức 585 tỷ năm. Vũ trụ mới 13,8 tỷ tuổi. Thế giới khá an toàn.
Thêm một cọc, mọi thứ thay đổi
Năm 1907, nhà ra câu đố người Anh Henry Dudeney đưa vào cuốn The Canterbury Puzzles một biến thể: bác chủ quán phải chuyển 8 miếng phô mai to nhỏ khác nhau qua 4 cái ghế đẩu, cũng theo luật không đặt miếng to lên miếng nhỏ[3]. Bài toán này giờ được gọi là Reve’s puzzle hay tháp Hà Nội 4 cọc.
Có thêm một cọc trống, ta không còn bị ép phải dồn mọi đĩa vào một chỗ. Chiến lược tự nhiên nhất, được J. S. Frame và B. M. Stewart công bố năm 1941, là[4]:
- Lấy đĩa nhỏ nhất ở trên cùng, chuyển chúng sang một cọc phụ để “đỗ” ở đó, được dùng cả 4 cọc.
- Chuyển đĩa to còn lại sang cọc đích. Lúc này một cọc đang bị chiếm bởi đống đĩa nhỏ (đĩa to không được đặt lên chúng), nên chỉ còn 3 cọc dùng được: mất bước.
- Chuyển đĩa nhỏ từ chỗ đỗ về cọc đích, lại dùng cả 4 cọc.
Gọi là số bước với 4 cọc. Nếu chọn trước , tổng số bước là . Nhưng chọn bằng bao nhiêu? Đỗ ít đĩa quá thì phần 3 cọc ở giữa đắt khủng khiếp; đỗ nhiều quá thì chính việc đỗ lại tốn kém. Không có lý do gì để đoán trước; cách chắc chắn là thử mọi rồi chọn cái rẻ nhất:
Công thức này có một điểm đặc biệt: để tính , bạn cần biết cho mọi nhỏ hơn. Và chính đây là chỗ quy hoạch động bước vào.
Quy hoạch động là gì?
Thử tính theo cách “thẳng thắn”: viết một hàm, trong hàm thử từng , và với mỗi thì gọi lại chính hàm đó để tính .
Vấn đề là các bài toán con chồng lên nhau. Tính cần . Tính lại cần . Tính lại cần … Câu hỏi “ bằng bao nhiêu?” bị hỏi đi hỏi lại hàng trăm lần, và lần nào máy cũng cặm cụi tính lại từ đầu như chưa từng gặp. Số lần gọi hàm đúng bằng : với 22 đĩa là hơn 2 triệu lần; với 64 đĩa là lần. Cách giải “thẳng thắn” này chậm gần ngang ngôi đền.
Cách của quy hoạch động: điền một cái bảng từ nhỏ đến lớn.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 3 cọc: | 1 | 3 | 7 | 15 | 31 | 63 | 127 | 255 | 511 | 1023 |
| 4 cọc: | 1 | 3 | 5 | 9 | 13 | 17 | 25 | 33 | 41 | 49 |
| tốt nhất | 1 | 1 | 1 | 2 | 3 | 3 | 4 | 5 | 6 |
Muốn điền ô , bạn chỉ cần nhìn 9 ô đã có bên trái, thử 9 giá trị , lấy cái nhỏ nhất. Mỗi ô tính đúng một lần. Tính tới 64 đĩa, tổng cộng chỉ có phép thử, máy tính làm xong trong chưa tới một phần nghìn giây.
Để ý cột : 33 bước. Đó chính là đáp án bài 8 miếng phô mai của Dudeney năm 1907.
Còn kết quả cho 64 đĩa: bước. Mỗi giây một bước, khoảng 5 giờ 7 phút. Một cái cọc thêm vào đã biến 585 tỷ năm thành một buổi chiều.

Hình 1 cho thấy hai lần “bùng nổ hàm mũ” bị dập tắt. Bên trái là trong trò chơi: thêm một cọc, số bước tăng chậm hơn hàm mũ rất nhiều. Bên phải là trong cách ta tính: nhớ lại kết quả cũ, khối lượng tính từ hàm mũ rơi xuống chỉ còn tăng theo bình phương.
Hai điều kiện để dùng quy hoạch động
Không phải bài toán nào cũng “điền bảng” được. Cần đủ hai điều kiện:
- Cấu trúc con tối ưu: lời giải tốt nhất của bài lớn được ghép từ lời giải tốt nhất của các bài nhỏ. Cách đỗ đĩa nhỏ tốt nhất bên trong lời giải tốt nhất của đĩa chính là lời giải tốt nhất của bài đĩa.
- Bài toán con chồng lấn: cùng một bài nhỏ bị hỏi lại nhiều lần. Đây là lý do việc ghi nhớ có lợi. Nếu các bài con không bao giờ lặp lại (như khi chia đôi một danh sách để sắp xếp), ghi nhớ chẳng giúp được gì, và ta chỉ cần đệ quy bình thường.
Tháp Hà Nội 3 cọc chỉ có một lựa chọn duy nhất ở mỗi bước, nên đệ quy là đủ. Tháp 4 cọc buộc ta chọn giữa nhiều , và mỗi lựa chọn lại dẫn về những bài con đã gặp. Đó là dấu hiệu nhận biết một bài toán quy hoạch động: phải chọn, và các lựa chọn dẫn về cùng một nhóm bài nhỏ.
Vì sao lại gọi là “quy hoạch động”?
Cái tên nghe chẳng liên quan gì tới bảng hay ghi nhớ, và đó là cố ý. Người đặt tên là nhà toán học Mỹ Richard Bellman, khi làm việc cho tổ chức nghiên cứu RAND đầu thập niên 1950. Theo lời ông kể trong hồi ký, RAND nhận tiền từ Không quân Mỹ, còn Bộ trưởng Quốc phòng khi đó là Charles Wilson thì ghét cay ghét đắng chữ “nghiên cứu”, nhất là “nghiên cứu toán học”. Bellman cần một cái tên mà không ông nghị nào phản đối được[6].
Ông chọn programming, theo nghĩa thời đó là “lập kế hoạch, lên lịch”, không phải viết code. Thêm dynamic vì bài toán của ông có yếu tố thời gian, các quyết định nối tiếp nhau, và vì theo ông, “không thể dùng chữ dynamic theo nghĩa xấu được”. Tiếng Việt dịch sát thành quy hoạch động.
Đằng sau cái tên có phần “chính trị” ấy là một nguyên lý rất gọn mà Bellman gọi là nguyên lý tối ưu: một kế hoạch tốt nhất có tính chất là, dù bạn đang ở bước nào, phần còn lại của kế hoạch cũng phải là tốt nhất tính từ chỗ bạn đang đứng. Nói theo kiểu chỉ đường: nếu con đường nhanh nhất từ Hà Nội vào Sài Gòn đi qua Đà Nẵng, thì đoạn từ Đà Nẵng vào Sài Gòn của nó cũng phải là đường nhanh nhất giữa hai thành phố đó. Nếu không, bạn chỉ việc thay đoạn ấy bằng đường nhanh hơn.
Quy hoạch động đang chạy ở đâu quanh bạn?
Internet chọn đường cho gói tin
Năm 1958, Bellman áp đúng nguyên lý trên vào bài toán tìm đường ngắn nhất[7]. Thay vì thử mọi con đường, mỗi điểm chỉ cần biết: “từ đây tới đích mất bao lâu?” và tính nó từ câu trả lời của các điểm hàng xóm. Đường ngắn nhất từ tôi bằng nhỏ nhất của (khoảng cách tới hàng xóm + đường ngắn nhất từ hàng xóm). Đó là một bảng được điền dần.
Thuật toán này, nay gọi là Bellman–Ford, là nền của giao thức RIP, một trong những cách đầu tiên các router trên Internet trao đổi bảng đường đi với nhau[8]. Mỗi router chỉ nói chuyện với hàng xóm, vậy mà cả mạng dần biết đường đi ngắn nhất tới mọi nơi.
Bộ gõ sửa lỗi chính tả, lệnh so sánh văn bản
Bạn gõ “quy hoahc” và máy gợi ý “quy hoạch”. Để làm vậy, máy cần đo hai từ khác nhau bao nhiêu: số lần thêm, xóa hoặc sửa một chữ cái ít nhất để biến từ này thành từ kia. Đại lượng này gọi là khoảng cách chỉnh sửa (hay khoảng cách Levenshtein).
Thử mọi cách sửa là bất khả thi. Quy hoạch động làm thế này: dựng một bảng, ô ở hàng , cột ghi khoảng cách giữa chữ đầu của từ thứ nhất và chữ đầu của từ thứ hai. Mỗi ô chỉ cần nhìn ba ô kề nó (bên trái, bên trên, chéo trên trái) và chọn cách rẻ nhất trong ba thao tác. Ô góc dưới phải là đáp án[9]. Công cụ so sánh hai phiên bản văn bản hay mã nguồn (như lệnh diff) giải một bài toán họ hàng: tìm phần chung dài nhất của hai văn bản, để tô màu những dòng đã thêm và đã xóa.
So sánh hai đoạn ADN
Thay chữ cái bằng các bazơ A, C, G, T và bạn có công cụ cơ bản của sinh học phân tử. Năm 1970, Saul Needleman và Christian Wunsch công bố thuật toán dóng hàng hai chuỗi protein bằng đúng kiểu bảng ấy[10]. Mỗi lần các nhà khoa học hỏi “gen này của người giống gen nào của chuột?”, hay so một mẫu virus mới với những chủng đã biết, ý tưởng của họ (cùng những biến thể và phiên bản tăng tốc) đang làm việc.
Điện thoại giải mã tín hiệu
Sóng vô tuyến tới điện thoại của bạn luôn bị nhiễu. Để sửa lỗi, bên gửi mã hóa dữ liệu sao cho mỗi bit phụ thuộc vào vài bit trước nó. Bên nhận phải đoán: chuỗi bit gốc nào có khả năng nhất đã sinh ra tín hiệu nhiễu này? Số chuỗi có thể là khổng lồ.
Năm 1967, Andrew Viterbi đưa ra một thuật toán quy hoạch động cho việc này[11]: đi dần theo thời gian, tại mỗi thời điểm chỉ giữ lại con đường tốt nhất dẫn tới mỗi trạng thái, vứt bỏ mọi con đường kém hơn. Thuật toán Viterbi có mặt trong mạng di động, Wi‑Fi, liên lạc vệ tinh, và cả những hệ nhận dạng giọng nói đời đầu. Viterbi sau đó đồng sáng lập Qualcomm.
Thu nhỏ ảnh mà không bóp méo
Bạn muốn ảnh phong cảnh hẹp lại mà không làm người trong ảnh gầy đi? Năm 2007, Shai Avidan và Ariel Shamir đề xuất kỹ thuật seam carving[12]: tìm một “đường may” chạy từ trên xuống dưới ảnh đi qua những điểm ảnh ít quan trọng nhất (bầu trời, mặt nước) rồi cắt bỏ nó. Đường may tốt nhất được tìm bằng một bảng: chi phí tốt nhất tới mỗi điểm ảnh bằng chi phí của nó cộng với ô rẻ nhất trong ba ô ngay phía trên. Ý tưởng này có trong tính năng co giãn thông minh của các phần mềm sửa ảnh.
Định giá quyền chọn
Trong tài chính, mô hình cây nhị thức Cox–Ross–Rubinstein (1979) định giá một quyền chọn kiểu Mỹ, loại được thực hiện bất cứ lúc nào trước hạn, bằng cách đi ngược từ ngày đáo hạn về hôm nay[13]. Tại mỗi nút của cây, người nắm quyền chọn so sánh “thực hiện ngay” với “giữ thêm” (giá trị này suy ra từ hai nút phía sau, vốn đã tính xong), rồi chọn cái lớn hơn. Đó là nguyên lý tối ưu của Bellman, áp vào tiền bạc.
Khi quy hoạch động không cứu được
Quy hoạch động biến hàm mũ thành đa thức khi số bài con khác nhau là nhỏ. Tháp 4 cọc chỉ có 64 bài con: tới . Nhưng có những bài toán mà số “trạng thái” phải nhớ tự nó đã bùng nổ.
Bài toán người bán hàng (đi qua thành phố, mỗi nơi một lần, quãng đường ngắn nhất) có một lời giải quy hoạch động, nhưng bảng của nó có khoảng ô. Với 30 thành phố đã là hơn 30 tỷ ô, và gần một nghìn tỷ phép tính. Bellman gọi hiện tượng này là “lời nguyền số chiều” (curse of dimensionality): mỗi khi trạng thái có thêm một chiều, bảng phình to gấp nhiều lần. Đó là lý do nhiều hệ thống thực tế (kể cả bản đồ chỉ đường) kết hợp quy hoạch động với những mẹo ước lượng, hoặc chuyển sang học máy, nơi mạng nơ‑ron học cách “ước đoán” giá trị của một ô thay vì tính chính xác từng ô.
Và cũng cần phân biệt: thêm cọc giúp trò chơi ngắn đi; quy hoạch động giúp việc tìm cách chơi nhanh đi. Hai việc khác nhau. Quy hoạch động không làm 3 cọc bớt được bước nào, vì đã là tối ưu. Nó chỉ giúp ta tìm ra chiến lược 4 cọc tốt nhất mà không phải thử lần.
Tự tay tính tháp Hà Nội 4 cọc
Đoạn code dưới đây tạo ra đúng Hình 1 và in ra bảng ở mục trên. Nó viết hai cách tính : cách đệ quy ngây thơ (đếm số lần gọi hàm) và cách quy hoạch động (điền bảng), kiểm tra hai cách cho cùng kết quả tới 22 đĩa, rồi dùng bảng tính tới 64 đĩa. Không có yếu tố ngẫu nhiên, chạy bao nhiêu lần cũng ra cùng con số. Chỉ cần matplotlib; phần đệ quy ngây thơ mất vài giây.
import matplotlib.pyplot as plt
plt.rcParams.update({"figure.facecolor": "#16181c", "axes.facecolor": "#16181c", "text.color": "#d4d7dc", "axes.edgecolor": "#2a2e35", "axes.labelcolor": "#878d97", "xtick.color": "#878d97", "ytick.color": "#878d97", "font.size": 12})VANG, XANH = "#e0b44c", "#5fa8d3"N = 64
# 1. Ba cọc: dọn n−1 đĩa sang cọc phụ, chuyển đĩa lớn nhất, dọn n−1 đĩa về lại.def ba_coc(n): return 2**n - 1
# 2. Bốn cọc (Frame–Stewart): để k đĩa trên cùng "đỗ" ở một cọc bằng cả 4 cọc,# chuyển n−k đĩa còn lại bằng 3 cọc, rồi đưa k đĩa về. Phải thử mọi k.dem = {"ngay_tho": 0}
def bon_coc_ngay_tho(n): """Đệ quy thẳng: gặp lại bài toán con nào cũng giải lại từ đầu.""" dem["ngay_tho"] += 1 if n <= 1: return n return min(2 * bon_coc_ngay_tho(k) + ba_coc(n - k) for k in range(1, n))
def bon_coc_quy_hoach_dong(n_max): """Quy hoạch động: điền bảng F[0..n_max] từ nhỏ đến lớn, mỗi ô chỉ tính một lần.""" F, k_tot, so_phep_thu = [0, 1], [0, 0], 0 for n in range(2, n_max + 1): ung_vien = {k: 2 * F[k] + ba_coc(n - k) for k in range(1, n)} so_phep_thu += len(ung_vien) k = min(ung_vien, key=ung_vien.get) F.append(ung_vien[k]) k_tot.append(k) return F, k_tot, so_phep_thu
F, k_tot, so_phep_thu = bon_coc_quy_hoach_dong(N)print(" n | 3 cọc | 4 cọc | k tốt nhất")for n in range(1, 11): print(f"{n:2d} | {ba_coc(n):5d} | {F[n]:5d} | {k_tot[n]}")print(f"n = 64: 3 cọc cần {ba_coc(N):,} bước, 4 cọc chỉ cần {F[N]:,} bước")nam = ba_coc(N) / (365.25 * 24 * 3600)print(f" mỗi giây một bước: {nam:.3e} năm so với {F[N] / 3600:.1f} giờ")
# 3. Đếm số lần gọi hàm của cách ngây thơ (n từ 2 tới 22, cho nhanh) và so với bảng.n_dem = list(range(2, 23))goi_ngay_tho = []for n in n_dem: dem["ngay_tho"] = 0 assert bon_coc_ngay_tho(n) == F[n] goi_ngay_tho.append(dem["ngay_tho"])phep_thu_bang = [bon_coc_quy_hoach_dong(n)[2] for n in n_dem]print(f"n = 22: ngây thơ gọi hàm {goi_ngay_tho[-1]:,} lần, bảng chỉ thử {phep_thu_bang[-1]} phép")print(f"n = 64: bảng thử {so_phep_thu} phép, ngây thơ sẽ cần 2^63 ≈ {2**63:.2e} lần gọi")
fig, (a1, a2) = plt.subplots(1, 2, figsize=(13, 5.2))ns = range(1, N + 1)a1.semilogy(ns, [ba_coc(n) for n in ns], color=VANG, lw=2.5, label="3 cọc: $2^n - 1$")a1.semilogy(ns, [F[n] for n in ns], color=XANH, lw=2.5, label="4 cọc: quy hoạch động")a1.annotate("64 đĩa: 1,8 × 10¹⁹ bước\n≈ 585 tỷ năm", (N, ba_coc(N)), (38, 1e9), color=VANG, arrowprops=dict(arrowstyle="->", color=VANG))a1.annotate("64 đĩa: 18.433 bước\n≈ 5 giờ", (N, F[N]), (38, 2e1), color=XANH, arrowprops=dict(arrowstyle="->", color=XANH))a1.set(xlabel="số đĩa n", ylabel="số bước ít nhất (thang log)", title="Thêm một cọc")a1.legend(frameon=False, loc="upper left")
a2.semilogy(n_dem, goi_ngay_tho, "o-", color=VANG, lw=2, label="đệ quy ngây thơ: $2^{n-1}$ lần gọi")a2.semilogy(n_dem, phep_thu_bang, "o-", color=XANH, lw=2, label="điền bảng: $n(n-1)/2$ phép thử")a2.set(xlabel="số đĩa n", ylabel="khối lượng tính (thang log)", title="Nhớ lại thay vì tính lại")a2.set_xticks(range(2, 23, 4))a2.legend(frameon=False, loc="upper left")for a in (a1, a2): a.grid(color="#2a2e35", lw=0.6)fig.tight_layout()fig.savefig("thap-ha-noi-quy-hoach-dong.png", dpi=150)Kết quả in ra:
n | 3 cọc | 4 cọc | k tốt nhất 1 | 1 | 1 | 0 2 | 3 | 3 | 1 ...10 | 1023 | 49 | 6n = 64: 3 cọc cần 18,446,744,073,709,551,615 bước, 4 cọc chỉ cần 18,433 bước mỗi giây một bước: 5.845e+11 năm so với 5.1 giờn = 22: ngây thơ gọi hàm 2,097,152 lần, bảng chỉ thử 231 phépn = 64: bảng thử 2016 phép, ngây thơ sẽ cần 2^63 ≈ 9.22e+18 lần gọiMuốn thấy sức mạnh của việc ghi nhớ bằng mắt, hãy thử đổi range(2, 23) thành range(2, 30): phần đệ quy ngây thơ sẽ chạy hàng phút, trong khi phần bảng vẫn xong tức thì. Một cách khác để thêm “trí nhớ” mà không phải tự dựng bảng là đặt @functools.cache lên trên hàm bon_coc_ngay_tho; số lần hàm thực sự phải tính lập tức rơi về đúng số ô của bảng.
Đừng giải lại điều đã biết
Tháp Hà Nội thường được dạy như bài học về đệ quy, và đúng là thế. Nhưng câu chuyện thú vị hơn nằm ở cái cọc thứ tư. Khi bài toán buộc ta phải chọn, và mỗi lựa chọn dẫn về những câu hỏi nhỏ đã từng gặp, thì cách làm khôn ngoan là trả lời mỗi câu hỏi nhỏ đúng một lần và ghi lại.
Nghe hiển nhiên đến mức hơi buồn cười, nhưng chính sự hiển nhiên ấy đã giúp router chọn đường, giúp điện thoại nghe rõ trong nhiễu, giúp các nhà sinh học đọc ADN. Lần tới gặp một bài toán có vẻ phải thử hàng tỷ khả năng, hãy hỏi thử: có bao nhiêu câu hỏi nhỏ thật sự khác nhau trong đó? Nếu câu trả lời là “không nhiều”, bạn vừa tìm thấy một bài toán quy hoạch động.
Nếu thích kiểu bài “một ý tưởng thuật toán đứng sau thứ bạn dùng hằng ngày”, bạn có thể đọc tiếp về tìm kiếm nhị phân trong database hay Bloom filter.
Vẽ minh họa hình học miễn phí cho học sinh và giáo viên: EyeViz.
Tài liệu tham khảo
- [1]Andreas M. Hinz, Sandi Klavžar và Ciril Petr. The Tower of Hanoi – Myths and Maths (2nd ed.). Birkhäuser, 2018.
- [2]Tower of Hanoi. Wikipedia.
- [3]Henry Ernest Dudeney. The Canterbury Puzzles (The Reve's Puzzle), 1907.
- [4]J. S. Frame; B. M. Stewart. Solution to Advanced Problem 3918. The American Mathematical Monthly 48(3), 1941.
- [5]Thierry Bousch. La quatrième tour de Hanoï. Bulletin of the Belgian Mathematical Society – Simon Stevin 21(5), 2014.
- [6]Stuart Dreyfus. Richard Bellman on the Birth of Dynamic Programming. Operations Research 50(1), 2002.
- [7]Richard Bellman. On a Routing Problem. Quarterly of Applied Mathematics 16(1), 1958.
- [8]G. Malkin. RFC 2453: RIP Version 2. IETF, 1998.
- [9]Robert A. Wagner và Michael J. Fischer. The String-to-String Correction Problem. Journal of the ACM 21(1), 1974.
- [10]Saul B. Needleman và Christian D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 48(3), 1970.
- [11]Andrew J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory 13(2), 1967.
- [12]Shai Avidan và Ariel Shamir. Seam Carving for Content-Aware Image Resizing. ACM SIGGRAPH, 2007.
- [13]John C. Cox, Stephen A. Ross và Mark Rubinstein. Option pricing: A simplified approach. Journal of Financial Economics 7(3), 1979.


