NHẬP MÔN QUY HOẠCH ĐỘNG

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

Quy hoạch động (Dynamic Programming - 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 con trước đó.

Các thuật toán DP thường có độ phức tạp đa thức, giúp đảm bảo thời gian chạy tối ưu hơn rất nhiều so với các kỹ thuật vét cạn (brute-force) hay quay lui (backtracking).

2. Ví dụ 1: Bài toán Đổi tiền (Coin Change)

Đề bài:

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

Xây dựng lời giải

• Trạng thái (State): Trạng thái là cách mô tả một bài toán con. Ta gọi trạng thái \(i\) (\(i \le S\)) là số lượng đồng xu ít nhất để tạo ra tổng giá trị \(i\). Để tính trạng thái \(i\), ta cần biết kết quả của các trạng thái nhỏ hơn \(j\) (\(j < i\)).
• Cách tìm trạng thái:
• Với mỗi đồng xu \(j\) thỏa mãn \(V_j \le i\), ta xét số lượng đồng xu tối thiểu để tạo ra tổng \(i - V_j\).
• Giả sử số lượng đồng xu tối thiểu cho tổng \(i - V_j\) là \(m\). Nếu \(m + 1\) nhỏ hơn số lượng đồng xu tối thiểu hiện tại của tổng \(i\), ta cập nhật lại giá trị tối ưu cho \(i\).

Ví dụ minh họa

• Các đồng xu: \(1, 3, 5\).
• Tổng cần đạt: \(S = 11\).

Khởi tạo:

• Với tổng \(0\): Cần \(0\) đồng xu (\(\text{Min}[0] = 0\)).
• Với các tổng khác: Gán giá trị ban đầu là \(\infty\).

Quá trình tính toán:

• Tổng \(S = 1\): Chỉ có đồng xu \(1 \le 1\). Xét \(1 - 1 = 0 \rightarrow \text{Min}[1] = \text{Min}[0] + 1 = 1\).
• Tổng \(S = 2\): Chỉ có đồng xu \(1 \le 2\). Xét \(2 - 1 = 1 \rightarrow \text{Min}[2] = \text{Min}[1] + 1 = 2\).
• Tổng \(S = 3\): Có 2 đồng xu khả dụng (\(1, 3\)):
• Dùng đồng \(1\): Tổng \(3 - 1 = 2\) cần \(2\) đồng \(\rightarrow 2 + 1 = 3\) đồng.
• Dùng đồng \(3\): Tổng \(3 - 3 = 0\) cần \(0\) đồng \(\rightarrow 0 + 1 = 1\) đồng.

• Chọn tối ưu: \(\text{Min}[3] = 1\).

• Tổng \(S = 4\):

• Dùng đồng \(1\): Tổng \(4 - 1 = 3\) cần \(1\) đồng \(\rightarrow 1 + 1 = 2\) đồng.
• Dùng đồng \(3\): Tổng \(4 - 3 = 1\) cần \(1\) đồng \(\rightarrow 1 + 1 = 2\) đồng.

• Chọn tối ưu: \(\text{Min}[4] = 2\).

• Tổng \(S = 5\):

• Dùng đồng \(1\): Cần \(1 + \text{Min}[4] = 3\) đồng.
• Dùng đồng \(3\): Cần \(1 + \text{Min}[2] = 3\) đồng.
• Dùng đồng \(5\): Cần \(1 + \text{Min}[0] = 1\) đồng.

• Chọn tối ưu: \(\text{Min}[5] = 1\).

• Tiếp tục lần lượt cho các tổng \(6, 7, \dots, 11\).

Kết quả: Số đồng xu ít nhất để tạo thành tổng \(11\) là 3 đồng xu (\(5 + 5 + 1\)).

3. Ví dụ 2: Dãy con không giảm dài nhất (Longest Non-Decreasing Subsequence)

Đề bài:

Cho dãy gồm \(N\) số: \(A[1], A[2], \dots, 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 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]\).
• \(S[i]\) chỉ phụ thuộc vào các phần tử đứng trước nó (\(j < i\)) và không bị thay đổi bởi các phần tử phía sau.

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

• Khởi tạo: Mỗi phần tử đứng một mình tạo thành dãy con độ dài 1: $\(S[i] = 1 \quad (\forall i = 1 \dots N)\)$

• Chuyển trạng thái: Với mỗi \(j < i\), nếu \(A[j] \le A[i]\) và \(S[j] + 1 > S[i]\), ta cập nhật: $\(S[i] = S[j] + 1\)$

Ví dụ minh họa

Xét dãy số: \(5, 3, 4, 8, 6, 7\)

Kết quả: Độ dài dãy con không giảm dài nhất là 4.

4. Một số bài tập vận dụng đề xuất

• Bài toán chiếc balo 5 (Unbounded Knapsack)
• Bài toán xâu con chung dài nhất (LCS)