Quy hoạch động là gì?

Quy hoạch động (Dynamic Programming) là một phương pháp giải quyết vấn đề thông qua việc chia nhỏ vấn đề lớn thành các vấn đề con nhỏ hơn, sau đó giải quyết các vấn đề con này và lưu trữ kết quả để tránh việc phải tính toán lại nhiều lần. Phương pháp này được sử dụng đặc biệt hiệu quả trong các bài toán tối ưu hóa và có thể áp dụng cho nhiều lĩnh vực như lập lịch, lập trình, kinh tế, và khoa học máy tính. Có hai hình thức chính của quy hoạch động: 1. **Top-down (Phương pháp đệ quy với bộ nhớ)**: Bắt đầu từ vấn đề lớn và đệ quy để giải quyết các vấn đề con. Kết quả của các vấn đề con được lưu trữ trong bộ nhớ (thường là một mảng hoặc bảng) để tránh việc tính toán lại. 2. **Bottom-up (Phương pháp lấp đầy bảng)**: Bắt đầu từ các vấn đề con nhỏ nhất và giải quyết từng vấn đề cho đến khi đạt đến vấn đề lớn nhất. Kết quả của các vấn đề con cũng được lưu trữ trong một bảng để có thể sử dụng cho các bước tiếp theo. Lợi ích lớn nhất của quy hoạch động là giảm thiểu độ phức tạp tính toán bằng cách sử dụng bộ nhớ để lưu trữ kết quả đã tính toán, từ đó tiết kiệm thời gian và tài nguyên tính toán. Một số vấn đề nổi bật có thể giải quyết bằng quy hoạch động bao gồm bài toán ba lô (knapsack problem), bài toán tìm đường đi ngắn nhất (shortest path problem), và bài toán tìm chuỗi con chung dài nhất (longest common subsequence problem).