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

Đỗ Thị Hồng Ngát 17/11/2023
17
Th11

Quy hoạch động cho người mới bắt đầu (Phần 4) – Sử dụng đệ quy có nhớ 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.

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]\)

Code Fibonacci sử dụng đệ quy

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

Hình sau mô tả hàm đệ quy Fibonacci khi n=5
quy hoạch động

Nhận xét

Khi tính \(F[5]\) ta cần tính \(F[4]\) 1 lần, \(F[3]\) 2 lần, \(F[2]\) 3 lần, \(F[1]\) 2 lần

=> Thuật toán đệ quy tính đi tính lại 1 bài toán nhiều lần (mặc dù kết quả bài toán không thay đổi trong suốt thời gian chạy trương trình), gây tốn thời gian và không hiệu quả.

Giải pháp

Ta lưu lại kết quả của mỗi bài toán sau mỗi lần tính, khi gặp lại bài toán đó, kiểm tra nếu bài toán đã được tính thì mình sẽ trả về kết quả đã lưu, nếu không thì mình sẽ đi tính nó.
=> Mỗi bài toán được tính duy nhất 1 lần và sử dụng kết quả để tính cho các bài toán khác
=> Cách làm này được gọi là Quy hoạch động và cài đặt bằng phương pháp “đệ quy có nhớ”. Đệ quy là sử dụng hàm đệ quy để tính kết quả (như trên). Có nhớ là lưu lại kết quả của bài toán vào mảng để không cần tính lại nữa

Code Fibonacci sử dụng đệ quy có nhớ

//Khai báo mảng F để lưu giá trị của số fibonacci thứ n.
//Mặc định các phần tử của mảng F được khởi tạo là 0
int F[100];

int Fibonacci(int n)
{
    if (n == 1 || n == 2)
        return 1;
    //Kiểm tra xem F[n] đã được tính hay chưa? F[n]==0 thì là chưa được tính, != là đã tính
    if(F[n] != 0) return F[n];
    //Nếu F[n] chưa được tính thì đi tính nó và lưu lại
    F[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
    return F[n];
}

Minh hoạ thuật toán khi chạy bằng đệ quy có nhớ

  • Đầu tiên muốn tính \(Fibonacci(5)\), ta cần đi tính \(Fibonacci(4)\) và \(Fibonacci(3)\), hàm đệ quy sẽ đi xuống tính \(Fibonacci(4)\) trước
  • Tại \(Fibonacci(4)\), muốn tính ta lại cần biết kết quả của \(Fibonacci(3)\) và \(Fibonacci(2)\), đệ quy xuống \(Fibonacci(3)\)
  • \(Fibonacci(3)\) lại chạy xuống tính \(Fibonacci(2)\) và \(Fibonacci(1)\)
  • \(Fibonacci(2)\) rơi vào điều kiện dừng đệ quy, trả về kết quả 1.
  • Hàm đệ quy quay lại và đi tính \(Fibonacci(1)\), rơi vào điều kiện dừng đệ quy, trả về kết quả 1.
  • Hàm đệ quy quay lại \(Fibonacci(3)\), tổng hợp kết quả của \(Fibonacci(2)\) và \(Fibonacci(1)\) vừa được tính và trả về kết quả 2.
  • Tương tự, hàm đệ quy quay lại \(Fibonacci(4)\), tiếp tục đi tính \(Fibonacci(2)\). Sau đó tổng hợp kết quả cho \(Fibonacci(4)\) từ \(Fibonacci(3)\) và \(Fibonacci(2)\). Trả về kết qủa 3.
  • Hàm đệ quy quay lại \(Fibonacci(5)\), tiếp tục đi tính \(Fibonacci(3)\). Bài toán này đã được tính nên trả về kết qủa 2 luôn mà không cần đệ quy xuông dưới nữa.Sau đó tổng hợp kết quả cho \(Fibonacci(5)\) từ \(Fibonacci(4)\) và \(Fibonacci(3)\). Trả về kết qủa 5.

3. Cách chuyển từ nháp sang code đệ quy có nhớ

Khi mới học nên nháp cẩn thận 4 bước bước để làm một bài toán quy hoạch động ra nháp trước khi làm bài, sau đó mới code. Các bước làm bạn có thể tham khảo lại ở blog 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

Bước 1: Khai báo và khởi tạo mảng F: Kích thước, số chiều mảng F sẽ tương ứng với số tham số mình đặt ý nghĩa trong hàm đệ quy.

Bước 2: Khởi tạo giá trị của mảng F: vì các giá trị này thể hiện là bài toán đã được tính hay chưa => tùy vào đề bài mình sẽ khởi tạo cho nó bằng 1 giá trị mà bạn nghĩ là không bao giờ có thể xuất hiện ở kết quả (vì khởi tạo vậy mới phân biệt được)

Ví dụ: Ta thấy số Fibonacci luôn không âm nên ta có thể khởi tạo mảng F là một số âm nào đó, ví dụ như số \(-1\). Để khởi tạo các giá trị trong mảng F với giá trị \(-1\) ta gọi lệnh \(memset(F,255,sizeof(F))\)
Bước 3: Triển khai code

//Tham số của hàm đệ quy sẽ giống với các chiều của mảng F
int Fibonacci(int n)
{
    //1.Các bài toán con sẽ được viết đầu tiên để điều khiển tính dừng của hàm đệ quy
    if (n == 1 || n == 2)
        return 1;

    //2. Kiểm tra xem F[n] đã được tính hay chưa? F[n]==-1 thì là chưa được tính, !=-1 là đã tính rồi
    if(F[n] != -1) return F[n];

    //3. Nếu F[n] chưa được tính thì đi tính nó và lưu lại
    F[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
    //4. Trả về kết quả
    return F[n];
}

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

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)\) là chi phí nhỏ nhất để chú ếch nhảy khi đang đứng tại hòn đá \(i\), có nghĩa là các hòn đá từ \(1\) đến \(i-1\) đã nhảy qua rồi.

Cách tiếp cận này ngược lại so với cách tiếp cận sử dụng for. Nhưng lại thuận theo thực tế và đề bài mô tả, chú ếch sẽ nhảy lần lượt các hòn đá từ trái qua phải để tới đích là hòn đá \(n\). Làm theo cách này, ta không cần suy nghĩ xem là để đến được hòn đá \(i\) ta phải nhảy từ hòn đá nào như cách làm cũ.

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

Nếu \(i=n\) thì \( return\) \(0\) (Chú ếch đang đứng tại hòn đá \(n\), thì không cần tiếp tục nhảy nữa vì đã đến đích rồi)

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

quy hoạch động
Chú ếch đang đứng tại hòn đá thứ \(i\) thì nó sẽ có 2 cách nhảy tiếp:

  • Cách 1: Nhảy từ hòn đá \(i\) đến hòn đá \(i+1\):
    => Chi phí nhỏ nhất để nhảy = (Chi phí nhỏ nhất để nhảy khi đang đứng tại \(i + 1\)) + (Chi phí nhảy từ \(i\) đến \(i+1\))
    => Chi phí để nhảy khi đang đứng từ \(i\) là: \(dp(i+1) + abs(h[i]-h[i+1])\)
  • Cách 2: Nhảy từ hòn đá \(i\) đến hòn đá \(i+2\), với điều kiện \( i\) < \(n-1\) để tồn tại hòn đá \(i+2\):Chi phí để nhảy khi đang đứng tại hòn đá \(i\) tương tự là: \(dp(i+2) + abs(h[i]-h[i+2]) \)

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

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

Kết quả nằm ở: \(dp(1)\) – Ban đầu chú ếch đang đứng tại vị trí \(1\)

Code mẫu Frog 1 C++

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define MAXN 100005
int n, h[MAXN], f[MAXN];

int dp(int i){
	if (i==n) return 0;
	if (f[i] != -1) return f[i];
	f[i] = dp(i+1) + abs(h[i] - h[i+1]);
	if(i<n-1) 
		f[i] = min(f[i], dp(i+2) + abs(h[i] - h[i+2]));
	return f[i];

}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cin>>n;
	for(int i = 1; i <= n; i++) cin>>h[i];
 
	memset(f,-1,sizeof(f));

	cout<<dp(1);
	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

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

  • Gọi \(dp(i)\) là thời gian nhỏ nhất để mua vé khi đang mua cho người thứ \(i\). Nghĩa là người từ \(1\) đến \(i-1\) đã mua rồi.

Bước 2: Xác định điều kiện dừng đệ quy
Nếu \(i>n\) thì \( return\) \(0\) (Đã mua cho cả \(n\) người rồi, thì không cần tiếp tục mua nữa)
Bước 3: Xác định công thức tính
Ta xét 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à T[i], người tiếp theo cần mua vé sẽ là người thứ \(i+1\), ta có công thức: \(dp(i+1) + T[i]\)
  • Nếu người \(i\) ra khỏi hàng và nhờ người \(i+1\) mua vé hộ, ta sẽ mất thời gian là \(R[i]\), người tiếp theo cần mua vé là ngừoi thứ \(i+2\), ta có công thức: \(dp(i+2) + R[i]\)

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

Bước 4: Xác định kết quả nằm ở đâu?
Kết quả nằm ở: \(dp(1)\) – Người đầu tiên mua vé là người thứ \(1\)

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 dp(int i){
    if (i > n) return 0;
    if(f[i] != -1) return f[i];
    f[i] = dp(i + 1) + t[i];
    if(i<n)
    	f[i] = min(f[i], dp(i + 2) + r[i]);
    return f[i];
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> t[i];
    for(int i = 1; i < n; i++) cin >> r[i];
    memset(f, 255, sizeof(f));
    cout << dp(1);
    return 0;
}

Minh hoạ thuật toán khi chạy ví dụ đề bài

quy hoạch động

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 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)\)

Nhận xét

  • 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.
  • Khi sử dụng đệ quy có nhớ, không cần quan tâm thứ tự của các bài toán, vì trong hàm đệ quy ta có xét: nếu bài toán này đã được giải quyết rồi thì sẽ không thực hiện nữa và trả về kết quả đã lưu trước đó, còn nếu bài toán chưa được giải quyết thì sẽ đi thực hiện nó.
  • Sử dụng đệ quy sẽ có thể lâu hơn vòng for một chút (không đáng kể) do vẫn phải truyền tham số vào hàm mới rồi mới check và return (nếu đề bài không ép time quá chặt thì nên làm bằng đệ quy có nhớ sẽ có lợi hơn).

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 *