Quy hoạch động là gì, và nó được mô tả như thế nào?

Quy hoạch động (DP) là một kỹ thuật thuật toán thường dựa trên một công thức truy hồi và một (hoặc một vài) trạng thái khởi đầu. Một lời giải con của bài toán được xây dựng từ các lời giải trước đó. Các thuật toán DP có độ phức tạp đa thức, giúp đảm bảo thời gian chạy nhanh hơn nhiều so với các kỹ thuật khác như quay lui (backtracking) hay brute-force.

Bây giờ, hãy tìm hiểu cơ sở của quy hoạch động thông qua một ví dụ:

Cho một danh sách gồm \(N\) đồng xu với giá trị \(V_1, V_2, ..., V_N\) và một tổng số tiền cần đạt được là \(S\). Hãy tìm số lượng đồng xu ít nhất sao cho tổng của chúng bằng \(S\) (có thể sử dụng một đồng xu nhiều lần), hoặc kết luận rằng không thể chọn được tập hợp đồng xu thỏa mãn điều kiện.

Bây giờ, chúng ta sẽ bắt đầu xây dựng một lời giải DP:

Trước hết, chúng ta cần tìm một trạng thái mà tại đó ta có thể xác định được lời giải tối ưu và sử dụng nó để tìm lời giải tối ưu cho các trạng thái tiếp theo.

Trạng thái (“state”) có nghĩa là gì?

Trạng thái là một cách để mô tả một tình huống, một lời giải con của bài toán. Ví dụ, một trạng thái có thể là lời giải cho tổng \(i\), trong đó \(i \leq S\).

Một trạng thái nhỏ hơn trạng thái \(i\) sẽ là lời giải cho bất kỳ tổng nào \(j\), với \(j < i\).

Để tìm trạng thái \(i\), trước tiên ta cần tìm tất cả các trạng thái nhỏ hơn \(i\), tức là các trạng thái \(j\) với \(j < i\).

Khi đã tìm được số lượng đồng xu ít nhất để tạo ra tổng \(i\), ta có thể dễ dàng tìm được trạng thái tiếp theo – lời giải cho tổng \(i+1\).

Làm thế nào để tìm được trạng thái?

Cách tìm rất đơn giản:
- Với mỗi đồng xu \(j\) sao cho \(V_j \leq i\), ta xem số lượng đồng xu ít nhất đã tìm được cho tổng \(i - V_j\) (vì trước đó ta đã tính toán cho tổng này).
- Giả sử số đồng xu tối thiểu cần thiết để tạo tổng \(i - V_j\) là \(m\). Nếu \(m + 1\) nhỏ hơn số đồng xu tối thiểu hiện tại của tổng \(i\), ta cập nhật kết quả mới cho tổng \(i\).

Ví dụ minh họa

Cho các đồng xu có giá trị: \(1, 3, 5\).
Tổng cần đạt được: \(S = 11\).

1. Khởi tạo trạng thái ban đầu:

   • Với tổng 0, số đồng xu tối thiểu là 0.
   • Với các tổng khác, chưa có lời giải, nên gán giá trị ban đầu là \(\infty\).

2. Xét tổng \(S = 1\):

   • Chỉ có đồng xu 1 nhỏ hơn hoặc bằng 1.
   • Xét tổng 1 - 1 = 0, ta đã có lời giải cho tổng 0 là 0 đồng xu.
   • Khi thêm đồng xu 1, ta có tổng 1 với 1 đồng xu → Cập nhật Min[1] = 1.

3. Xét tổng \(S = 2\):

   • Chỉ có đồng xu 1 nhỏ hơn hoặc bằng 2.
   • Tổng 2 - 1 = 1 có lời giải là 1 đồng xu.
   • Thêm đồng xu 1, tổng 2 cần 2 đồng xu → Min[2] = 2.

4. Xét tổng \(S = 3\):

   • Có 2 đồng xu khả dụng: 1, 3.
   • Dùng đồng xu 1: tổng 3 - 1 = 2 có lời giải 2 đồng xu. Thêm 1 đồng xu → 3 đồng xu.
   • Dùng đồng xu 3: tổng 3 - 3 = 0 có lời giải 0 đồng xu. Thêm 1 đồng xu → 1 đồng xu.
   • Chọn lời giải tối ưu → Min[3] = 1.

5. Xét tổng \(S = 4\):

   • Dùng đồng xu 1: tổng 4 - 1 = 3 có lời giải 1 đồng xu. Thêm 1 đồng xu → 2 đồng xu.
   • Dùng đồng xu 3: tổng 4 - 3 = 1 có lời giải 1 đồng xu. Thêm 1 đồng xu → 2 đồng xu.
   • Cả hai cách đều cho 2 đồng xu → Min[4] = 2.

6. Xét tổng \(S = 5\):

   • Dùng đồng xu 1: tổng 5 - 1 = 4 có lời giải 2 đồng xu. Thêm 1 đồng xu → 3 đồng xu.
   • Dùng đồng xu 3: tổng 5 - 3 = 2 có lời giải 2 đồng xu. Thêm 1 đồng xu → 3 đồng xu.
   • Dùng đồng xu 5: tổng 5 - 5 = 0 có lời giải 0 đồng xu. Thêm 1 đồng xu → 1 đồng xu.
   • Chọn lời giải tối ưu → Min[5] = 1.

Tiếp tục với tổng 6, 7, …, 11 theo cách tương tự.

Kết quả cuối cùng

Sau khi tính toán, số đồng xu ít nhất để tạo tổng \(11\) là \(3\) đồng xu: \(5, 5, 1\).

Dãy con không giảm dài nhất

Đến thời điểm này, chúng ta đã thảo luận về những ví dụ rất đơn giản.

Bây giờ, hãy tìm cách chuyển từ trạng thái này sang trạng thái khác trong các bài toán khó hơn. Để làm điều đó, chúng ta sẽ giới thiệu một khái niệm mới gọi là công thức truy hồi (recurrent relation), giúp kết nối giữa một trạng thái nhỏ hơn và một trạng thái lớn hơn.

Cho một dãy gồm \(N\) số: \(A[1], A[2], ..., A[N]\). Hãy tìm độ dài lớn nhất của dãy con không giảm.

Bước 1: Xác định trạng thái

Như đã thảo luận trước đó, chúng ta cần xác định một trạng thái (“state”) thể hiện một bài toán con, và từ đó tìm ra lời giải cho nó.
Trong hầu hết các trường hợp, một trạng thái phụ thuộc vào các trạng thái trước đó (nhỏ hơn nó) và không bị ảnh hưởng bởi các trạng thái lớn hơn.

Chúng ta định nghĩa trạng thái \(S[i]\) là độ dài của dãy con không giảm dài nhất kết thúc tại phần tử \(A[i]\).

• Trạng thái \(S[i]\) chỉ chứa thông tin về độ dài dãy con, không quan tâm đến các số phía sau nó.
• Khi \(i < j\), trạng thái \(S[i]\) không bị thay đổi khi tính toán \(S[j]\).

Bước 2: Công thức truy hồi

• Khởi tạo: Ban đầu, mỗi phần tử đều có thể tạo thành một dãy con riêng lẻ, do đó: \(S[i] = 1, \quad \text{với mọi } i\)
• Chuyển trạng thái:
  Với mỗi \(j < i\), ta kiểm tra xem có thể mở rộng dãy con không giảm hay không:
  • Nếu \(A[j] \leq A[i]\) (tức là dãy con vẫn không giảm), ta có thể mở rộng \(S[j]\) bằng cách thêm \(A[i]\).
  • Nếu \(S[j] + 1 > S[i]\), ta cập nhật: \(S[i] = S[j] + 1\)

Như vậy, ta duyệt qua từng phần tử \(i\), tìm trạng thái tối ưu dựa trên các trạng thái trước đó.

Ví dụ minh họa

Xét dãy số:

Kết quả cuối cùng: Dãy con không giảm dài nhất có độ dài 4.

Một số bài tập vận dụng

1. Bài toán chiếc balo 5
2. Bài toán dãy con tăng dài nhất
3. Bài toán xâu con chung dài nhất

Nguồn: Dynamic Programming - From Novice to Advanced