Quy hoạch động (Dynamic Programming)

1. Tổng quan

A. Định nghĩa

Quy hoạch động (Dynamic Programming, DP) là kỹ thuật thiết kế thuật toán tối ưu hóa, phân rã một bài toán lớn thành các bài toán con nhỏ chồng lấp lẫn nhau, tính lời giải của mỗi bài toán con đúng một lần rồi lưu (ghi nhớ) và tái sử dụng, nhờ đó hạ độ phức tạp tìm kiếm từ hàm mũ xuống thời gian đa thức.

Quy hoạch động được Richard Bellman định hình vào thập niên 1950 để giải các bài toán ra quyết định nhiều giai đoạn; trong tên gọi, "dynamic" chỉ các quyết định nhiều giai đoạn theo thời gian, còn "programming" nghĩa là tối ưu hóa toán học (quy hoạch). Ngày nay DP là một trong ba mô thức lớn của thiết kế thuật toán (chia để trị, tham lam, quy hoạch động) và đã trở thành công cụ cốt lõi để loại bỏ sự kém hiệu quả của việc "giải cùng một bài toán con lặp đi lặp lại".

B. Bối cảnh ra đời và sự cần thiết

Nhiều bài toán tối ưu hóa, khi định nghĩa bằng đệ quy đơn giản (vét cạn), sẽ tính trùng lặp cùng một bài toán con theo cấp số mũ. Ví dụ phổ biến nhất là dãy Fibonacci. Nếu gọi đệ quy fib(n) = fib(n-1) + fib(n-2) đúng như viết, fib(n-2) được tính hai lần, fib(n-3) ba lần, và tổng số lần gọi bùng nổ tới khoảng O(1.618ⁿ) tỷ lệ với tỷ lệ vàng. Chỉ cần n=50 thì số lần gọi đã lên tới hàng trăm triệu và không kết thúc trong thời gian thực dụng. Số "lời giải" của bài toán rõ ràng là đa thức, nhưng phương thức tìm kiếm lại là hàm mũ — chính mâu thuẫn này là điều DP hướng tới giải quyết.

Quy hoạch động loại bỏ sự trùng lặp này bằng nguyên lý đơn giản mà mạnh mẽ: "lưu lại đáp án đã tính một lần, và lấy ra dùng khi cần lại". Các bài toán con khác nhau của Fibonacci chỉ là n+1 giá trị fib(0)~fib(n), nên tính mỗi giá trị đúng một lần sẽ kết thúc toàn bộ trong O(n). Nói cách khác, bản chất của DP là đánh đổi thời gian lấy bộ nhớ (sự đánh đổi không gian-thời gian), hấp thụ sự lãng phí cấp mũ của việc tính trùng lặp vào không gian lưu trữ đa thức. Để sự đánh đổi này thành lập, bài toán phải thỏa mãn hai điều kiện.

Sự cần thiết của DP tái diễn ở mọi bài toán tối ưu hóa "tìm kiếm theo hàm mũ cho một số lượng lời giải đa thức". Những bài toán tưởng chừng không liên quan — tìm đường, phân bổ tài nguyên, căn chỉnh chuỗi, lập lịch — thực ra chia sẻ cấu trúc chung rằng "các quyết định nhỏ tích lũy lại thành quyết định tổng thể tối ưu", và vét cạn khiến các tổ hợp quyết định bùng nổ theo hàm mũ. DP gấp sự bùng nổ này vào một bản tóm tắt trung gian gọi là "trạng thái", để một giá trị đã lưu đại diện cho vô số đường đi tới cùng một trạng thái. Do đó, học DP không phải là ghi nhớ lời giải của từng bài toán riêng lẻ mà là rèn luyện con mắt nhận ra cấu trúc chung này và trừu tượng hóa nó thành trạng thái.

C. Hai điều kiện để DP thành lập

Không thể áp dụng DP cho bất kỳ bài toán nào. Khả năng áp dụng được phán định bằng hai điều kiện: Cấu trúc con tối ưu (Optimal Substructure) và Bài toán con chồng lấp (Overlapping Subproblems). Điều kiện thứ nhất là tính chất "lời giải tối ưu của bài toán lớn được cấu thành từ lời giải tối ưu của các bài toán nhỏ", còn thứ hai là tính chất "cùng một bài toán nhỏ xuất hiện lặp đi lặp lại". Hai điều kiện độc lập với nhau, nên nếu cả hai thỏa mãn thì DP phù hợp; nếu chỉ có cấu trúc con tối ưu mà không có chồng lấp thì chia để trị phù hợp; và nếu thêm nữa tối ưu cục bộ bảo đảm tối ưu toàn cục thì phương pháp tham lam phù hợp. Sự phán định này được bàn chi tiết ở mục so sánh phía dưới.

Hai điều kiện cùng nhau giải thích không chỉ "DP có áp dụng được không" mà cả "hiệu quả" của nó. Nếu cấu trúc con tối ưu bảo đảm 'tính đúng đắn' của công thức truy hồi (kết hợp các lời giải con có cho ra lời giải tổng thể đúng không?), thì bài toán con chồng lấp quyết định 'lợi ích' của DP (lưu và tái sử dụng tiết kiệm được bao nhiêu?). Nếu hầu như không có chồng lấp, chi phí lưu trữ chỉ tăng lên mà không có lợi ích, về thực chất không khác gì chia để trị; càng nhiều chồng lấp thì biên độ giảm từ hàm mũ xuống đa thức càng lớn. Do đó, thói quen kiểm tra tường minh từng điều kiện khi nhận một bài toán trở thành cửa ải đầu tiên lọc bỏ cả việc áp dụng sai lẫn việc áp dụng không cần thiết.

2. Nguyên lý và cấu trúc của quy hoạch động

Cấu trúc tổng thể của quy hoạch động có thể hiểu theo luồng "phân rã bài toán → định nghĩa trạng thái → công thức truy hồi → lưu và tái sử dụng → phục hồi lời giải". Sơ đồ cấu trúc dưới đây cho thấy rõ trong nháy mắt sự khác biệt giữa vét cạn (tính trùng lặp) và DP (lưu và tái sử dụng).

flowchart TB
  P["Bài toán gốc"] --> SUB["Phân rã thành bài toán con"]
  SUB --> CHK{"Bài toán con<br/>đã tính chưa?"}
  CHK -->|"Rồi (trùng lặp)"| MEM["Tra cứu từ kho lưu (O(1))"]
  CHK -->|"Chưa (lần đầu)"| CALC["Tính bằng công thức truy hồi"]
  CALC --> STORE["Ghi vào kho lưu (ghi nhớ)"]
  STORE --> COMB["Kết hợp thành lời giải bài toán trên"]
  MEM --> COMB
  COMB --> ANS["Lời giải tối ưu của bài toán gốc"]

A. Cấu trúc con tối ưu (Optimal Substructure)

Cấu trúc con tối ưu là tính chất lời giải tối ưu của toàn bài toán được cấu thành chỉ từ lời giải tối ưu của các bài toán con. Chẳng hạn nếu đường đi ngắn nhất từ Seoul đến Busan đi qua Seoul→Daejeon→Busan, thì đoạn Seoul→Daejeon nằm trong đường đi đó cũng phải là đường đi ngắn nhất từ Seoul đến Daejeon. Nếu có một đường Seoul→Daejeon ngắn hơn thì toàn đường đi cũng có thể ngắn hơn, mâu thuẫn với giả định "tối ưu". Nhờ tính chất này, có thể biểu diễn bài toán lớn theo đáp án của các bài toán nhỏ dưới dạng 'công thức truy hồi (recurrence relation)'.

Cấu trúc con tối ưu quan trọng vì không có nó thì dù lưu bao nhiêu đáp án bài toán nhỏ cũng không thể cấu thành bài toán lớn. Ví dụ, bài toán 'đường đi đơn dài nhất (longest simple path)' không thỏa cấu trúc con tối ưu. Nối hai đường đi con có thể làm trùng đỉnh và phá vỡ ràng buộc 'đường đi đơn', nên kết hợp các tối ưu con không bảo đảm tối ưu tổng thể. Như vậy, trước khi áp dụng DP phải kiểm tra trước rằng "kết hợp các lời giải con có tạo thành lời giải tổng thể không".

B. Bài toán con chồng lấp (Overlapping Subproblems)

Bài toán con chồng lấp là tính chất khi giải bài toán theo đệ quy, cùng một bài toán con được gọi lặp đi lặp lại nhiều lần. Việc fib(3) bị tính lại nhiều lần trong Fibonacci là ví dụ điển hình. Sự chồng lấp này càng nhiều thì lợi ích của DP càng lớn. Ngược lại, như sắp xếp trộn, nếu các bài toán con không chồng lấp mà mỗi lần xử lý đầu vào mới thì không có gì để lưu và tái sử dụng, nên chia để trị — chứ không phải DP — mới đúng.

Bài toán con chồng lấp được định lượng bằng 'tổng số bài toán con khác nhau'. Fibonacci có n+1, bài toán cái túi 0/1 có (số vật phẩm)×(sức chứa), và dãy con chung dài nhất (LCS) có (độ dài chuỗi1)×(độ dài chuỗi2) bài toán con khác nhau. Độ phức tạp thời gian của DP nhìn chung được tính bằng 'số bài toán con khác nhau × chi phí giải một bài toán con', nên nắm chính xác kích thước không gian trạng thái là điểm khởi đầu của phân tích hiệu năng.

Sự định lượng này trong thực tế trở thành căn cứ để phán định trước khi lập trình rằng "liệu DP có chạy nổi không". Ví dụ nếu trạng thái là (1.000 vật phẩm)×(1 triệu sức chứa) thì số trạng thái lên tới một tỷ, vượt cả giới hạn bộ nhớ lẫn thời gian, là tín hiệu cần cân nhắc thu gọn trạng thái hay thuật toán xấp xỉ trước khi áp dụng DP trực tiếp. Ngược lại nếu số trạng thái trong vòng vài triệu thì có thể yên tâm thiết kế DP. Như vậy, 'ước lượng kích thước không gian trạng thái' là một chốt kiểm tra thực tế nhằm kiểm chứng trước tính hợp lý của việc áp dụng DP.

C. Hai phương thức cài đặt — ghi nhớ và lập bảng

Theo phương thức cài đặt, DP chia thành ghi nhớ từ trên xuống (Top-Down memoization) và lập bảng từ dưới lên (Bottom-Up tabulation). Ghi nhớ vẫn giữ các lời gọi đệ quy nhưng lưu kết quả đã tính vào bộ đệm (mảng/bảng băm) và trả về ngay khi gặp lại cùng lời gọi. Mã của nó gần như trùng với công thức truy hồi gốc nên trực quan, và có ưu điểm chỉ tính các bài toán con thực sự cần; nhược điểm là giới hạn độ sâu ngăn xếp đệ quy và chi phí gọi hàm.

Lập bảng điền bảng (table) từ bài toán con nhỏ nhất đi lên, tiến tới bài toán lớn. Không có đệ quy nên không tràn ngăn xếp, dựa trên vòng lặp với hệ số hằng nhỏ nên nhìn chung nhanh hơn; tuy nhiên nó tính mọi bài toán con không sót, nên một phần có thể không cần thiết, và phải tự thiết kế thứ tự tính. Bảng dưới đây tổng hợp tiêu chí lựa chọn hai phương thức, và sự khác biệt bắt nguồn không phải từ sở thích đơn thuần mà từ đặc tính bài toán "có nhiều trạng thái thừa không, đệ quy có sâu không".

Việc chọn giữa hai phương thức trong thực tế phân nhánh theo các ràng buộc cụ thể. Chẳng hạn nếu n vượt 100.000 và độ sâu đệ quy có nguy cơ vượt giới hạn ngăn xếp mặc định (1.000 với Python, mức vài vạn với nhiều ngôn ngữ), thì ghi nhớ dựa trên đệ quy có thể chết vì tràn ngăn xếp, buộc phải dùng lập bảng. Ngược lại, ở bài toán 'thưa (sparse)' mà không gian trạng thái trên lý thuyết khổng lồ nhưng trạng thái thực sự ghé thăm chỉ là một phần rất nhỏ, thì ghi nhớ — vốn chỉ tính các trạng thái cần — có lợi cả về bộ nhớ lẫn thời gian. Nói cách khác, căn cứ lựa chọn không phải sở thích về mã mà là đặc tính định lượng của mật độ không gian trạng thái và độ sâu đệ quy.

Phân loại	Ghi nhớ (Top-Down)	Lập bảng (Bottom-Up)
Hướng	Bài toán lớn → nhỏ (đệ quy)	Bài toán nhỏ → lớn (lặp)
Phạm vi tính	Chỉ bài toán con cần	Mọi bài toán con
Ưu điểm	Trực quan, lợi cho trạng thái thưa	An toàn ngăn xếp, hệ số hằng nhỏ, dễ tối ưu không gian
Nhược điểm	Chi phí đệ quy, giới hạn ngăn xếp	Cần thiết kế thứ tự, có thể tính thừa
Tình huống phù hợp	Không gian trạng thái lớn và thưa	Không gian trạng thái dày, cần tất cả

3. Quy trình thiết kế quy hoạch động

Trong thực tế, quá trình giải một bài toán DP có thể định dạng thành quy trình năm bước sau. Cốt lõi của quy trình này nằm không phải ở lập trình mà ở bước mô hình hóa 'định nghĩa trạng thái (state) và xây dựng công thức truy hồi'.

flowchart LR
  S1["1. Định nghĩa trạng thái<br/>(lưu gì)"] --> S2["2. Xây công thức truy hồi<br/>(quan hệ giữa các trạng thái)"]
  S2 --> S3["3. Điều kiện cơ sở<br/>(giá trị ban đầu)"]
  S3 --> S4["4. Thứ tự tính<br/>(sắp topo theo phụ thuộc)"]
  S4 --> S5["5. Phục hồi lời giải<br/>(truy vết ngược)"]

Bước 1, định nghĩa trạng thái, là việc xác định "các biến nhận diện duy nhất một bài toán con". Ví dụ bài toán cái túi định nghĩa dp[i][w] là "giá trị lớn nhất khi chỉ xét i vật phẩm đầu và sức chứa là w". Nếu chọn sai trạng thái thì công thức truy hồi không thành lập, nên bước này quyết định thành bại của toàn bộ thiết kế. Bước 2, công thức truy hồi, biểu diễn quan hệ phụ thuộc giữa các trạng thái bằng công thức. Bước 3, điều kiện cơ sở, nêu rõ giá trị của các trạng thái nhỏ nhất nơi đệ quy dừng (ví dụ dp[0][*]=0). Bước 4, thứ tự tính, sắp xếp topo theo phụ thuộc xem phải điền trạng thái nào trước, đặc biệt quan trọng trong lập bảng. Bước 5, phục hồi lời giải, là bước truy vết ngược để phục hồi không chỉ giá trị tối ưu mà cả "lựa chọn đã tạo ra giá trị đó (đã xếp vật phẩm nào)", lần ngược lại đường quyết định đã lưu.

Điểm mà người mới học thất bại thường xuyên nhất trong quy trình này là bước 1~2. Nếu định nghĩa trạng thái quá hẹp (không chứa đủ thông tin cần vào trạng thái) thì công thức truy hồi phụ thuộc vào lựa chọn quá khứ và không thành lập; nếu quá rộng thì không gian trạng thái bùng nổ và độ phức tạp lớn tới mức phi thực tế. Do đó, câu hỏi cốt lõi của định nghĩa trạng thái là "thông tin tối thiểu cần để ra quyết định hiện tại là gì". Công thức truy hồi cũng quy về một câu 'có thể biểu diễn trạng thái hiện tại bằng tổ hợp của những trạng thái nhỏ hơn nào', và một khi mô hình hóa này được sắp xếp rõ ràng trên giấy thì việc cài đặt gần như là công việc máy móc. Ngay trong bài thi kỹ sư chuyên nghiệp, chính bộ ba trạng thái, công thức truy hồi và điều kiện cơ sở — trình bày bằng công thức chứ không phải mã — mới là trung tâm của việc chấm điểm.

4. Các trường hợp tiêu biểu

Trước khi vào các trường hợp tiêu biểu, nếu xác nhận hiệu quả của DP bằng số liệu với trường hợp đơn giản nhất là Fibonacci thì các trường hợp sau sẽ sáng tỏ. Giải fib(50) bằng đệ quy đơn giản sinh ra khoảng 2×10¹⁰ lần gọi hàm, mất hàng chục giây trên một PC thông thường, nhưng điền dp[0]=0, dp[1]=1, dp[i]=dp[i-1]+dp[i-2] từ dưới lên thì kết thúc tức thì trong 51 phép cộng. Hơn nữa, vì Fibonacci chỉ phụ thuộc hai giá trị liền trước nên có thể tính chỉ bằng hai biến (không gian O(1)) mà không cần giữ toàn mảng. Một ví dụ này nén lại cả ba cốt lõi của DP — loại bỏ trùng lặp, đánh đổi không gian lấy thời gian, và tối ưu không gian trạng thái.

A. Bài toán cái túi 0/1 (0/1 Knapsack)

Bài toán cái túi 0/1 xếp các vật phẩm có trọng lượng và giá trị cho trước vào một cái túi sức chứa W để tối đa hóa tổng giá trị, trong đó mỗi vật phẩm chỉ chọn xếp hoặc không xếp (0 hoặc 1). Vét cạn kiểm tra tất cả 2ⁿ tập con của n vật phẩm nên là hàm mũ, nhưng DP chỉ điền n×W trạng thái với công thức truy hồi dp[i][w] = max(dp[i-1][w], dp[i-1][w-trọng_lượngᵢ] + giá_trịᵢ) và giải trong O(nW). Ví dụ với n=100, W=1000, vét cạn là 2¹⁰⁰ (khoảng 10³⁰) phép tính, trong khi DP kết thúc trong 100.000 phép tính, vượt hẳn ranh giới của tính thực dụng.

Điểm cần lưu ý là O(nW) này mang tính 'giả đa thức (pseudo-polynomial)'. W là 'giá trị' của đầu vào chứ không phải 'kích thước (số bit)', nên nếu W rất lớn thì vẫn phi thực tế. Đây chính là lý do cái túi 0/1, dù được phân loại NP-khó, vẫn giải được bằng DP. Trường hợp này đồng thời minh họa nguyên lý "độ phức tạp của DP tỷ lệ với kích thước không gian trạng thái" và cái bẫy khi không gian trạng thái đó phụ thuộc vào giá trị đầu vào.

B. Dãy con chung dài nhất (LCS) và khoảng cách chỉnh sửa

LCS tìm dãy con dài nhất có thể rút ra chung, giữ nguyên thứ tự, từ hai chuỗi; nó định nghĩa dp[i][j] là "độ dài LCS của i ký tự đầu chuỗi1 và j ký tự đầu chuỗi2". Nếu ký tự trùng thì điền dp[i-1][j-1]+1, nếu khác thì max(dp[i-1][j], dp[i][j-1]), giải trong O(mn). Khoảng cách chỉnh sửa (Levenshtein Distance) cũng tính số lần tối thiểu của ba phép toán — chèn, xóa, thay thế — bằng cùng một DP hai chiều.

Hai trường hợp này được dùng rất rộng rãi trong công nghiệp. LCS là nền tảng của git diff / so sánh khác biệt trong quản lý phiên bản và căn chỉnh chuỗi DNA (bioinformatics), còn khoảng cách chỉnh sửa được dùng trong sửa chính tả, sửa lỗi gõ từ khóa tìm kiếm, và đo độ tương đồng DNA. Ví dụ khi một công cụ tìm kiếm đề xuất sửa lỗi gõ "teh" thành "the", nó tính bằng DP sự thật rằng khoảng cách chỉnh sửa giữa hai từ là nhỏ rồi tận dụng. Độ tương đồng chuỗi, một trong các chỉ số đánh giá đầu ra của AI tạo sinh, cũng bắt rễ từ họ DP này.

C. Floyd-Warshall (đường đi ngắn nhất mọi cặp)

Floyd-Warshall là thuật toán DP tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị. Nó định nghĩa dp[k][i][j] là "khoảng cách ngắn nhất i→j khi chỉ cho phép các đỉnh 1~k làm trung chuyển", và cập nhật bằng dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]), tăng dần đỉnh trung chuyển k từng cái một. Thuật toán tìm mọi cặp trong O(V³) bằng ba vòng lặp lồng nhau này được dùng trong tính bảng định tuyến, phân tích độ trễ mạng, và lập bảng khoảng cách mạng lưới giao thông. Nó có ưu điểm cài đặt ngắn gọn hơn so với lặp Dijkstra từ mọi đỉnh và xử lý được trọng số âm (trừ chu trình âm).

Bài học của Floyd-Warshall là ý tưởng 'thêm chiều đỉnh trung chuyển vào trạng thái'. Định nghĩa đường đi ngắn nhất chỉ bằng khoảng cách khiến công thức truy hồi tuần hoàn và không thành lập, nhưng đặt "tập đỉnh được phép trung chuyển" làm biến giai đoạn k sẽ tạo nên cấu trúc không chu trình trong đó k tăng đơn điệu, làm cho DP khả thi. Việc cùng một bài toán có thể giải được hay không tùy vào cách định nghĩa trạng thái cho thấy một cách sắc nét vì sao thiết kế trạng thái là cốt lõi của DP.

D. Dãy con tăng dài nhất (LIS)

Dãy con tăng dài nhất (Longest Increasing Subsequence) tìm độ dài của dãy con 'tăng' dài nhất có thể rút ra từ một dãy số trong khi giữ nguyên thứ tự. DP cơ bản định nghĩa dp[i] là "độ dài LIS kết thúc tại phần tử thứ i" và điền bằng dp[i] = max(dp[j]) + 1 (với j<i và phần_tửⱼ<phần_tửᵢ), giải trong O(n²). Ví dụ LIS của [10, 9, 2, 5, 3, 7, 101, 18] là [2, 3, 7, 18] với độ dài 4, thu được bằng cách mỗi vị trí kế thừa giá trị dp lớn nhất trong các phần tử đứng trước nhỏ hơn chính nó.

LIS quan trọng về mặt giáo dục vì nó là trường hợp điển hình của việc kết hợp DP với một cấu trúc dữ liệu khác để làm nó nhanh hơn. Ghép thêm tìm kiếm nhị phân, ta có thể tìm trong O(log n) vị trí chèn mỗi phần tử vào 'mảng đuôi của các dãy tăng', cải thiện toàn bộ xuống O(n log n). Đây là một mẫu thiết kế nâng cao "bản thân công thức truy hồi DP là O(n²), nhưng giảm chi phí chuyển tiếp (transition) bằng cấu trúc dữ liệu để hạ độ phức tạp tổng thể", và là điểm khởi đầu của tối ưu DP kết hợp cây phân đoạn và cây Fenwick. Trong thực tế, nó được dùng ở dạng biến thể cho lập lịch công việc, tìm đường tương thích phiên bản, và phân tích xu hướng giá cổ phiếu.

5. So sánh với chia để trị và tham lam

Cả ba mô thức đều có điểm chung "chia nhỏ bài toán", nhưng phân nhánh ở chỗ bài toán con có chồng lấp không và chiến lược lựa chọn. Bảng dưới đây tóm tắt sự khác biệt, đồng thời nhìn cả 'lý do' nảy sinh khác biệt.

Phân loại	Quy hoạch động	Chia để trị	Tham lam
Chồng lấp bài toán con	Có (lưu và tái sử dụng)	Không (độc lập)	Không
Hướng triển khai	Cả dưới lên/trên xuống	Trên xuống (đệ quy)	Quyết định tuần tự
Cách lựa chọn	So sánh mọi trường hợp rồi lấy tối ưu	Chia rồi trộn	Tối ưu cục bộ mỗi bước
Bảo đảm tối ưu	Luôn luôn (khi đủ điều kiện)	Tùy tiêu chí chia	Cần tính chất lựa chọn tham lam
Ví dụ tiêu biểu	Cái túi, LCS, Floyd	Sắp xếp trộn, tìm kiếm nhị phân	Trả tiền thừa, MST, Huffman

Sự khác biệt quyết định giữa chia để trị và DP là bài toán con có chồng lấp hay không. Sắp xếp trộn chia mảng làm đôi, nhưng hai nửa hoàn toàn độc lập nên không có gì để tái sử dụng. Ngược lại, fib(n-1) và fib(n-2) của Fibonacci chia sẻ fib(n-2) nên việc lưu trữ mang lại lợi ích. Nói cách khác, "các mảnh được chia có chồng lấp với nhau không" quyết định dùng DP hay chia để trị.

Sự khác biệt giữa tham lam và DP nằm ở khả năng xem xét lại lựa chọn. Tham lam ở mỗi bước chọn phương án trông tốt nhất và không ngoái lại. Để điều này bảo đảm tối ưu toàn cục thì phải chứng minh được 'tính chất lựa chọn tham lam'. Ví dụ cái túi chia nhỏ được (fractional) là tối ưu với phương pháp tham lam xếp theo thứ tự giá trị trên đơn vị trọng lượng giảm dần, nhưng cái túi 0/1 thì không, nên nhất thiết phải so sánh mọi trường hợp bằng DP. Hàm ý thực tế rất rõ — nếu phương pháp tham lam đúng thì nó nhanh và đơn giản hơn DP, nhưng nếu chứng minh tính chất lựa chọn tham lam thất bại thì phải chuyển an toàn sang DP. Áp dụng tham lam vội vã sinh ra loại lỗi nguy hiểm nhất: "phần lớn đúng nhưng thỉnh thoảng sai".

Thực ra, ba mô thức nằm trên một dải liên tục hơn là loại trừ lẫn nhau. Tham lam có thể xem là "một DP đặc biệt chỉ để lại một lựa chọn ở mỗi bước", và chia để trị là "một DP đặc biệt trong đó các bài toán con không chồng lấp". Từ góc nhìn này, khi gặp một bài toán, một luồng ra quyết định tự nhiên hiện ra: kiểm tra theo thứ tự ① các bài toán con có chồng lấp không (nếu không thì chia để trị), và ② nếu chồng lấp thì một lựa chọn mỗi bước có đủ không (nếu đủ thì tham lam, nếu không thì DP tổng quát). Ở trình độ kỹ sư chuyên nghiệp, cần thể hiện chính luồng phân định này thành tri thức thiết kế — vượt lên trên việc ghi nhớ từng thuật toán — và có khả năng trình bày kèm căn cứ mô thức nào phù hợp với bài toán nghiệp vụ đã cho.

6. Chuyên sâu: Tối ưu không gian trạng thái và các ứng dụng mới

Khó khăn thực tế của DP là khi không gian trạng thái vượt quá bộ nhớ. Một giải pháp tiêu biểu là kỹ thuật cửa sổ trượt (rolling array): nếu công thức truy hồi chỉ phụ thuộc hàng liền trước (dp[i-1]) thì nén mảng hai chiều thành một chiều, giảm không gian từ O(nW) xuống O(W). Ví dụ là thu được đúng cùng một đáp án chỉ với mảng một chiều bằng cách duyệt sức chứa theo thứ tự ngược trong bài toán cái túi. Ngoài ra, DP mặt nạ bit (bitmask DP), mã hóa trạng thái thành mặt nạ bit, giải các bài toán lấy một tập làm trạng thái — như bài toán người bán hàng (TSP) — trong O(2ⁿ·n²), nhanh hơn một cách đột phá so với O(n!) của vét cạn. Với n=15, sự khác biệt giữa 15! (khoảng 1,3 nghìn tỷ) và 2¹⁵·15² (khoảng 7,4 triệu) lại một lần nữa cho thấy sức mạnh của DP.

Một trường hợp tiêu biểu khác trong công nghiệp là định giá quyền chọn trong kỹ thuật tài chính. Mô hình cây nhị phân định giá quyền chọn kiểu Mỹ (có thể thực hiện sớm trước đáo hạn) tính giá trị tại mỗi nút thời điểm/giá ngược từ giá trị tại đáo hạn theo max(giá trị thực hiện ngay, kỳ vọng chiết khấu của giá trị nắm giữ) — một DP từ dưới lên điển hình. Ngoài ra, bộ tối ưu hóa truy vấn (optimizer) cơ sở dữ liệu, khi định thứ tự kết nối nhiều bảng, dùng DP mặt nạ bit để tìm kế hoạch kết nối chi phí thấp nhất theo từng tập con, tìm ra thứ tự tối ưu trong O(3ⁿ) (kỹ thuật cổ điển từ thời System R). Giải mã Viterbi trong truyền thông cũng tìm đường hợp lẽ cực đại của mã chập bằng DP, cho thấy DP là một động cơ cốt lõi trên khắp tài chính, DB và truyền thông vượt ra ngoài sách giáo khoa thuật toán.

Về xu hướng mới, có thể kể đến việc DP đã thấm sâu vào học máy và xử lý ngôn ngữ tự nhiên, vượt ra ngoài các thuật toán truyền thống. Giải mã Mô hình Markov ẩn (HMM), cốt lõi của nhận dạng giọng nói và nhận dạng chữ viết tay, tìm chuỗi trạng thái tối ưu bằng một DP gọi là thuật toán Viterbi, còn các thuật toán Needleman-Wunsch và Smith-Waterman cho căn chỉnh chuỗi DNA/protein cũng là DP thuộc họ khoảng cách chỉnh sửa. Phương trình Bellman (Bellman Equation) của học tăng cường lấy tên trực tiếp từ người sáng lập quy hoạch động, và Lặp giá trị (Value Iteration) cùng Lặp chính sách (Policy Iteration) đều là ứng dụng trực tiếp của DP. Từ góc nhìn kỹ sư chuyên nghiệp, nên hiểu DP không phải là một kỹ thuật lập trình đơn thuần mà là một khung tư duy tổng quát phân rã việc ra quyết định tối ưu thành nhiều giai đoạn.

Hướng ra đề có khả năng gồm: ① suy dẫn công thức truy hồi và độ phức tạp của một bài toán cụ thể (cái túi, LCS, dãy con tăng dài nhất, v.v.), ② so sánh với chia để trị và tham lam cùng việc phân định điều kiện áp dụng, ③ căn cứ chọn ghi nhớ/lập bảng, và ④ quan hệ giữa độ phức tạp giả đa thức và tính NP-khó. Khi viết bài, chiến lược đạt điểm cao là luôn nêu rõ công thức truy hồi, suy dẫn độ phức tạp từ kích thước không gian trạng thái, và trình bày kèm căn cứ "vì sao là DP chứ không phải tham lam/chia để trị" (cấu trúc con tối ưu, bài toán con chồng lấp).

Minh họa một chiến lược bố cục bài làm cụ thể: ngay cả với một câu trả lời ngắn ở buổi thi thứ nhất, chiều sâu vẫn hiện ra nếu có bộ khung "định nghĩa → hai điều kiện → một công thức truy hồi tiêu biểu (ví dụ cái túi) → độ phức tạp → một dòng so sánh với các kỹ thuật khác". Với bài luận ở buổi thi thứ hai hoặc thứ ba thì chồng lên trên đó ⓐ một sơ đồ khái niệm (khác biệt giữa vét cạn và DP), ⓑ quy trình thiết kế năm bước, ⓒ suy dẫn công thức truy hồi và độ phức tạp theo từng trường hợp cho hai trường hợp trở lên, ⓓ các kỹ thuật tối ưu không gian trạng thái (cửa sổ trượt, mặt nạ bit), và ⓔ một phán định áp dụng theo góc nhìn kỹ sư chuyên nghiệp (cái bẫy giả đa thức, luồng chọn mô thức). Đặc biệt, người chấm xem "có xây được công thức truy hồi không" và "có phân định được điều kiện áp dụng không" là những điểm phân biệt then chốt, nên việc thể hiện bằng văn xuôi quá trình tư duy từ định nghĩa trạng thái đến công thức truy hồi, thay vì một kết quả học thuộc, là điều quyết định.

7. Điểm cần cân nhắc và hàm ý

Kiểm chứng điều kiện áp dụng trước (tính đúng đắn): DP không phải thuốc vạn năng. Phải kiểm chứng trước rằng cả cấu trúc con tối ưu lẫn bài toán con chồng lấp đều thành lập; áp dụng DP cho một bài toán như đường đi đơn dài nhất, nơi kết hợp các lời giải con không bảo đảm lời giải tổng thể, sẽ cho đáp án sai. Trước khi thiết kế, luôn chứng minh "kết hợp các lời giải con có tạo thành lời giải tổng thể không".
Quản lý sự đánh đổi không gian-thời gian (hiệu quả tài nguyên): DP đánh đổi thời gian lấy bộ nhớ. Khi không gian trạng thái vượt giới hạn bộ nhớ, một thiết kế giảm không gian bằng cửa sổ trượt, nén trạng thái, hay lưu trữ thưa (bảng băm) là thiết yếu. Trong môi trường nhúng và quy mô lớn, việc có thực hiện tối ưu này hay không chi phối khả năng áp dụng.
Cái bẫy của độ phức tạp giả đa thức (phán định hiệu năng): Khi độ phức tạp tỷ lệ với 'giá trị' đầu vào, như O(nW) của bài toán cái túi, thì trên thực tế nó chậm theo hàm mũ khi giá trị lớn. Việc một bài toán NP-khó giải được bằng DP không có nghĩa là nó thực dụng ở mọi quy mô, nên hãy phán định tính hợp lệ của việc áp dụng dựa trên phạm vi đầu vào.
Chiến lược chọn mô thức (phán định thiết kế): Nếu phương pháp tham lam thành lập thì nó nhanh và đơn giản hơn DP nên hãy cân nhắc trước; nhưng nếu chứng minh tính chất lựa chọn tham lam thất bại thì chuyển sang DP. Nếu các bài toán con độc lập thì chia để trị mới đúng. Thay vì nhìn ba mô thức như loại trừ lẫn nhau, năng lực của kỹ sư là sự sáng suốt chọn lựa và kết hợp chúng theo đặc tính bài toán.
Mở rộng thành khung tư duy tổng quát (triển vọng và công nghệ liên đới): DP là một khung tối ưu hóa tổng quát mở rộng tới học tăng cường (phương trình Bellman), căn chỉnh chuỗi (tin sinh học), và nhận dạng giọng nói/chữ viết tay (Viterbi). Hiểu nó như liên kết với các công nghệ nền tảng của lĩnh vực AI/dữ liệu, vượt ra ngoài các thuật toán truyền thống, sẽ mở rộng rất nhiều phạm vi ứng dụng.

Tài liệu tham khảo

Cormen et al., "Introduction to Algorithms", MIT Press (quy hoạch động, cấu trúc con tối ưu)
R. Bellman, "Dynamic Programming", Princeton University Press, 1957
cp-algorithms, Dynamic Programming: https://cp-algorithms.com/dynamic_programming/

Tóm tắt một câu: Quy hoạch động là kỹ thuật, đối với các bài toán mà cấu trúc con tối ưu và bài toán con chồng lấp thành lập, chia bài toán thành các bài toán con rồi lưu và tái sử dụng lời giải của chúng để hạ độ phức tạp tìm kiếm từ hàm mũ xuống thời gian đa thức; nó được cài đặt bằng ghi nhớ/lập bảng, và — khác với tham lam và chia để trị — cốt lõi là phán định thiết kế "so sánh mọi trường hợp nhưng chỉ tính mỗi phần trùng lặp một lần".