Lập trình động chia nhỏ vấn đề thành các vấn đề phụ nhỏ hơn và có thể nhỏ hơn. 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.
Đối với sự cố khi sử dụng lập trình động,
- Có thể chia vấn đề thành vấn đề con chồng chéo nhỏ hơn.
- Có thể đạt được giải pháp tối ưu bằng cách sử dụng 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 khả năng ghi nhớ.
Các vấn đề lập trình động có thể được giải quyết bằng 2 cách tiếp cận -
-
Lập trình động từ dưới lên:Trong cách tiếp cận này, trước tiên, chúng tôi phân tích vấn đề và xem thứ tự giải quyết các vấn đề phụ.
-
Lập trình động từ trên xuống:Trong cách tiếp cận này, chúng tôi bắt đầu giải quyết vấn đề đã cho bằng cách chia nhỏ nó ra. Nếu bạn thấy rằng một vấn đề phụ nhất định đã được giải quyết, thì chỉ cần trả lại giải pháp đã lưu trữ.