Giới thiệu DP

Chương này sẽ giới thiệu về Quy hoạch động (Dynamic Programming, DP) cùng các bài toán mà nó giải quyết, các thuật toán được thiết kế dựa trên nó và các kỹ thuật tối ưu hóa liên quan.

Quy hoạch động là một phương pháp giải quyết các bài toán phức tạp bằng cách chia bài toán gốc thành các bài toán con tương đối đơn giản hơn.

Vì quy hoạch động không phải là một thuật toán cụ thể nào đó mà là một phương pháp để giải quyết các loại bài toán đặc thù, nên nó xuất hiện trong rất nhiều loại cấu trúc dữ liệu khác nhau, và các dạng bài tập liên quan cũng vô cùng đa dạng.

Trong OI (Tin học trẻ/Olympic Tin học), các phương pháp giải bằng đệ quy/truy hồi cho các bài toán không phải tối ưu hóa (như bài toán đếm) cũng thường được gọi là DP một cách không chính thống. Do đó, chương này sẽ liệt kê cả những nội dung đó. Trên thực tế, quy hoạch động và các loại công thức truy hồi khác thực sự có nhiều điểm tương đồng, khi học bạn có thể chú ý đến sự giống và khác nhau giữa chúng.

Tài liệu tham khảo

Quy hoạch động - Wikipedia, bách khoa toàn thư mở

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply