Trong bài viết này, vncode.tech sẽ giới thiệu với các bạn một thuật toán thần thánh: thuật toán quy hoạch động. Nếu bạn tham gia các cuộc thi code, bạn nhất định phải biết thuật toán này.
Gần một nửa các bài thi trong các cuộc thi code cần đến quy hoạch động. Tất nhiên, có những cách khác để giải bài toán đó. Nhưng vì các cuộc thi code đều có giới hạn về thời gian, cũng như bộ nhớ của chương trình, nên một thuật toán hiệu quả là cực kỳ cần thiết. Và trong những trường hợp như vậy, quy hoạch động là một trong những thuật toán xuất hiện nhiều nhất.
Thuật toán quy hoạch động được ưa chuộng bởi vì ban đầu, bài toán có muôn hình vạn trạng và bạn phải suy nghĩ rất nhiều mới tìm ra được lời giải. Không có một công thức chuẩn mực nào áp dụng được cho mọi bài toán. Bởi vì sự phổ biến của nó, bạn bắt buộc phải cực kỳ thuần thục thuật toán này nếu muốn áp dụng nó vào các bài tập.
1. Khái niệm
Quy hoạch động là một kỹ thuật trong lập trình giúp giải quyết một cách hiệu quả một lớp vấn đề có các bài toán con gối nhau và cấu trúc con tối ưu. Những bài toán như vậy liên quan đến việc tính toán nhiều lần giá trị của các bài toán con giống nhau để tìm ra giải pháp tối ưu.
- Các bài toán con gối nhau: Bài toán con là các bài toán nhỏ hơn của bài toán ban đầu. Bất kỳ bài toán nào cũng có các bài toán con trùng nhau nếu việc tìm lời giải của nó liên quan đến việc giải cùng một bài toán con nhiều lần.
- Cấu trúc con tối ưu: Bất kỳ bài toán nào cũng có thuộc tính cấu trúc con tối ưu nếu giải pháp tối ưu tổng thể của nó có thể được xây dựng từ các giải pháp tối ưu của các bài toán con của nó.
Thường thì một bài toán có đủ cả hai tính chất này, chúng ta có thể dùng quy hoạch động được.
Các bài toán con chồng chéo
Tương tự như thuật toán chia để trị, quy hoạch động cũng chia bài toán lớn thành các bài toán con nhỏ hơn. Quy hoạch động được sử dụng khi các bài toán con này được gọi đi gọi lại. Phương pháp quy hoạch động sẽ lưu kết quả của bài toán con này, và khi được gọi, nó sẽ không cần phải tính lại, do đó làm giảm thời gian tính toán.
Một ví dụ rất điển hình của bài toán con gối nhau là bài toán tính số Fibonacci. Bài toán quá nổi tiếng rồi, chúng ta có thể tính toán số Fibonacci theo đúng công thức như sau:
int fib(int n)
{
if(n<=1)
return n;
return fib(n-1)+fib(n-2);
}Nếu tính toán như trên, chúng ta rất nhiều bài toán con sẽ được tính đi tính lại, điển hình là các số fib(0) và fib(1).
Và quy hoạch động chính là một trong số những phương pháp có thể giúp chúng ta tối ưu hóa quá trình tính toán này. Mỗi bài toán con (số fib) sẽ được lưu lại trước khi tính những bài toán con lớn hơn. Nhờ đó, mà việc tính toán giảm đi đáng kể, mỗi bài toán con chỉ cần tính đúng một lần.
int fibonacci(int n)
{
fib[0]=0;
fib[1]=1;
for(int i=2; i<=n; i++)
fib[i]=fib[i-1]+fib[i-2];
return fib[n];
}Cấu trúc con tối ưu
Cấu trúc con tối ưu là một tính chất là lời giải của bài toán lớn sẽ là tập hợp lời giải từ các bài toán nhỏ hơn. Ví dụ:
Trong bài toán tìm đường đi ngắn nhất trong đồ thị, nếu một node 
nằm trên đường đi ngắn nhất giữa hai node 
thì đường đi ngắn nhất từ u đến 
sẽ là tổng hợp của đường đi ngắn nhất từ 
đến và đường đi ngắn nhất từ’ đến v. Môt số thuật toán tìm đường trên đồ thị (nổi tiếng nhất có lẽ là Dijkstra) đều dựa trên tính chất này, và nó cũng áp dụng quy hoạch động.
Tính chất cấu trúc con tối ưu rất quan trọng. Nó cho phép chúng ta giải bài toán lớn dựa vào các bài toán con đã giải được. Nếu không có tính chất này, chúng ta không thể áp dụng quy hoạch động được.
2. Các dạng toán quy hoạch động
Bài toán tối ưu
Bài toán tối ưu yêu cầu chúng ta phải tìm đáp án tốt nhất từ mục tiêu của bài toán. Mối liên hệ của các bài toán con thuộc dạng này có công thức chung là dp[s] = min(F1(dp[i], dp[j], ..., dp[k]), F2(dp[u], dp[v], ..., dp[w]), ..., Fl(dp[q], dp[p], ..., dp[z])), trong đó dp mảng lưu kết quả của các bài toán con đó.
Trước khi tính toán, mảng chứa kết quả có thể được điền đầy một giá trị trung tính nào đó. Giá trị trung tính có nghĩa là giá trị đó sẽ không bao giờ là đáp án cho bất kỳ bài toán con nào. Ví dụ khi cần tìm ra số dương nhỏ nhất, chúng ta có thể điền mảng này bằng số dương lớn nhất, mọi tính toán tiếp theo sẽ cho ra một kết quả nhỏ hơn nhiều. Nếu không ra kết quả nào khác, chúng ta có thể coi như là không có một đáp án nào cho bài toán con đó.
Bài toán tổ hợp
Bài toán tổ hợp thường yêu cầu chúng ta tìm ra số cách khác nhau để thực hiện một việc gì đó. Trong dạng bài toán này, công thức khi xây dựng các bài toán con sẽ là R[s] = F1(R[i], R[j], ..., R[k]) + F2(R[u], R[v], ..., R[w]) + ... + Fl(R[q], R[p], ..., R[z]). Sự khác biệt cơ bản của dạng bài toán này với dạng bài toán tối ưu là ở chỗ chúng ta cần tính tổng thay vì tìm số lớn nhất hoặc nhỏ nhất.
Trong mọi bài toán quy hoạch động, tính chất cấu trúc con tối ưu luôn là quan trọng nhất và cũng là tính chất khó đảm bảo nhất. Nếu cấu trúc con không được tối ưu, chúng ta sẽ tính toán theo một phương thức sai lầm và đương nhiên, kết quả thu được cũng không chính xác.
Với phần lớn các bài toán quy hoạch động, việc chia các bài toán con gối nhau khá dễ dàng trong khi đảm bảo cấu trúc con tối ưu thì khó hơn nhiều.