Quy hoạch động cho người mới bắt đầu (Phần 5) – Sử dụng đệ quy có nhớ nâng cao

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 có kết quả tốt trong các cuộc thi.
Series Quy hoạch động cho người mới bắt đầu gồm 6 phần, chia ra làm hai hướng tiếp cận:

Sử dụng vòng lặp for – với cách tiếp cận Bottom-up
Sử dụng đệ quy có nhớ – với cách tiếp cận Top-down

Series quy hoạch động sẽ đi từ các ví dụ cơ bản đến nâng cao, quy hoạch động 1 chiều, 2 chiều. So sánh và đánh giá hai cách tiếp cận, để từ đó giúp các bạn có cái nhìn tổng quan về Quy hoạch động, hình thành tư duy, lối suy nghĩ khi gặp các bài toán về quy hoạch động.

Mục lục

1. Khi nào thì dùng quy hoạch động

Khi nào thì chúng ta cần đến quy hoạch động? Đó là một câu hỏi rất khó trả lời. Không có một công thức nào cho các bài toán như vậy.
Tuy nhiên, có một số tính chất của bài toán mà bạn có thể nghĩ đến quy hoạch động. Dưới đây là hai tính chất nổi bật nhất trong số chúng:

Bài toán có các bài toán con gối nhau (bài toán có công thức quy nạp giống trong toán học): Sử dụng kết quả của bài toán nhỏ để giải quyết bài toán lớn (bài toán chia để trị)
Bài toán có cấu trúc con tối ưu

2. Bài toán Đường đi có tổng lớn nhất

Link đề bài: Đường đi có tổng lớn nhất

Yêu cầu đề bài: Xác định cách để đi từ ô bất kỳ thuộc cột \(1\) đến ô bất kỳ thuộc cột \(n\) sao cho tổng các ô trên đường đi là lớn nhất.

Xác định các bước giải bài toán (làm ra nháp)

Bước 1: Xác định ý nghĩa hàm đệ quy

Gọi \(dp(i,j)\) là tổng đường đi lớn nhất khi đang đứng tại ô \((i,j)\)

Mảng \(F[i][j]\) lần này sẽ không khởi tạo bằng giá trị \(-1\) được nữa, do trên bảng xuất hiện cả những số âm, ta khởi tạo giá trị là \(-INF=-2e9\), là giá trị mà kết quả không bao giờ đạt được.

Bước 2: Xác định điều kiện dừng đệ quy

Nếu đang đứng tại ô nào đó tại cột \(n\), tức là \(j=n\), ta sẽ không đi nữa, kết quả trả về chính giá trị tại ô đang đứng
if \(j = n\) \(return\) \(a[i][j];\)
Nếu đi vào một ô nào đó nằm ngoài bảng, coi bước đi này là không hợp lệ, kết quả trả về \(-INF\)
if \((i\) < \(1 || i > m)\) \(return\) \(-1e9;\)

Bước 3: Xác định công thức tính

Ô \((i,j)\) sẽ đi tới được các ô: \((i-1,j+1), (i, j+1), (i+1, j+1)\). Vậy sẽ có 3 cách đi:

Cách 1: Đi từ ô \((i,j)\) đến ô \((i-1, j+1)\) : \(dp(i-1,j+1) + a[i][j]\)
Cách 2: Đi từ ô \((i,j)\) đến ô \((i, j+1)\): \(dp(i,j+1) + a[i][j]\)
Cách 3: Đi từ ô \((i,j)\) đến ô \((i+1, j+1)\): \(dp(i+1,j+1) + a[i][j]\)

Vậy ta có công thức: \(F[i][j] = max(dp(i-1,j+1), dp(i,j+1), dp(i+1,j+1)) + a[i][j] \)

Bước 4: Xác định kết quả nằm ở đâu?

Kết quả nằm ở: \(max(dp(i,1)\) với mọi \(i = 1 \rightarrow m\) – ô xuất phát là ô bất kỳ thuộc cột \(1\)

Code mẫu Đường đi có tổng lớn nhất C++

#include<bits/stdc++.h>
#define maxN 105
using namespace std;
const int INF = 1e9;

int n, m;
int a[maxN][maxN], f[maxN][maxN];


void enter()
{
	cin >> m >> n;
	for (int i =1; i <= m; i++){
		for (int j =1; j <= n; j++)
			cin >> a[i][j];
	}
}

int dp(int i, int j){
	if(i < 1 || i > m) return -INF;
	if (j == n) return a[i][j];
	if (f[i][j] != -2e9) return f[i][j];
	f[i][j] = max(max(dp(i - 1, j + 1), dp(i, j + 1)), dp(i + 1, j + 1)) + a[i][j];			
	return f[i][j];
}

int main(){
	enter();
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			f[i][j] = -2e9;
	
	int res = -INF;
	for (int i = 1; i <= m; i++)
		res = max(res, dp(i,1));
	cout<<res;
}

3. Bài toán cái túi – Knapsack

Link đề bài: Atcoder Educational DP Contest D – Knapsack 1
Yêu cầu đề bài: Xác định cách lấy các đồ vật sao cho tổng trọng lượng các đồ vật không quá \(W\) và giá trị của các đồ vật là lớn nhất.

Xác định các bước giải bài toán

Bước 1: Xác định ý nghĩa hàm đệ quy

Gọi \(dp(i, t)\) là tổng giá trị lớn nhất thu được khi đang xét đồ vật \(i\), tổng trọng lượng các đồ vật đã lấy là \(t\), các đồ vật từ \(1\) tới \(i-1\) đã xét chọn/không chọn rồi.
Mảng \(F\) được khởi tạo giá trị \(-1\) – do giá trị các đồ vật đều dương, cùng lắm ta không chọn được đồ vật nào thì tổng giá trị bằng \(0\)

Bước 2: Xác định điều kiện dừng đệ quy
Nếu \(i > n\) \(return\) \(0\), đã xét hết các đồ vật từ \(1\) tới \(n\) thì dừng việc lấy.

Bạn tưởng tượng như các đồ vật đang được xếp trên một chiếc bàn dài, bạn di chuyển lần lượt từ trái qua phải, đi tới đồ vật nào thì sẽ phải đưa ra quyết định: chọn/không chọn đồ vật đó để cho vào túi. Cho đến khi đi hết chiếc bàn là kết thúc

Bước 3: Xác định công thức tính
Khi xét đến đồ vật thứ \(i\), ta có hai trường hợp:

Trường hợp 1: Không chọn đồ vật \(i\):
Nếu không chọn đồ vật này, trọng lượng vẫn là \(t\), xét đồ vật tiếp theo: \(dp(i+1,t)\)
Trường hợp 2: Chọn đồ vật \(i\) – Điều kiện là \(t+w[i] \leq W\)
Chọn đồ vật này, trọng lượng chiếc túi đang là \(t\) sẽ biến thành \(t + w[i]\), giá trị được tăng thêm \(v[i]\): \(dp(i+1, t+w[i]) + v[i]\)

Vậy ta có công thức: \(dp(i,t)=\left\{\begin{matrix}
dp(i+1,t)& \text{nếu } t+w[i]>W\\
max(dp(i+1, t), dp(i+1, t+w[i]) + v[i])& \text{nếu } t+w[i] \leq W&
\end{matrix}\right.\)

Bước 4: Xác định kết quả nằm ở đâu?

Kết quả nằm ở: \(dp(1,0)\) – Xét bắt đầu từ đồ vật \(1\), ban đầu chiếc túi có trọng lượng là \(0\).

Code mẫu Bài toán cái túi – Knapsack C++

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define MAXN 105
#define MAXW 100005
int n, W;
ll w[MAXN],v[MAXN];
ll f[MAXN][MAXW];

ll dp(int i, int t){
	if (i > n) return 0;
	if (f[i][t] != -1) return f[i][t];
	f[i][t] = dp(i+1, t);
	if (t + w[i] <= W)
		f[i][t] = max (f[i][t], dp(i + 1, t + w[i]) + v[i]);
	return f[i][t];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
	cin >> n >> W;
	for(int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	memset(f, -1, sizeof(f));
	cout<<dp(1,0);
	return 0;
}

4. Bài toán Xâu con chung dài nhất

Link đề bài: Atcoder Educational DP Contest F – LCS
Yêu cầu đề bài: Xác định xâu con chung (không liên tiếp) dài nhất của hai xâu \(s\) và \(t\) cho trước.

Bài tập này yêu cầu truy vết kết quả. Tuy nhiên ở bài viết này sẽ chỉ đề cập đến việc tìm độ dài xâu con chung dài nhất trước, sau khi tìm được độ dài dài nhất rồi ta sẽ sử dụng kết quả của mảng quy hoạch động để tìm ra xâu con chung dài nhất đó. Các bạn có thể xem thêm tại phần 6 của series nhé: Quy hoạch động cho người mới bắt đầu (Phần 6) – Sử dụng đệ quy có nhớ truy vết

Xác định các bước giải bài toán

Bước 0: Khởi tạo bài toán

Gọi \(n\) là độ dài của xâu \(s\)
Gọi \(m\) là độ dài của xâu \(t\)
Để việc xử lý cho tiện, ta sẽ thêm một ký tự # ở đầu mỗi xâu, khi đó ký tự bắt đầu của một xâu là 1.

Bước 1: Xác định ý nghĩa hàm đệ quy

Gọi \(dp(i,j)\) là độ dài xâu con chung dài nhất khi đang xét đến vị trí \(i\) của xâu \(s\) và vị trí \(j\) của xâu \(t\)
Mảng \(F\) được khởi tạo giá trị \(-1\)

Bước 2: Xác định điều kiện dừng đệ quy
Nếu \(i\) hoặc \(j\) lớn hơn độ dài xâu \(s\) và \(t\) tương ứng, nghĩa là từ đây không thể trùng được nữa. Kết quả trả về 0.

Bước 3: Xác định công thức truy hồi
Khi xét vị trí \(i\) của xâu \(s\) và vị trí \(j\) của xâu \(t\), ta có hai trường hợp:

Trường hợp 1: \(s[i] = t[j]\)
Hai xâu sẽ trùng nhau ký tự \(s[i]\). Vậy ta xét tiếp vị trí \(i + 1\) và \(j + 1\): \(dp(i,j) = dp(i+1,j+1) + 1\)
Trường hợp 2: \(s[i] \neq t[j]\): Một trong hai ký tự sẽ không thuộc xâu con chung: \(dp(i,j) = max(dp(i+1,j), dp(i,j+1))\)

Vậy ta có công thức: \(dp(i,j)=\left\{\begin{matrix}
dp(i+1,j+1) + 1 & \text{nếu } s[i] = t[j]\\
max(dp(i+1,j), dp(i,j+1))& \text{nếu } s[i] \neq t[j]&
\end{matrix}\right.\)

Bước 4: Xác định kết quả nằm ở đâu?

Kết quả nằm ở: \(dp(1,1)\) – xét bắt đầu từ các ký tự đầu tiên của hai xâu.

Code mẫu Bài toán Xâu con chung dài nhất C++

#include <bits/stdc++.h>
using namespace std;

#define MAXN 3005

int n, m, f[MAXN][MAXN];
string s, t;
int dp(int i, int j){
	if (i > n || j > m) return 0;
	if (f[i][j] != -1) return f[i][j];
	if (s[i] == t[j])
		f[i][j] = dp(i + 1, j + 1) + 1;
	else 
		f[i][j] = max(dp(i + 1, j), dp(i, j + 1));
	return f[i][j];
}
int main() {
	cin >> s >> t;
	n = s.size();
	m = t.size();
	s = "#" + s;
	t = "#" + t;
	memset(f, -1, sizeof(f));
	cout << dp(1, 1);
	return 0;
}

5. Bài toán Dãy con tăng dài nhất

Link đề bài: Dãy con tăng dài nhất (bản dễ)
Yêu cầu đề bài: Xác định dãy con tăng (không liên tiếp) dài nhất của dãy \(a\).

Xác định các bước giải bài toán

Bước 1: Xác định ý nghĩa hàm đệ quy

Gọi \(dp(i, j)\) là độ dài dãy con tăng dài nhất khi xét đến phần tử thứ \(i\), phần tử cuối cùng trong dãy con tăng đã kết nạp là phần từ \(j\)
Mảng \(F\) được khởi tạo giá trị \(-1\)

Bước 2: Xác định bài toán con
Nếu \(i > n \), ta đã xét hết các phần tử, kết quả trả về 0.

Bước 3: Xác định công thức truy hồi
Khi xét đến phần tử thứ \(i\), ta có hai trường hợp:

Trường hợp 1: Không kết nạp phần tử \(i\) vào dãy con tăng, phần tử tiếp theo cần xét là phần tử i+1, phần tử cuối cùng trong dãy con tăng vẫn là phần tử \(j\): \(dp(i+1, j)\)
Trường hợp 2: Kết nạp phần tử \(i\) vào dãy con tăng – xét điều kiện \(a[i] > a[j]\), lúc đó phần tử cuối cùng trong dãy con tăng sẽ là phần tử \(i\): \(dp(i+1, i) + 1\)

Vậy ta có công thức: \(dp(i,j)=\left\{\begin{matrix}
dp(i+1,j) & \text{nếu } a[i] \leq a[j]\\
max(dp(i+1,j), dp(i+1,i)+1)& \text{nếu } a[i] > a[j]&
\end{matrix}\right.\)

Bước 4: Xác định kết quả nằm ở đâu?

Kết quả nằm ở: \(dp(1,0)\), xét phần tử đầu tiên, lưu ý khởi tạo phần tử \(0\) của mảng là \(-INF\) để bất kỳ số nào cũng có thể là số đầu tiên trong dãy con tăng.

Code mẫu Bài toán Dãy con tăng dài nhất (bản dễ) C++

#include <bits/stdc++.h>
using namespace std;

#define MAXN 1005

int n, a[MAXN], f[MAXN][MAXN];
int dp (int i, int j){
	if (i > n) return 0;
	if (f[i][j] != -1) return f[i][j];
	f[i][j] = dp(i+1, j);
	if (a[i]>a[j])
		f[i][j] = max(f[i][j], dp(i+1, i) + 1);
	return f[i][j];
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	a[0] = -1e9;
	memset(f, -1, sizeof(f));
	cout<<dp(1,0);
	return 0;
}

6. Tổng kết

Các bài toán giải quyết bằng Quy hoạch động sử dụng đệ quy có nhớ với cách tiếp cận Top-down, mỗi bài toán sẽ được tính duy nhất 1 lần.

Độ phức tạp của thuật toán quy hoạch động được tính bằng công thức:

Số bài toán * Chi phí chuyển trạng thái

Trong đó:

Số bài toán: là số phần tử trong mảng \(F\)
Chi phí chuyển trạng thái: Độ phức tạp khi triển khai công thức tính mỗi bài toán.

Ví dụ:

Độ phức tạp của bài toán Đường đi có tổng lớn nhất là \(O(m*n*3\)), \(m*n\) bài toán, mỗi bài toán mất 3 phép tính để triển khai công thức (lấy max của 3 cách đi).
Độ phức tạp của bài toán Cái túi – Knapsack là \(O(n*W*2), n*W\) bài toán, mỗi bài toán mất 2 phép tính để triển khai công thức (2 phép tính tìm max của 2 cách)
Độ phức tạp của bài toán Xâu con chung dài nhất là \(O(m*n)\)
Độ phức tạp của bài toán Dãy con tăng dài nhất là \(O(n*n)\), \(n\) bài toán con, mỗi bài toán con mất \(n\) phép tính để thực hiện công thức

Nhận xét

Khi triển khai bằng cách tiếp cận này, các bạn sẽ không cần phải suy nghĩ xem nên thực hiện bài toán nào trước, bài toán nào sau. Vì bài toán nào chưa được tính thì hàm đệ quy sẽ đi tính nó. Vậy ta có thể nói, tất cả các bài toán quy hoạch động đều có thể giải quyết bằng đệ quy có nhớ được, nhưng chưa chắc đã giải quyết được bằng cách sử dụng vòng lặp for.
Không cần khởi tạo nhiều tham số lằng nhằng, vì mọi điều kiện của bài toán đều có thể được kiểm soát trong khi triển khai công thức và điều kiện dừng đệ quy
Tư duy thuật toán theo cách này cũng thuận với thực tế và đề bài.

Xem thêm các bài trong Series Quy hoạch động cho người mới bắt đầu:

7. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn