Tại sao việc sử dụng Memoization trong đệ quy lại được coi là kỹ thuật bắt buộc khi giải quyết các bài toán có cấu trúc bài toán con trùng lặp (Overlapping Subproblems)?

Question

Accepted Answer

Trong các bài toán như tính dãy Fibonacci bằng đệ quy thuần túy, số lượng lời gọi hàm tăng theo hàm mũ (2^n). Memoization giúp lưu trữ kết quả của các tham số đầu vào đã tính toán vào một bộ nhớ đệm (Cache/Map). Khi gặp lại tham số đó, hàm sẽ trả về kết quả ngay lập tức thay vì tính toán lại, giúp giảm độ phức tạp thời gian từ O(2^n) xuống O(n). Đây là bước đệm quan trọng để tiến tới kỹ thuật Dynamic Programming.

Tại sao việc sử dụng Memoization trong đệ quy lại được coi là kỹ thuật bắt buộc khi giải quyết các bài toán có cấu trúc bài toán con trùng lặp (Overlapping Subproblems)?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi recursion liên quan cùng chủ đề