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 N đồng xu với giá trị V 1 , V 2 , . . . , V N 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 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.

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 j sao cho V j ≤ i V j ​ ≤i, ta xem số lượng đồng xu ít nhất đã tìm được cho tổng i − V j 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 i−V j ​ là m m. Nếu m + 1 m+1 nhỏ hơn số đồng xu tối thiểu hiện tại của tổng i i, ta cập nhật kết quả mới cho tổng i i