Lập trình

- Kỹ thuật chia để trị thường dẫn chúng ta tới một giải thuật đệ quy. Trong các giải thuật đó, có thể có một số giải thuật có độ phức tạp thời gian mũ

- Ðể tránh việc giải dư thừa một số bài toán con, chúng ta tạo ra một bảng để lưu trữ kết quả của các bài toán con và khi cần chúng ta sẽ sử dụng kết quả đã được lưu trong bảng mà không cần phải giải lại bài toán đó

- Lấp đầy bảng kết quả các bài toán con theo một quy luật nào đó để nhận được kết quả của bài toán ban đầu (cũng đã được lưu trong một số ô nào đó của bảng) được gọi là quy hoạch động (dynamic programming). Trong một số trường hợp, để tiết kiệm ô nhớ, thay vì dùng một bảng, ta chỉ dùng một véctơ

- Quy hoạch động là kỹ thuật nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu trữ môt phần hay toàn bộ kết quả tính toán tại mỗi bước với mục đích sử dụng lại

Tạo bảng bằng cách:

Gán giá trị cho một số ô nào đó

Gán trị cho các ô khác nhờ vào giá trị của các ô trước đó

Tra bảng và xác định kết quả của bài toán ban đầu

- Ưu điểm của phương pháp quy hoạch động là chương trình thực hiện nhanh do không phải tốn thời gian giải lại một số bài toán con đã được giải

- Kỹ thuật quy hoạch động có thể vận dụng để giải các bài toán tối ưu, các bài toán có công thức truy hồi

- Phương pháp quy hoạch động sẽ không đem lại hiệu quả trong các trường hợp sau:

Không tìm được công thức truy hồi

Số lượng các bài toán con cần giải quyết và lưu giữ kết quả là rất lớn

Sự kết hợp lời giải của các bài toán con chưa chắc cho ta lời giải của bài toán ban đầu