Cấu trúc dữ liệu - Lập trình động

Cách tiếp cận lập trình động tương tự như phương pháp phân chia và chinh phục trong việc chia nhỏ vấn đề thành các vấn đề con nhỏ hơn và có thể nhỏ hơn. Nhưng không giống như, phân chia và chinh phục, những vấn đề phụ này không được giải quyết một cách độc lập. Thay vào đó, kết quả của các bài toán con nhỏ hơn này được ghi nhớ và sử dụng cho các bài toán con tương tự hoặc chồng chéo.

Lập trình động được sử dụng khi chúng ta gặp vấn đề, có thể được chia thành các vấn đề con tương tự để có thể sử dụng lại kết quả của chúng. Hầu hết, các thuật toán này được sử dụng để tối ưu hóa. Trước khi giải bài toán con trong tay, thuật toán động sẽ cố gắng 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 các vấn đề phụ được kết hợp để đạt được giải pháp tốt nhất.

Vì vậy, chúng ta có thể nói rằng -

Vấn đề có thể được chia thành các vấn đề con chồng chéo nhỏ hơn.
Một giải pháp tối ưu có thể đạt được bằng cách sử dụng một giải pháp tối ưu cho các vấn đề nhỏ hơn.
Các thuật toán động sử dụng Memoization.

So sánh

Ngược lại với các thuật toán tham lam, trong đó tối ưu hóa cục bộ được giải quyết, các thuật toán động được thúc đẩy để tối ưu hóa tổng thể của vấn đề.

Ngược lại với các thuật toán phân chia và chinh phục, trong đó các giải pháp được kết hợp để đạt được một giải pháp tổng thể, các thuật toán động sử dụng đầu ra của một bài toán con nhỏ hơn và sau đó cố gắng tối ưu hóa một bài toán con lớn hơn. Các thuật toán động sử dụng Ghi nhớ để ghi nhớ kết quả đầu ra của các bài toán con đã được giải quyết.

Thí dụ

Các vấn đề máy tính sau đây có thể được giải quyết bằng cách sử dụng phương pháp lập trình động:

Chuỗi số Fibonacci
Knapsack vấn đề
Tháp Hà Nội
Tất cả các cặp đường đi ngắn nhất của Floyd-Warshall
Con đường ngắn nhất của Dijkstra
Lập kế hoạch dự án

Lập trình động có thể được sử dụng theo cả cách từ trên xuống và từ dưới lên. Và tất nhiên, hầu hết các trường hợp, tham khảo đầu ra giải pháp trước đó rẻ hơn so với tính toán lại về chu kỳ CPU.