CTDL và giải thuật - Giải thuật Qui hoạch động

Cho một dãy số nguyên a gồm n số nguyên. Hãy đưa ra dãy con không giảm dài nhất ở trong dãy a, nếu có nhiều dãy con dài nhất thì đưa ra dãy xuất hiện đầu tiên.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    7
    1 2 1 4 5 6 2

    1 4 5 6

    Với a = [1, 2, 1, 4, 5, 6, 2] thì kết quả mong muốn là: " 1 4 5 6".
     
  • Test mẫu 2:
     
    Input Output

    6
    1 2 3 1 3 4

    1 2 3 

    Với a = [1, 2, 3, 1, 3, 4] thì kết quả mong muốn là: "1 2 3 ".

Lý thuyết.

Giới thiệu giải thuật Qui hoạch động (Dynamic Programming).

Giải thuật Qui hoạch động (Dynamic Programming) giống như giải thuật chia để trị (Divide and Conquer) trong việc chia nhỏ bài toán thành các bài toán con nhỏ hơn và sau đó thành các bài toán con nhỏ hơn nữa có thể. Nhưng không giống chia để trị, các bài toán con này không được giải một cách độc lập. Thay vào đó, kết quả của các bài toán con này được lưu lại và được sử dụng cho các bài toán con tương tự hoặc các bài toán con gối nhau (Overlapping Sub-problems).

Chúng ta sử dụng Qui hoạch động (Dynamic Programming) khi chúng ta có các bài toán mà có thể được chia thành các bài toán con tương tự nhau, để mà các kết quả của chúng có thể được tái sử dụng. Thường thì các giải thuật này được sử dụng cho tối ưu hóa. Trước khi giải bài toán con, giải thuật Qui hoạch động sẽ cố gắng kiểm tra kết quả của các bài toán con đã được giải trước đó. Các lời giải của các bài toán con sẽ được kết hợp lại để thu được lời giải tối ưu.

Do đó, chúng ta có thể nói rằng:

  • Bài toán ban đầu nên có thể được phân chia thành các bài toán con gối nhau nhỏ hơn.

  • Lời giải tối ưu của bài toán có thể thu được bởi sử dụng lời giải tối ưu của các bài toán con.

  • Giải thuật Qui hoạch động sử dụng phương pháp lưu trữ (Memoization) – tức là chúng ta lưu trữ lời giải của các bài toán con đã giải, và nếu sau này chúng ta cần giải lại chính bài toán đó thì chúng ta có thể lấy và sử dụng kết quả đã được tính toán.

So sánh

Giải thuật tham lam và giải thuật qui hoạch động.

  • Giải thuật tham lam (Greedy Algorithms) là giải thuật tìm kiếm, lựa chọn giải pháp tối ưu địa phương ở mỗi bước với hi vọng tìm được giải pháp tối ưu toàn cục.

  • Giải thuật Qui hoạch động tối ưu hóa các bài toán con gối nhau.

Giải thuật chia để trị và giải thuật Qui hoạch động:

  • Giải thuật chia để trị (Divide and Conquer) là kết hợp lời giải của các bài toán con để tìm ra lời giải của bài toán ban đầu.

  • Giải thuật Qui hoạch động sử dụng kết quả của bài toán con và sau đó cố gắng tối ưu bài toán lớn hơn. Giải thuật Qui hoạch động sử dụng phương pháp lưu trữ (Memoization) để ghi nhớ kết quả của các bài toán con đã được giải.

Hướng dẫn bài tập.

Với bài này chúng ta có thể làm như sau:

  • Tạo dãy l, với l[i] dùng để lưu độ dài của dãy con dài nhất kết thúc tại il[0] = 1.
  • Nếu a[i] ≥ a[i-1] thì l[i] = l[i-1] + 1, ngược lại l[i] = 1.
  • Độ dài của dãy con không giảm dài nhất chính là phần tử lớn nhất trong dãy l.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

int a[100001];
int l[100001];
void printArray(int a[], int l, int r){
	for (int i = l; i <=r; i++){
		cout << a[i] << " ";
	}
}
int main(){
	int n, x;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	l[0] = 1;
	for (int i = 1; i < n; i++){
		if (a[i] >= a[i-1]){
			l[i] = l[i-1] + 1;
		} else {
			l[i] = 1;
		}
	}
	int csMax = 0;
	for (int i = 0; i < n; i++){
		if (l[csMax] < l[i]){
			csMax = i;
		}
	}
	printArray(a, csMax - l[csMax] + 1, csMax);
	return 0;
}