Quy hoạch động cho người mới bắt đầu (Phần 2) – Sử dụng vòng lặp for nâng cao

Đỗ Thị Hồng Ngát 11/10/2023
11
Th10

Quy hoạch động cho người mới bắt đầu (Phần 2) – Sử dụng vòng lặp for 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.

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 mảng F

  • Gọi \(F[i][j]\) là tổng đường đi lớn nhất khi đi từ ô nào đó thuộc cột \(1\) đến ô \((i,j)\)
  • Kích thước mảng \(F\) là \(m*n\), mảng \(F\) có 2 chiều, tương ứng hàng và cột.

Bước 2: Xác định bài toán con
Ta thấy một ô \((i,j)\) bất kỳ sẽ được đi tới bởi các ô: \((i-1,j-1), (i, j-1), (i+1, j-1)\)
quy hoạch động

Để tránh việc phải kiểm tra xem các ô nhảy trước đó có nằm ngoài bảng hay không, ta khởi tạo các hàng \(0, m+1\) và cột \(0\) của mảng \(F\).

  • \(F[0][j] = -INF\) với mọi \(j = 0 \rightarrow n\) (Các ô nằm ở hàng \(0\) của bảng sẽ không được đi tới, do nằm ngoài bảng nên cần khởi tạo bằng một giá trị cực nhỏ, để khi ta lấy giá trị lớn nhất trong các trường hợp thì tổng này sẽ không bao giờ là số lớn nhất)
  • \(F[m+1][j] = -INF\) với mọi \(j = 0 \rightarrow n\) (Tương tự, các ô nằm ở hàng \(m+1\) của bảng sẽ không được đi tới, do nằm ngoài bảng nên cần khởi tạo bằng một giá trị cực nhỏ, để khi ta lấy giá trị lớn nhất trong các trường hợp thì tổng này sẽ không bao giờ là số lớn nhất)
  • \(F[i][0] = 0\) với mọi \(i = 0 \rightarrow m\) (Vì có thể xuất phát ở một ô bất kỳ thuộc cột \(1\), các ô nằm ở cột \(0\) của bảng sẽ được gán bằng \(0\) để khi tính giá trị \(F\) bất kỳ ô nào thuộc cột \(1\), chúng sẽ đều có giá trị bằng giá trị chính giá trị trên bảng của ô đó (do max của 3 ô phía trước là \(0\)))

Lưu ý: giá trị \(INF\) đủ lớn để khi tính tổng lại đảm bảo rằng kết quả không lấy max vào trường hợp đó, và khi cộng cũng không bị tràn số. Ở đây ta nên để \(INF = 10^9\).
Bước 3: Xác định công thức truy hồi
Ô \((i,j)\) sẽ được đi tới bởi 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-1, j-1)\) đến ô \((i,j)\): \(F[i-1][j-1] + a[i][j]\)
  • Cách 2: Đi từ ô \((i, j-1)\) đến ô \((i,j)\): \(F[i][j-1] + a[i][j]\)
  • Cách 3: Đi từ ô \((i+1, j-1)\) đến ô \((i,j)\): \(F[i+1][j-1] + a[i][j]\)

Vậy ta có công thức: \(F[i][j] = max(F[i-1][j-1], F[i][j-1], F[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(F[i][n]\) với mọi \(i = 1 \rightarrow m\) (ô kết thúc là ô bất kỳ thuộc cột \(n\))

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];
	}
}

void solve(){
	for (int i = 0; i <= m; i++)
		f[i][0] = 0;
	for (int i =0; i <= n; i++)
		f[0][i] = -INF;
	for (int i =0; i <= n; i++)
		f[m+1][i] = -INF;
	for (int j = 1; j <=n; j++){
		for (int i =1; i <= m; i++)
			f[i][j] = max(max(f[i-1][j-1], f[i][j-1]), f[i+1][j-1]) + a[i][j];			
	}
	int res = -INF;
	for (int i = 1; i <=m; i++)
		res = max(res, f[i][n]);
	cout<<res;
}

int main(){
	enter();
	solve();
}

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 (làm ra nháp)

Bước 1: Xác định ý nghĩa mảng F

  • Gọi \(F[i][t]\) là tổng giá trị lớn nhất thu được khi xét những đồ vật từ \(1\) tới \(i\), tổng trọng lượng các đồ vật đã lấy là \(t\)
  • Kích thước mảng \(F\) là \(n*W\), mảng \(F\) có 2 chiều, tương ứng hàng và cột.

Bước 2: Xác định bài toán con

  • \(F[0][0] = 0\) (Không xét đồ vật nào, thì trọng lượng là \(0\) và khi đó tổng giá trị thu được cũng là \(0\))
  • \(F[0][t] = -INF\) với mọi \(t = 1 \rightarrow W\) (Không xét đồ vật nào, mà \( t \geq 1\), thì trường hợp này là vô lý, không xảy ra nên ta khởi tạo giá trị thu được là \(INF\) để khi lấy kết quả không lấy \(max\) vào trường hợp này)

Lưu ý: giá trị \(INF\) đủ lớn để khi tính tổng lại đảm bảo rằng kết quả không lấy max vào trường hợp đó, và khi cộng cũng không bị tràn số. Ở đây ta nên để \(INF = 10^{15}\).

Bước 3: Xác định công thức truy hồi
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\):
    => Để trọng lượng các đồ vật là \(t\), ta cần chọn các đồ vật từ \(1\) tới \(i-1\) sao cho trọng lượng vẫn là \(t\), mà giá trị của chúng là lớn nhất
    => Đây chính là \(F[i-1][t]\)
  • Trường hợp 2: Chọn đồ vật \(i\) – Điều kiện là \(t \geq w[i]\)
    => Để trọng lượng các đồ vật là \(t\), ta cần chọn các đồ vật từ \(1\) tới \(i-1\) sao cho trọng lượng là \(t-w[i]\), mà giá trị của chúng là lớn nhất
    => Đây chính là \(F[i-1][t-w[i]]\), cộng thêm giá trị của đồ vật \(i\) là \(v[i]\) nữa
    => Ta được tổng giá trị là: \(F[i-1][t-w[i]] + v[i]\)

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

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

Kết quả nằm ở: \(max(F[n][t]\) với mọi \(t = 0 \rightarrow W\) (Chọn các vật từ \(1\) đến \(n\), tổng giá trị là \(t\) không vượt quá \(W\))

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
#define INF 1e15
int n, W, w[MAXN],v[MAXN];
ll f[MAXN][MAXW];

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];
	
	f[0][0] = 0;
	for(int t = 1; t <= W; t++) 
		f[0][t] = -INF;
	
	for(int i = 1; i <= n; i++)
		for(int t = 0; t <= W; t++) {
			f[i][t] = f[i-1][t];
			if(t-w[i]>=0) f[i][t] = max(f[i][t],f[i-1][t-w[i]] + v[i]);
		}

	ll res = -INF;
	for(int t = 0; t <= W; t++) 
		res = max(res, f[n][t]);
	cout<<res;
	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 3 của series nhé: Quy hoạch động cho người mới bắt đầu (Phần 3) – Sử dụng vòng lặp for truy vết

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

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 mảng F

  • Gọi \(F[i][j]\) là độ dài xâu con chung dài nhất của xâu \(s(1..i)\) và \(t(1..m)\)
  • Kích thước mảng \(F\) là \(n*m\), mảng \(F\) có 2 chiều.

Bước 2: Xác định bài toán con

  • \(F[0][j] = 0\) (Xâu con chung của \(s(1..0)\) và \(t(1..j)\) là \(0\))
  • \(F[i][0] = 0\) (Xâu con chung của \(s(1..i)\) và \(t(1..0)\) là \(0\))

Lưu ý: Nếu khai báo mảng \(F\) là biến global thì cả mảng \(F\) đã được khởi tạo mặc đinh là \(0\), nên không cần phải khởi tạo lại.
Bước 3: Xác định công thức truy hồi
Khi xét xâu \(s(1..i)\) và \(t(1..j)\), ta có hai trường hợp:

  • Trường hợp 1: \(s[i] = t[j]\)
    => Ký tự cuối cùng của mỗi xâu sẽ chính là ký tự chung của hai xâu \(s\) và \(t\). Vậy ta chỉ cần cộng thêm với độ dài xâu con chung dài nhất của \(s(1..i-1)\) và \(t(1..j-1)\) là xong.
    => \(F[i][j] = F[i-1][j-1] + 1\)
  • Trường hợp 2: \(s[i] \neq t[j]\):
    => Hai ký tự cuối của hai xâu khác nhau, nên ta có thể xác định được luôn là một trong hai ký tự này sẽ không thể nằm trong xâu con chung của chúng được.

    • Nếu ký tự \(s[i]\) không thuộc xâu con chung, thì kết quả sẽ là xâu con chung của hai xâu \(s(1..i-1)\) và \(t(1..j)\): \(F[i-1][j]\)
    • Nếu ký tự \(t[j]\) không thuộc xâu con chung, thì kết quả sẽ là xâu con chung của hai xâu \(s(1..i)\) và \(t(1..j-1)\): F[i][j-1]\)

    => \(F[i][j] = max(F[i-1][j], F[i][j-1])\)

Vậy ta có công thức: \(F[i][j]=\left\{\begin{matrix}
F[i-1][j-1] + 1 & \text{nếu } s[i] = t[j]\\
max(F[i-1][j], F[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 ở: \(F[n][m]\)

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 main() {
	cin >> s >> t;
	n = s.size();
	m = t.size();
	s = "#" + s;
	t = "#" + t;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if (s[i] == t[j])
				f[i][j] = f[i-1][j-1] + 1;
			else
				f[i][j] = max(f[i-1][j], f[i][j-1]);
		}
	}
	cout<<f[n][m];
	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 (làm ra nháp)

Bước 1: Xác định ý nghĩa mảng F

  • Gọi \(F[i]\) là độ dài dãy con tăng dài nhất mà phần tử cuối cùng của dãy con tăng là phần tử \(A[i]\)
  • Kích thước mảng \(F\) là \(n\), mảng \(F\) có 1 chiều.

Bước 2: Xác định bài toán con

  • \(F[0] = 0\) (Độ dài dãy con kết thúc tại phần tử \(0\) là \(0\))
  • \(F[1] = 1\) (Độ dài dãy con kết thúc tại phần tử \(1\) là \(1\) vì dãy chỉ có duy nhất \(1\) phần tử)

Bước 3: Xác định công thức truy hồi
quy hoạch động
Khi xét đến phần tử thứ \(i\), nếu coi phần tử thứ \(i\) là phần tử cuối cùng trong dãy con tăng, vậy ta cần tìm một vị trí \( j < i \) làm phần tử gần cuối, vị trí \(j\) này phải thoả mãn:

  • \(j < i\)
  • \(A[j] < A[i]\)
  • \(F[j]\) lớn nhất (độ dài dãy con tăng kết thúc tại \(j\) lớn nhất có thể)

Ví dụ như hình bên trên, có 3 vị trí \(j_1, j_2, j_3\) thoả mãn điều kiện \(j < i\) và \(A[j] < A[i]\)

  • nếu chọn \(j_1\) làm vị trí của phần tử gần cuối trong dãy ta được dãy có độ dài \(3\) (\(F[j_1] = 2\))
  • nếu chọn \(j_2, j_3\) làm vị trí của phần tử gần cuối trong dãy ta được dãy có độ dài \(2\) (\(F[j_2] = F[j_3] = 1\))

Vậy ta có công thức: \( F[i]=max(F[j])+1\), trong đó \(j =1..i-1\) và \(A[j] < A[i] \)

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

Kết quả nằm ở: \(max(F[i])\), vì dãy con tăng dài nhất có thể kết thúc ở bất cứ phần tử nào trong dãy

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];
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	f[1] = 1;
	for(int i = 1; i <= n; i++){
		f[i] = 1;
		for(int j = 1; j <= i-1; j++){
			if (a[j] < a[i])
				f[i] = max(f[i], f[j] + 1);
		}
	}
	int res = 1;
	for(int i = 1; i <= n; i++){
		res = max( res, f[i]);
	}
	cout<<res;
	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 vòng lặp for với cách tiếp cận Bottom-up, thứ tự thực hiện tính toán các bài toán sẽ là: Tính trước các bài toán con, rồi sau đó sử dụng kết quả của những bài toán này để tính lên cho các bài toán lớn hơn. Vậy 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

Khi triển khai bằng cách tiếp cận này, các bạn sẽ 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. Hay nói cách khác là suy nghĩ xem for từ đâu đến đâu.

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

Unable to display PDF file. Download instead. 

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *