Làm thế nào để áp dụng kỹ thuật Memoization vào hàm đệ quy để giải quyết bài toán tính dãy Fibonacci hoặc quy hoạch động cơ bản nhằm tránh lặp toán tử?

Question

Accepted Answer

Bản chất vấn đề
Đệ quy thuần túy đôi khi tính toán lại một tập hợp các giá trị con rất nhiều lần, dẫn đến độ phức tạp thời gian theo cấp số nhân (Exponential Time Complexity O(2^n)). Memoization là kỹ thuật lưu trữ kết quả của các lời gọi hàm đã thực hiện vào một bộ nhớ đệm (Cache) để tái sử dụng.
Lợi ích thực tế
Biến đổi độ phức tạp thời gian từ O(2^n) xuống còn O(n), giúp cải thiện hiệu năng rõ rệt cho các API xử lý tính toán nặng trong hệ thống.
Ví dụ minh họa bằng JavaScript
function fibonacci(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];

memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

Làm thế nào để áp dụng kỹ thuật Memoization vào hàm đệ quy để giải quyết bài toán tính dãy Fibonacci hoặc quy hoạch động cơ bản nhằm tránh lặp toán tử?

Bản chất vấn đề

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ủ đề