DAA - Lập trình động

Lập trình động cũng được sử dụng trong các bài toán tối ưu hóa. Giống như phương pháp chia để trị, Lập trình động giải quyết các vấn đề bằng cách kết hợp các giải pháp của các bài toán con. Hơn nữa, thuật toán Lập trình động giải quyết mỗi vấn đề con chỉ một lần và sau đó lưu câu trả lời của nó vào một bảng, do đó tránh phải tính toán lại câu trả lời mỗi lần.

Hai thuộc tính chính của một vấn đề gợi ý rằng vấn đề đã cho có thể được giải quyết bằng cách sử dụng Lập trình động. Các thuộc tính này làoverlapping sub-problems and optimal substructure.

Các vấn đề phụ chồng chéo

Tương tự như cách tiếp cận Phân chia và Chinh phục, Lập trình động cũng kết hợp các giải pháp cho các vấn đề phụ. Nó chủ yếu được sử dụng khi cần lặp đi lặp lại giải pháp của một vấn đề phụ. Các giải pháp đã tính toán được lưu trữ trong một bảng, do đó chúng không cần phải tính toán lại. Do đó, kỹ thuật này là cần thiết khi tồn tại vấn đề phụ chồng chéo.

Ví dụ, Tìm kiếm nhị phân không có vấn đề phụ chồng chéo. Trong khi chương trình đệ quy các số Fibonacci có nhiều vấn đề con trùng lặp.

Cấu trúc con tối ưu

Một bài toán đã cho có Thuộc tính cấu trúc con tối ưu, nếu phương án tối ưu của bài toán đã cho có thể thu được bằng cách sử dụng các lời giải tối ưu của các bài toán con của nó.

Ví dụ, bài toán Đường đi ngắn nhất có thuộc tính cấu trúc con tối ưu sau:

Nếu một nút x nằm trong đường dẫn ngắn nhất từ nút nguồn u đến nút đích v, sau đó là con đường ngắn nhất từ u đến v là sự kết hợp của con đường ngắn nhất từ u đến xvà con đường ngắn nhất từ x đến v.

Các thuật toán đường dẫn ngắn nhất theo cặp tiêu chuẩn như Floyd-Warshall và Bellman-Ford là những ví dụ điển hình của Lập trình động.