Quy hoạch động chia bài toán thành các bài toán con nhỏ hơn và nhỏ hơn nữa. Các bài toán con này không được giải độc lập. Thay vào đó, kết quả của các bài toán con nhỏ hơn được ghi nhớ và dùng cho các bài toán con tương tự hoặc chồng chéo.
Quy hoạch động dùng ở nơi có bài toán, có thể chia thành các bài toán con tương tự để kết quả có thể tái sử dụng. Phần lớn, các thuật toán này dùng cho tối ưu hóa. Trước khi giải bài toán con hiện tại, thuật toán quy hoạch động sẽ thử kiểm tra kết quả của các bài toán con đã giải trước. Các giải pháp của bài toán con được kết hợp để đạt giải pháp tốt nhất.
Để một bài toán dùng quy hoạch động:
- Bài toán phải có thể chia thành các bài toán con nhỏ hơn chồng chéo.
- Giải pháp tối ưu có thể đạt được bằng cách dùng giải pháp tối ưu của các bài toán con nhỏ hơn.
- Thuật toán quy hoạch động sử dụng ghi nhớ (memorization).
Bài toán quy hoạch động có thể giải bằng 2 cách tiếp cận:
Bottom Up Dynamic Programming (Từ dưới lên): Trong cách này, ta trước phân tích bài toán và xem thứ tự các bài toán con được giải. Ta bắt đầu giải bài toán con tầm thường và xây dựng lên bài toán cho trước.
Top Down Dynamic Programming (Từ trên xuống): Trong cách này, ta bắt đầu giải bài toán cho trước bằng cách chia nhỏ nó. Nếu thấy một bài toán con đã được giải, chỉ trả về giải pháp đã lưu.