Có thể cải thiện mọi thuật toán đệ quy bằng lập trình động không?

Question

Tôi là sinh viên năm thứ nhất của trường đại học CSC đang tìm cách tham gia vào chương trình cạnh tranh.

Đệ quy liên quan đến việc xác định và giải quyết các vấn đề phụ. Như tôi đã hiểu, lập trình động từ trên xuống (dp) liên quan đến việc ghi nhớ các giải pháp cho các vấn đề phụ để giảm thời gian phức tạp của thuật toán.

Có thể sử dụng dp trên cùng để cải thiện hiệu quả của mọi thuật toán đệ quy với các vấn đề phụ trùng lặp? Trường hợp dp sẽ không làm việc và làm thế nào tôi có thể xác định điều này?

Answer 1

Câu trả lời ngắn gọn là: Có.

Tuy nhiên, có một số hạn chế. Điều rõ ràng nhất là các cuộc gọi đệ quy phải chồng lên nhau. I E. trong khi thực thi thuật toán, hàm đệ quy phải được gọi nhiều lần với cùng các tham số. Điều này cho phép bạn cắt bớt cây đệ quy bằng cách ghi nhớ. Vì vậy, bạn luôn có thể sử dụng tính năng ghi nhớ để giảm số lượng cuộc gọi.

Tuy nhiên, việc giảm các cuộc gọi này đi kèm với một mức giá. Bạn cần lưu trữ kết quả ở đâu đó. Ràng buộc rõ ràng tiếp theo là bạn cần có đủ bộ nhớ. Điều này đi kèm với một ràng buộc không rõ ràng. Truy cập bộ nhớ luôn đòi hỏi một chút thời gian. Trước tiên, bạn cần phải tìm nơi kết quả được lưu trữ và sau đó thậm chí có thể sao chép nó vào một số vị trí. Vì vậy, trong một số trường hợp, nó có thể nhanh hơn để cho đệ quy tính toán kết quả thay vì tải nó từ đâu đó. Nhưng điều này rất thực hiện cụ thể và thậm chí có thể phụ thuộc vào hệ điều hành và thiết lập phần cứng.