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.

I. BÀI TOÁN ĐỔI TIỀN

Cho một danh sách gồm N đồng xu với giá trị V1, V2, ..., VN và một tổng 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.

1. Xác định trạng thái

Ta gọi Min[i] là số lượng đồng xu ít nhất để tạo ra tổng i (với i ≤ S). Trạng thái nhỏ hơn của i là mọi Min[j] với j < i.

1. Khởi tạo

• Min[0] = 0 (tổng 0 không cần đồng xu nào)
• Với mọi i > 0: Min[i] = ∞

1. Công thức truy hồi

Với mỗi i từ 1 đến S:

• Với mỗi đồng xu Vj sao cho Vj ≤ i: Min[i] = min(Min[i], Min[i - Vj] + 1)

1. Ví dụ minh họa

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

Sau khi tính toán theo quy hoạch động, ta có: Min[11] = 3

Tập đồng xu tối ưu là: 5, 5, 1.

II. BÀI TOÁN DÃY CON KHÔNG GIẢM DÀI NHẤT

Cho dãy 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.

1. Xác định trạng thái

Gọ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].

1. Khởi tạo

Với mọi i: S[i] = 1

1. Công thức truy hồi

Với mỗi i từ 1 đến N:

• Với mỗi j < i: Nếu A[j] ≤ A[i] thì: S[i] = max(S[i], S[j] + 1)

1. Ví dụ minh họa

Dãy số: 5, 3, 4, 8, 6, 7

Bảng kết quả:

i A[i] S[i] 1 5 1 2 3 1 3 4 2 4 8 3 5 6 3 6 7 4

Kết luận: Độ dài dãy con không giảm dài nhất là 4. Cảm ơn các bạn đã đọc :>