MỘT SỐ ĐỊNH HƯỚNG CHO VIỆC ĐỊNH NGHĨA BÀI TOÁN CON VÀ XÁC
ĐỊNH CẤU TRÚC CON TỐI ƯU TRONG QUÁ TRÌNH GIẢI CÁC BÀI TOÁN
BẰNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG
Nguyễn Văn Minh
Trường PTTH Chuyên Lê Quý Đôn - Quảng Trị.
Làm sao cho học sinh PTTH có thể tiếp cận được lời giải của bài toán cùng với
kỹ thuật lập trình đặc trưng của phương pháp quy hoạch động là trăn trở của rất
nhiều giáo viên trong quá trình giảng dạy phương pháp này.
Tìm ra các bài toán con phù hợp cho một bài toán khi giải là một công việc phụ
thuộc rất nhiều kinh nghiệm và sự sáng tạo của người giải. Tuy nhiên, cũng có một
số định nghĩa lặp lại trong các bài toán quy hoạch động. Bài viết đề cập đến bốn
định hướng cho việc định nghĩa bài toán con và xác định cấu trúc con tối ưu trên
các định nghĩa đó.
I. MỞ ĐẦU.

Phương pháp quy hoạch động thường dùng để giải các bài toán tối ưu có bản
chất đệ quy, tức là việc tìm lời giải tối ưu cho bài toán đó có thể đưa về việc tìm lời
giải tối ưu của một số hữu hạn các bài toán con.
Thông thường khi giải một bài toán bằng phương pháp quy hoạch động chúng ta
cần thực hiện 4 bước sau:
1. Xác định cấu trúc của một lời giải tối ưu.
• Tìm cách chia bài toán thành các bài toán con.
• Xác định cấu trúc con tối ưu, tức là lời giải tối ưu của các bài toán con sẽ
đem lại lời giải tối ưu cho bài toán ban đầu.
2. Định nghĩa đệ quy cho giá trị của một lời giải tối ưu dựa trên giá trị có
được từ các bài toán con.
3. Tính giá trị của một lời giải tối ưu từ dưới lên.
• Tính giá trị của một lời giải tối ưu, xuất phát từ bài toán con nhỏ nhất và
lưu các giá trị đó lại theo một cách nào đó.
• Ở bước sau sẽ dùng các giá trị đã lưu từ các bước trước.
4. Xây dựng lời giải tối ưu từ các thông tin đã được lưu lại.

tổng giá trị lớn nhất.
1. Bài toán con thứ i gồm các thành phần tứ 1 đến i. Có thể phát biểu lại bài toán
như sau: Hãy chọn trong các số hạng từ 1 đến i, nhưng không được chọn 3 số hạng
liền nhau, sao cho tổng giá trị các số hạng được chọn là lớn nhất. Bài toán con thứ
n là bài toán ban đầu.
2. Với cách chia đó ta có:
+ Với bài toán con 1, chỉ có 1 món quà nên tổng giá trị thu được là a1, giá trị tối
ưu cho bài toán này là a1.
+ Với bài toán con 2 cũng vậy, chỉ có 2 món quà nên tổng giá trị thu được là
a1+a2, giá trị tối ưu cho bài toán này là a1+a2.
+ Với bài toán con 3 thì sẽ có các cách chọn thỏa mãn yêu cầu của bài toán: (a1,
a2), (a1, a3), (a2, a3) với tổng giá trị lần lượt là: a1+a2, a1+a3, a2+a3. Từ đó giá trị tối
ưu cho bài toán này là giá trị lớn nhất trong 3 cách chọn: max{a1+a2, a1+a3, a2+a3}
+ Với bài toán con 4 ta có các cách chọn: (a1, a2), (a1, a3), (a1, a4), (a2, a3), (a2,
a4), (a3, a4), (a1, a2, a4), (a1, a3, a4). Từ đó giá trị tối ưu cho bài toán này là:
max{a1+a2, a1+a3, a1+a4, a2+a3, a2+a4, a3+a4, a1+a2+a4, a1+a3+a4}
= max{max{a1+a2, a1+a3, a2+a3}, max{a1+a4, a2+a4, a1+a2+a4}, max{a1+a3+a4, a3+a4}}.

= max{max{a1+a2, a1+a3, a2+a3}, (a1+a2)+a4, (a1)+a3+a4}.
BT con 3

BT con 2

-2-

BT con 1


(Do a1, a2, a3, a4 nguyên dương nên: max{a1+a4, a2+a4, a1+a2+a4} = a1+a2+a4 và
max{a1+a3+a4, a3+a4} = a1+a3+a4)


Trường hợp 2: Cấu trúc con tối ưu của mỗi bài toán con phụ thuộc một số bài
toán con được chưa được xác định (cần phải tìm kiếm). Cấu trúc đệ quy
của bài toán thường ở dạng tuyến tính.
Bài toán 2: Dãy con đơn điệu tăng dài nhất.
Cho dãy số nguyên A, a1, a2, …, an. Một dãy con của dãy A là dãy thu được bằng

cách chọn ra từ A một số phần tử và giữ nguyên thứ tự của chúng.
Hãy tìm dãy con đơn điệu tăng của A có độ dài lớn nhất bắt đầu từ a1.
Ví dụ: với A = (5, 2, 8, 6, 3, 6, 9, 7) thì (2, 3, 6, 9) là một dãy con đơn điệu tăng
dài nhất của A.
-3-


1. Bài toán con thứ i gồm các phần tử từ 1 đến i của dãy A. Có thể phát biểu lại bài
toán như sau: Hãy tìm dãy con đơn điệu dài nhất của dãy gồm các phần tử từ 1 đến
i. Bài toán con thứ n là bài toán ban đầu.
2. Với cách phân chia đó ta có:
+ Với bài toán con thứ nhất, bởi chỉ có 1 phần tử a1 nên nó là dãy đơn điệu tăng
độ dài (lớn nhất) là 1.
+ Khi xét bài toán con thứ i, ta cần xem phần tử aj của các bài toán con j từ 1
đến i-1 xem chúng có thỏa mãn aj < ai không? Điều này đảm bảo cho ta có thể
ghép thêm ai vào cuối các dãy con đơn điệu tăng kết thúc tại j của bài toán con j.
Trong trường hợp có nhiều dãy con (của các bài toán con) như vậy chúng ta chọn
dãy con nào là dài nhất nhằm bảo đảm tính dài nhất của bài toán.
Đó cũng chính là cấu trúc con tối ưu của bài toán: lời giải tối ưu của bài toán
con thứ i phụ thuộc vào lời giải tối ưu của các bài toán con trong số các bài toán
con từ bài toán con j (1 ≤ j ≤ i - 1) mà aj < ai.
Từ phân tích trên, nếu gọi f(i) là giá trị tối ưu của bài toán con thứ i, tức là độ dài
của dãy con đơn điệu tăng có được từ dãy gồm các phần tử từ a1 đến ai thì:



Bài toán ở dạng này với đầu vào (input) thường là hai hay nhiều dãy số thành
phần của mỗi dãy có thể khác nhau. Ta xét 2 dãy sau X = x1, x2, …, xn và Y = y1, y2,
…, ym khi đó mỗi bài toán con của dạng này là 2 tiền tố của X và Y x1, x2, …, xi, với
i ≤ n và y1, y2, …, yj, với j ≤ m. Khi phân chia bài toán ban đầu thành các bài toán
con ở dạng tiền tố ta có mô hình như sau:

Hình 2: Mô hình bài toán con

Cấu trúc con tối ưu: tương ứng với quan hệ giữa 2 tiền tố. Thông thường là một
số bài toán con xác định.
Bài toán 3: Dãy con chung dài nhất (LCS).
Cho X = x1, x2, …, xm và Y = y1, y2, …, yn . Hãy tìm dãy con chung Z của X và Y.
Ví dụ:

1. Bài toán con (i, j) là các tiền tố x1, x2, …, xi, với i ≤ m và y1, y2, …, yj, với j ≤ n
của 2 dãy X và Y. Có thể phát biểu lại bài toán như sau: Hãy tìm dãy con chung
dài nhất của 2 dãy x1, x2, …, xi và y1, y2, …, yj.
2. Với cách chia đó ta có.
+ Với bài toán con (1, 1) nếu x1 = y1 thì độ dài dãy Z là 1, ngược lại là 0.
+ Với bài toán con (i, j) thì:
- nếu x1 = y1 thì độ dài dãy Z sẽ là độ dài dãy con chung dài nhất thu được từ
bài toán con (i – 1, j - 1) thêm một phần tử chung nữa.

- nếu x1 ≠ y1 thì độ dài dãy Z, hoặc là độ dài dãy con chung dài nhất thu được
từ bài toán con (i – 1, j) hoặc là từ bài toán con (i, j - 1), dãy nào dài hơn thì chọn.

-5-


toán con này ta quy ước là ∞.
+ các bài toán con (1, j) mà j > d1 thì ta có thể đổi và giá trị tối ưu của bài toán
con này tương ứng sẽ là giá trị tối ưu của bài toán con (1, j – d1) + 1.
+ các bài toán con (i, j) mà j < di với mọi i = 2, 3, …, n; rõ ràng là không đổi
được khi đó giá trị tối ưu của (i, j) sẽ là giá trị tối ưu của bài toán con (i – 1, j).
+ trường hợp còn lại là ta có thể đổi, tuy nhiên ta có thể chọn việc đổi hay
không.
- nếu không dùng tờ tiền loại i để đổi thì giá trị tối ưu của (i, j) sẽ bằng giá
trị tối ưu của bài toán con (i – 1, j).
-6-


- còn nếu dùng ít nhất một tờ loại i để đổi thì số tiền còn lại cần đổi là j – di
hay giá trị tối ưu của (i, j) sẽ bằng giá trị tối ưu (số tờ tiền ít nhất) của bài toán con
(i, j – di) thêm một tờ (di).
Gọi f(i, j) là giá trị tối ưu của bài toán con (i, j), ta có công thức:

Gọi d[1..n] mãng lưu đầu vào, ta có đoạn chương trình đệ quy sau:
const inf = maxlongint;
function f(i, j:integer): integer;
begin
if j = 0 then f :=0
else if (i = 1) and (j < d[1]) then f := inf
else if i = 1 then f := 1 + f(1, j - d[1])
else if j < d[i] then f := f(i - 1, j)
else f := min(f(i-1, j), 1 + f(i, j-d[i]));
end;
BEGIN
…
writeln(f(n, S));

2. Xét bài toán con (i, j). Ta có:
1. Nếu i > j, chỉ số đầu trái lớn hơn chỉ số đầu phải, ta quy ước đặt f(i, j)=0.
2. Nếu i = j thì f(i, i) = 1, dãy khảo sát chỉ chứa đúng 1 kí tự nên nó là đối xứng.
3. Nếu i < j và si = sj thì f(i, j) = f(i + 1, j – 1) + 2. Vì hai kí tự đầu và cuối dãy
si..sj giống nhau nên chỉ cần xác định chiều dài của dãy con đối xứng dài nhất trong
đoạn giữa là si+1.. sj–1 (bài toán con (i + 1, j – 1)) rồi cộng thêm 2 đơn vị ứng với hai
kí tự đầu và cuối dãy. Hình 4.

Hình 4: Trường hợp si = sj.

4. Nếu i < j và si ≠ sj, tức là hai kí tự đầu và cuối của dãy con si..sj là khác
nhau thì ta khảo sát hai dãy con là si..sj–1 (bài toán con (i, j – 1)) và si+1..sj (bài toán
con (i+1, j)) để lấy chiều dài của dãy con đối xứng dài nhất trong hai dãy này làm
kết quả, hình 5: f(i, j) = max{f(i, j-1),f(i+1, j)}

Hình 5: Trường hợp si ≠ sj.

Vậy lời giải tối ưu của bài toán con (i, j) phụ thuộc vào sự tối ưu của các bài
toán con (i+1, j-1), (i, j-1) và (i+1, j). Lời giải tối ưu của bài toán ban đầu (1, n)
phụ thuộc vào sự tối ưu của các bài toán con (2, n-1), (1, n-1) và (2, n).
Ta có công thức sau:

Ta có chương trình con đệ quy sau:
function f(i, j : longint) : longint;
begin
if i > j then f ≔ 0
else if i = j then f ≔ 1
else if s[i] = s[j] then f ≔ f(i + 1, j - 1) + 2 else f := max(f(i, j - 1), f(i + 1, j);

-8-

Dễ thấy với điểm chia i ta sẽ có các bài toán con tương ứng (cùng kiểu). Nếu bài
toán chỉ gồm một đống, chi phí là 0. Nếu bài toán có 2 đống ta cũng có ngay kết
quả. Nếu bài toán có 3 đống thì ta có thể dựa trên bài toán 2 đống và 1 đống để tìm
kết quả, tiếp tục quá trình như vậy cho đến khi có N đống.
Bằng cách dùng điểm chia ta có thể liệt kê tất cả các cách ghép: (a1)( a2, …, an),
(a1, a2)(a3, a4, …, an), (a1, a2, a3)(a4, a5, …, an), …, (a1, a2, …, ai-1)(an) và tìm cách
tối ưu chúng.
1. Do tính đối xứng của phép đặt móc nên ta chia bài toán theo mô hình trên, bài
toán con (i, j) gồm các đống sỏi ai, ai+1, …, aj. Bài toán (1, N) là bài toán ban đầu.
2. Với cách chia bài toán con như vậy ta thấy: lời giải tối ưu cho bài toán (i, j) là
tìm cách ghép các đống sỏi từ đống thứ i tới đống thứ j với tổng chi phí nhỏ nhất.
-9-


• Với mọi cách ghép thì phép ghép cuối cùng luôn có chi phí là ai, ai+1, …, aj.
• Với điểm chia k (i ≤ k ≤ j), lời giải tối ưu của bài toán (i, j) phụ thuộc vào lời
giải tối ưu của các bài toán con (i, k) và (k+1, j). Hay nói cách khác là sẽ phụ thuộc
vào tất cả các bài toán con được tạo ra từ điểm chia k:
k=i
k = i+1
…
k=j

(ai)( ai+1, …, aj)
(ai, ai+1)(ai+2, ai+3, …, aj)
…
(ai, ai+1, …, aj-1)(aj)

Gọi f(i, j) là giá trị tối ưu của bài toán con (i, j), tương ứng là tổng chi phí nhỏ
nhất để ghép các đống sỏi từ đống i đến đống j thành một đống.



Hình 8: Mô hình dạng cây.

Cấu trúc con tối ưu: Cấu trúc con tối ưu của mỗi bài toán con phụ thuộc vào số
bài toán con tương ứng là số node con của cây con đó.
Bài toán 7: Tam giác số.
Cho một tam giác số như hình sau:
7
3
8
2

8
1

7

0
4

4

4
5
2
6
5
Tìm một đường đi từ đỉnh đến đáy tam giác sao cho tổng tất cả các số trên
đường đi là lớn nhất, mỗi bước đi chỉ có thể đi chéo xuống phía trái hoặc chéo

5 2 6 5

Hình 10: Bảng đầu vào.
Hình 9: Cây đầu vào.

1. Với cách chia trên, bài toán con (r, c) tương ứng là tìm cách đi tối ưu để đi từ
gốc (r, c) đến một node lá.
2. Rõ ràng từ gốc (r, c) chỉ có thể đi xuống một trong hai node (r+1, c) hoặc (r+1,
c+1). Hay nói cách khác sự tối ưu của bài toán con gốc (r, c) phụ thuộc sự tối ưu
của các bài toán con gốc (r+1, c) và gốc (r+1, c+1).
Gọi f(r, c) là giá trị tối ưu của bài toán con (r, c) và bảng t[1..N, 1..N] lưu bảng
đầu vào.
- 11 -


Ta có công thức sau:

Từ đó ta có đoạn chương trình đệ quy tìm giá trị tối ưu của các bài toán con (r, c)
và của bài toán ban đầu.
function f(r, c : longint) : longint;
begin
if r = N then f ≔ t[r, c]
else f := max(f(r + 1, c), f(r+1, c + 1)) + t[r, c]);
end;
BEGIN
…
write(f(1, 1));
…
END.