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

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 Fibonacci

Ta có công thức truy hồi của số Fibonacci: \(F[n] = F[n-1] + F[n-2]\)

Dễ thấy, bài toán tính số Fibonacci thứ n thuộc lớp bài toán có các bài toán con gối nhau. Sử dụng kết quả của bài toán nhỏ để giải quyết bài toán lớn (Sử dụng \(F[n-1]\) và \(F[n-2]\) để tính \(F[n]\))

Đây là phương pháp Bottom-up, tất cả các bài toán con có thể cần đến đều được giải trước (từ bài toán cơ sở trở đi) , sau đó được dùng để xây dựng lời giải cho các bài toán lớn hơn.
Cách tiếp cận này cho ta thấy rõ độ phức tạp của thuật toán quy hoạch động : một vòng for \(O(n)\). Ở đây ta thực hiện chuẩn bị sẵn các bài toán đã tính được : đầu tiên là \(F[1]\) và \(F[2]\) sau đó sẽ lần lượt tính các \(F[3] -> F[4]\) … và cuối cùng sẽ được \(F[n]\) là kết quả bài toán.
Thuật toán cũng có thể cài đặt đơn giản bằng vòng for như thế này, vẫn đảm bảo mỗi bài toán được tính 1 lần và sử dụng kết quả của bài toán nhỏ để giải quyết bài toán lớn.

Code Fibonacci C++

 
int F[100];
int Fibonacci(int n){
      F[1] = 1; 
      F[2] = 1;
      for(int i = 3; i <= n; i++)
          F[i] = F[i-1] + F[i-2];
      return F[n];
}

3. Các bước để làm một bài toán quy hoạch động

Bước 1: Xác định mảng F (kích thước, số chiều của mảng, ý nghĩa)

Gọi \(F[n]\) là giá trị của số fibonacci thứ \(n\).
Mảng \(F\) có độ dài n

Bước 2: Xác định các bài toán con
Xác định các bài toán mà mình có thể dễ dàng nhận ra được, hay những trường hợp biên, là những bài toán có thể dễ dàng tính được và có thể đặt làm bài toán nhỏ nhất để tính dần lên

\(F[1] = 1\)
\(F[2] = 1\)

Bước 3: Xác định công thức truy hồi

\(F[n] = F[n-1] + F[n-2]\)

Bước 4: Xác định kết quả nằm ở đâu?
Kết quả nằm ở \(F[n]\) (là giá trị số fibonacci thứ \(n\) )

Khi mới học nên nháp cẩn thận 4 bước này ra nháp trước khi làm bài, sau đó mới code

4. Bài toán Frog 1 VNOJ

Link đề bài: Atcoder Educational DP Contest A – Frog 1

Yêu cầu đề bài: Xác định cách để chú ếch nhảy từ hòn đá \(1\) đến hòn đá \(n\) sao cho chi phi phí là nhỏ nhất

Nhận thấy đây là một bài toán về tối ưu, ta thử dùng quy hoạch động xem sao nhé.

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

Bước này giống hệt như hồi cấp 2 học giải bài toán có lời văn, đề bài hỏi cái gì thì mình đặt ẩn cái đó.

Gọi \(F[i]\) là chi phí nhỏ nhất để chú ếch nhảy từ hòn đá \(1\) đến hòn đá \(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[1] = 0\) (Ban đầu chú ếch đang đứng tại hòn đá 1 nên ta không mất chi phí nào để nhảy từ hòn đá \(1\) đến hòn đá \(1\) nữa)
\(F[2] = abs(h[2]-h[1])\) (Nếu chỉ có hai hòn đá thì chú ếch chỉ có duy nhất 1 cách là nhảy trực tiếp từ hòn đá \(1\) đến hòn đá \(2\))

Bước 3: Xác định công thức truy hồi

Để chú ếch đứng tại hòn đá thứ \(i\) thì nó sẽ có 2 cách nhảy:

Cách 1: Nhảy từ hòn đá \(i-1\) đến hòn đá \(i\):
=> Chi phí nhỏ nhất để nhảy từ \(1\) đến \(i\) = (Chi phí nhỏ nhất để nhảy từ \(1\) đến \(i – 1\)) + (Chi phí nhảy từ \(i-1\) đến \(i\))
=> Chi phí để nhảy từ \(1\) đến \(i\) là:
\(F[i-1] + abs(h[i]-h[i-1])\)
Cách 2: Nhảy từ hòn đá \(i-2\) đến hòn đá \(i\):
Chi phí để nhảy từ \(1\) đến \(i\) tương tự là:
\(F[i-2] + abs(h[i]-h[i-2])\)

Vậy ta có công thức: \(F[i] = min(F[i-1] + abs(h[i]-h[i-1]), F[i-2] + abs(h[i]-h[i-2]))\)

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

Bước này thì xem lại ý nghĩa mảng \(F\) và đề bài hỏi gì? đôi khi mình sẽ đặt ý nghĩa mảng \(F\) khác với cái đề bài hỏi một chút

Kết quả nằm ở: \(F[n]\) – chi phí để nhảy từ hòn đá \(1\) đến hòn đá \(n\)

Code mẫu Frog 1 C++

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int,int>
#define MAXN 100005
int n, h[MAXN], f[MAXN];
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++) 
		cin >> h[i];
 
	f[1] = 0;
	f[2] = abs(h[2] - h[1]);
	for(int i = 3; i <= n; i++){
	   f[i] = min(f[i-1] + abs(h[i] - h[i-1]), f[i-2] + abs(h[i] - h[i-2]));
	}
	cout << f[n];
	return 0;
}

5. Bài toán Xếp hàng mua vé

Link đề bài: Xếp hàng mua vé

Yêu cầu đề bài: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ 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]\) là thời gian nhỏ nhất để người thứ \(1\) đến người thứ \(i\) có thể mua vé
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

Nếu chỉ có \(1\) người mua vé thì thời gian để người đó mua là \(T[1]\), \(F[1]=T[1]\)
Nếu chỉ có \(2\) người mua vé thì mình sẽ có \(2\) cách mua:
- Cách \(1\): \(2\) người tự mua vé mất số thời gian là \(T[1] + T[2]\)
- Cách \(2\): người \(1\) mua vé cho cả hai người \(1\) và \(2\), mất thời gian là \(R[1]\)
- Vì ta đang cần tìm thời gian nhỏ nhất nên sẽ chọn cách nào cho ra kết quả nhỏ nhất: \(F[2] = min(T[1] + T[2], R[1])\)

Bước 3: Xác định công thức truy hồi
Xác định được bài toán con thì đến đây có thể dễ dàng tìm được công thức. Các cách để người thứ \(i\) mua vé:

Nếu người \(i\) tự mua vé của mình ta sẽ mất thời gian là: \(F[i-1] + T[i]\)
Nếu người \(i\) nhờ người \(i-1\) mua vé hộ, ta sẽ mất thời gian là: \(F[i-2] + R[i-1]\)

Vậy ta có công thức: \(F[i] = min(F[i-1]+T[i], F[i-2] + R[i-1])\)

Bước 4: Xác định kết quả nằm ở đâu?
Kết quả nằm ở: \(F[n]\) – Thời gian mua vé cho người từ \(1\) tới \(n\)

Code mẫu Xếp hàng mua vé C++

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

int n, t[MAXN], r[MAXN], f[MAXN];

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) 
		cin >> t[i];
	for(int i = 1; i<n; i++) 
		cin>>r[i];
	f[1] = t[1];
	f[2] = min(t[1]+t[2],r[1]);
	for(int i = 3; i <= n; i++)
		f[i] = min(f[i-1] + t[i], f[i-2] + r[i-1]);
	cout << f[n];
	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 Fibonacci là \(O(n)*1=O(n)\), \(n\) bài toán, mỗi bài toán mất 1 phép tính để triển khai công thức.
Độ phức tạp của bài toán Frog 1 là \(O(n)*3, 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 (2 phép tính lấy tổng, tìm max của 2 tổng)
Độ phức tạp của bài toán Xếp hàng mua vé là \(O(n)\)

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