I. Giới thiệu chung

Ta đã biết rằng, giải pháp chúng ta thường sử dụng để giải một bài toán có bản chất đệ quy mà tồn tại các bài toán con gối nhau và cấu trúc con tối ưu là Quy hoạch động. Thông thường, khi cài đặt các bài toán quy hoạch động, chúng ta hay quen với việc đi từ những bài toán nhỏ, dần dần tiến lên tính toán các bài toán lớn hơn dựa vào công thức truy hồi. Cách cài đặt đó được gọi là cách cài đặt bottom-up (đi từ dưới lên trên), hay tabulation. Tuy nhiên, còn một cách cài đặt nữa cũng có thể sử dụng được, đó là cách cài đặt top-down (đi từ trên xuống dưới). Trong cách làm này, ta sẽ sử dụng đệ quy để phân tách bài toán lớn thành các bài toán nhỏ, rồi tính toán kết quả của chúng dựa trên công thức truy hồi, đồng thời lưu luôn kết quả lại vào một bảng phương án để tránh việc phải tính toán lại các bài toán con gối nhau. Điều này sẽ giúp tối ưu thời gian chạy cho giải thuật đệ quy, chính vì vậy, cách làm này còn được gọi là ***đệ quy có nhớ (recursion with memoization)***.

Lược đồ tổng quát của cài đặt top-down có thể mô tả đơn giản như sau:

void top_down_dp({Danh_sách_tham_số})
{ {Nếu đã tiến tới bài toán nhỏ nhất} return; {Nếu bài toán hiện tại đã được tính rồi} return; {Gọi đệ quy phân tách bài toán hiện tại thành các bài toán con}
}

Phương án cài đặt top-down có ưu điểm là cài đặt ngắn gọn, đơn giản, minh họa ý tưởng tốt, tuy nhiên lại có nhược điểm là tốn bộ nhớ hơn, vì các lời gọi đệ quy sẽ được lưu trữ trong vùng nhớ stack (nên thời gian chạy của cách cài đặt này sẽ chậm hơn bottom-up một chút xíu). Ngoài ra, các kĩ thuật tối ưu cho quy hoạch động sẽ khó áp dụng hơn khi sử dụng phương án cài đặt top-down. Vì vậy, tùy vào bài toán mà chúng ta sẽ lựa chọn cách cài đặt sao cho phù hợp.

Dưới đây là bảng so sánh về hiệu quả giữa hai cách cài đặt top-down và bottom-up:

Sau đây, tôi sẽ trình bày một vài bài toán minh họa cho cách cài đặt top-down để bạn đọc hiểu rõ hơn về cách cài đặt này.

II. Một số bài toán minh họa

1. Dãy Fibonacci

Đề bài

Dãy số Fibonacci được định nghĩa theo công thức:

$$\begin{cases}f_0 = 0, f_1 = 1.\\ f_i = f_{i - 1} + f_{i - 2}; \forall i > 2. \end{cases}$$

Yêu cầu: Cho trước số nguyên dương $n,$ hãy tìm số Fibonacci thứ $n?$

Input:

• Chứa duy nhất số nguyên dương $n$.

Ràng buộc:

• $1 \le n \le 10^5$.

Output:

• In ra số fibonacci thứ $n$. Do kết quả có thể rất lớn nên chỉ cần đưa ra phần dư của kết quả khi chia cho $10^9 + 7$.

Sample Input:

5

Sample Output:

5

Ý tưởng

Đây là bài toán rất cơ bản mà ai cũng được học cả trong đệ quy lẫn nhập môn quy hoạch động. Ta có thể giải bài toán này bằng đệ quy theo mô hình dưới đây, tuy nhiên thời gian chạy sẽ rất lâu do đây là một bài toán có nhiều bài toán con gối nhau:

int fibo(int n)
{ if (n == 0 || n == 1) return n; return fibo(n - 1) + fibo(n - 2);
}

Để cải tiến, ta sẽ dùng bảng phương án $f[i]$ để lưu lại số fibonacci thứ $i$. Cài đặt theo phương pháp top-down hay bottom-up trong trường hợp này đều được, vì độ đơn giản là như nhau!

Cài đặt

Kiểu top-down:

#include <bits/stdc++.h>
#define int long long using namespace std; const int mod = 1e9 + 7; int fibo(int n, vector < int > &f)
{ if (n <= 1) return n; if (f[n] != 0) return f[n]; f[n] = (fibo(n - 1) + fibo(n - 2)) % mod; return f[n];
} main()
{ int n; cin >> n; vector < int > f(n + 1); cout << fibo(n, f);
}

Kiểu bottom-up:

#include <bits/stdc++.h>
#define int long long using namespace std; const int mod = 1e9 + 7; main()
{ int n; cin >> n; vector < int > f(n + 1); f[0] = 0; f[1] = 1; for (int i = 2; i <= n; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod; cout << f[n];
}

2. Bài toán cái túi 0 - 1

Đề bài

Cho $n$ đồ vật khác nhau, đồ vật thứ $i$ có trọng lượng $w_i$ và giá trị $v_i$. Bạn mang theo một chiếc túi có tải trọng tối đa là $W,$ nhiệm vụ của bạn là chọn ra các đồ vật để cho vào túi sao cho tổng giá trị của các đồ vật lấy được là lớn nhất có thể.

Yêu cầu: Tìm ra tổng giá trị lớn nhất có thể lấy được từ $n$ đồ vật?

Input:

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $W$.
• $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $w_i$ và $v_i$ phân tách nhau bởi dấu cách.

Ràng buộc:

• $1 \le n \le 1000$.
• $1 \le W \le 1000$.
• $1 \le w_i, v_i \le 100; \forall i: 1 \le i \le n$.

Output:

• In ra tổng giá trị lớn nhất của các vật lấy được.

Sample Input:

3 50
10 60
20 100
30 120

Sample Output:

220
2 3

Ý tưởng

Đây là bài toán quy hoạch động khá quen thuộc. Tuy nhiên, trong bài viết này chúng ta sẽ tìm hiểu về cách cài đặt top-down cho bài toán trên.

Trước hết, ta xem xét tính đệ quy của bài toán:

Gọi $dp(i, j)$ là tổng giá trị lớn nhất thu được khi chọn các đồ vật từ vật thứ nhất tới vật thứ $i,$ và giới hạn trọng lượng của chiếc túi là $j$. Xét tới đồ vật thứ $i,$ ta sẽ có hai phương án xử lý:

• Nếu như ta lựa chọn đồ vật thứ $i$ vào danh sách các vật được chọn, thì giá trị nhận thêm được sẽ là $v_i,$ và giới hạn trọng lượng còn lại của chiếc túi là $j - w_i$. Dĩ nhiên, trường hợp này chỉ xảy ra khi $j \ge w_i$. Tức là ta có giá trị mới là: $dp(i - 1, j - w_i) + v_i$.
• Nếu như không lựa chọn đồ vật thứ $i$ vào danh sách các vật được chọn, thì giá trị tối ưu nhận được vẫn sẽ giống như khi lựa chọn trong các đồ vật từ $1$ tới $i - 1$. Trường hợp này có thể xảy ra cả khi $j \ge w_i$ và $j < w_i$. Khi đó ta có giá trị thu được là: $dp(i - 1, j)$.

Mà chúng ta đang cần chọn được giá trị lớn nhất, nên ta có công thức truy hồi:

$$dp(i, j) = \begin{cases} dp(i - 1, j); \text{nếu } j < w_i. \\ \text{max}\big(dp(i - 1, j), dp(i - 1, j - w_i) + w_i \big); \text{nếu } j \ge w_i.\end{cases}$$

Bài toán cơ sở (neo) sẽ là $dp(0, j) = 0,$ vì ta không thể chọn được vật nào nếu như $i = 0;$ còn các $dp(i, j)$ với $j < 0$ sẽ có giá trị $-\infty$. Kết quả cần tìm sẽ nằm ở trạng thái: $dp(n, W)$. Ta sẽ sử dụng một bảng phương án hai chiều $dp[i][j]$ để lưu trữ lại kết quả trong quá trình tính toán.

Cài đặt

Kiểu top-down:

#include <bits/stdc++.h> using namespace std; int top_down_dp(int i, int j, vector < vector < int > > &dp, vector < vector < int > > &items)
{ // Xử lý trước các trường hợp neo (cơ sở quy hoạch động). if (j < 0) return -INFTY; if (i == 0) return 0; // Nếu bài toán con hiện tại đã được tính xong thì không tính lại. if (dp[i][j] != 0) return dp[i][j]; // Hai trường hợp không chọn và chọn đồ vật thứ i. int skip = top_down_dp(i - 1, j); int take = top_down_dp(i - 1, j - items[i].first) + items[i].second; // Tính kết quả bài toán hiện tại và lưu luôn vào bảng phương án. if (j >= items[i].first) dp[i][j] = max(skip, take); else dp[i][j] = skip; // Trả về kết quả cho bài toán hiện tại. return dp[i][j];
} main()
{ int n, W; cin >> n >> W; vector < pair < int, int > > items(n + 1); for (int i = 1; i <= n; ++i) cin >> items[i].first >> items[i].second; vector < vector < int > > dp(n + 1, vector < int >(W + 1, 0)); cout << top_down_dp(n, W, dp, items); return 0;
}

Kiểu bottom-up:

#include <bits/stdc++.h> using namespace std; void enter(int &n, int &W, vector < pair < int, int > > items)
{ cin >> n >> W; items.resize(n + 1); for (int i = 1; i <= n; ++i) cin >> items[i].first >> items[i].second;
} // Quy hoạch động.
void solution(int n, int W, vector < pair < int, int > > &items)
{ vector < vector < int > > dp(n + 1, vector < int >(W + 1, 0)); for (int i = 1; i <= n; ++i) for (int j = 0; j <= W; ++j) { dp[i][j] = dp[i - 1][j]; if (j >= items[i].first) dp[i][j] = max(dp[i][j], dp[i - 1][j - items[i].first] + items[i].second); } // In kết quả. cout << dp[n][W] << endl;
} main()
{ int n, W; vector < pair < int, int > > items; enter(n, W, items); solution(n, W, items); return 0;
}

3. Rút bài

Đề bài

Trên bàn có $n$ lá bài, trên mỗi lá bài có ghi một số nguyên dương. Các quân bài được xếp thành một chồng. Người ta lần lượt rút các lá bài bên trong chồng bài (tức là trừ lá bài trên cùng và dưới cùng), mỗi lần rút một quân cho đến khi chỉ còn lại lá trên cùng và dưới cùng. Chi phí để rút một lá bài là tích của ba số nguyên ghi trên lá bài được rút, lá bài ngay trên lá bài được rút và lá bài ngay dưới lá bài được rút. Đến khi rút hết $n-2$ lá bài ở giữa, ta có tổng chi phí rút bài. Mỗi trình tự rút bài khác nhau sẽ có tổng chi phí khác nhau.

Ví dụ: Với $n=5$ và số ghi trên các lá bài là $[10,1,50,20,5]$. Nếu lần lượt rút các lá bài có các số $1,20$ và $50$ thì tổng chi phí là:

$$10×1×5+50×20×5+10×50×5=8000$$

Còn nếu rút các lá bài với số $50,20$ và $1$ thì tổng chi phí sẽ là:

$$1×50×20+1×20×5+10×1×5=1150$$

Yêu cầu: Hãy tìm tổng chi phí nhỏ nhất khi rút hết $n-2$ lá bài?

Input:

• Dòng đầu tiên chứa số nguyên dương $n$ - số lá bài.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2,..., a_n$ - số ghi trên lá bài thứ $i$.

Ràng buộc:

• $1 \le n \le 100$.
• $1 \le a_i \le 1000; \forall i: 1 \le i \le n$.

Output:

• Số nguyên duy nhất là chi phí nhỏ nhất để rút hết $n - 2$ lá bài ở giữa.

Sample Input:

5
10 1 50 20 5

Sample Output:

1150

Ý tưởng

Đặt $dp[l][r]$ là tổng chi phí nhỏ nhất để rút hết các lá bài trong đoạn $[l, r],$ nhưng giữ lại hai lá ở vị trí $l$ và $r$.

Ta có công thức:

$$dp[l][r] = \text{min}\big(dp[l][k] + dp[k][r] + a_k \times a_l \times a_r\big)$$

(Do rút hết đoạn từ $l$ tới $k$ và đoạn từ $k$ tới $r,$ giữ lại $l, r$ và $k,$ sau đó lại rút nốt $k$ để giữ lại $l$ và $r$ thì sẽ thêm chi phí là $a_l \times a_k \times a_r$)

Cơ sở quy hoạch động sẽ là các $dp[i][i + 1] = 0$ và $dp[i][i] = 0$. Còn lại các giá trị $dp$ khác đều coi như bằng $\infty$ ban đầu.

Do bài toán này khá khó để xác định thứ tự cập nhật quy hoạch động, nên các bạn hãy ưu tiên sử dụng phương án đệ quy có nhớ hơn là quy hoạch động thông thường.

Kết quả cuối cùng là $dp[1][n]$.

Cài đặt

Kiểu top-down:

#include <bits/stdc++.h>
#define int long long using namespace std; const int maxn = 100 + 10, INFTY = 1e18; void enter(int &n, vector < int > &a)
{ cin >> n; a.resize(n + 1); for (int i = 1; i <= n; ++i) cin >> a[i];
} int top_down_dp(int l, int r, vector < vector < int > > &dp, vector < int > &a)
{ if (l + 1 == r || l >= r) return 0; if (dp[l][r] != INFTY) return dp[l][r]; for (int k = l + 1; k <= r - 1; ++k) { int t1 = top_down_dp(l, k, dp, a); int t2 = top_down_dp(k, r, dp, a); dp[l][r] = min(dp[l][r], t1 + t2 + a[k] * a[l] * a[r]); } return dp[l][r];
} void solution(int n, vector < int > &a)
{ vector < vector < int > > dp(n + 1, vector < int >(n + 1)); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) dp[i][j] = INFTY; cout << top_down_dp(1, n, dp, a);
} main()
{ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; vector < int > a; enter(n, a); solution(n, a); return 0;
}

Kiểu bottom-up:

#include <bits/stdc++.h>
#define int long long using namespace std; const int INFTY = 1e18; void enter(int &n, vector < int > &a)
{ cin >> n; a.resize(n + 1); for (int i = 1; i <= n; ++i) cin >> a[i];
} void solution(int n, vector < int > &a)
{ vector < vector < int > > dp(n + 1, vector < int >(n + 1, INFTY)); for (int i = 1; i <= n; ++i) { dp[i][i] = 0; if (i < n) dp[i][i + 1] = 0; } for (int r = 3; r <= n; ++r) for (int l = r - 2; l >= 1; --l) for (int k = l + 1; k < r; ++k) dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[r] * a[k]); cout << dp[1][n];
} main()
{ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; vector < int > a; enter(n, a); solution(n, a); return 0;
}

III. Tài liệu tham khảo

• https://inginious.org/course/competitive-programming/dp-topdown-bottomup
• https://stackoverflow.com/questions/34897484/when-to-use-bottom-up-dp-and-when-to-use-top-down-dp
• https://stackoverflow.com/questions/6164629/what-is-the-difference-between-bottom-up-and-top-down