Tổng quan
Ghi nhớ (memoization) từ trên xuống giữ nguyên cấu trúc đệ quy tự nhiên nhưng thêm một bộ nhớ đệm: lần đầu một bài toán con được giải, đáp án của nó được lưu lại, và mọi yêu cầu sau trả về giá trị đã lưu thay vì tính lại.
Áp dụng cho Fibonacci, ghi nhớ tạo ra thay đổi lớn: đệ quy ngây thơ theo cấp số nhân thu về thời gian tuyến tính vì mỗi giá trị fib(k) được tính đúng một lần, rồi tái sử dụng.
Ghi nhớ (Memoization) hoạt động thế nào?
- Trước khi tính fib(n), kiểm tra xem bộ nhớ đệm đã có nó chưa.
- Nếu trúng cache, trả về giá trị đã lưu ngay lập tức — không đệ quy thêm.
- Nếu trượt, đệ quy vào fib(n−1) và fib(n−2) như thường để lấy giá trị.
- Lưu kết quả vừa tính vào bộ nhớ đệm trước khi trả về.
Khi nào nên dùng?
- Các bài toán quy hoạch động có bài toán con chồng lấn (Fibonacci, đổi tiền, đường đi trên lưới).
- Bổ sung tốc độ cho một lời giải đệ quy rõ ràng sẵn có với thay đổi mã tối thiểu.
- Ưu tiên lập bảng từ dưới lên khi độ sâu đệ quy có nguy cơ tràn ngăn xếp.
Phân tích độ phức tạp
Với ghi nhớ, mỗi trong n bài toán con phân biệt được giải một lần và tái dùng rẻ, nên Fibonacci chạy trong O(n). Bộ nhớ đệm và ngăn xếp đệ quy mỗi cái giữ O(n) mục, cho O(n) bộ nhớ — cải thiện vượt bậc so với O(φ^n) ngây thơ.
Câu hỏi thường gặp
Ghi nhớ và lập bảng khác nhau thế nào?
Ghi nhớ là từ trên xuống: nó đệ quy và lưu kết quả một cách lười khi cần. Lập bảng là từ dưới lên: nó điền bảng bằng vòng lặp từ các trường hợp cơ sở. Cả hai đều đạt O(n) cho Fibonacci.
Ghi nhớ có làm thay đổi đáp án của thuật toán không?
Không. Nó chỉ tránh làm lại việc; các giá trị trả về giống hệt đệ quy ngây thơ. Đây là tối ưu hiệu năng thuần túy, đánh đổi bộ nhớ lấy thời gian.