Làm thế nào để thiết kế cấu trúc dữ liệu lưu trữ Memoization (Cache) một cách hiệu quả khi bài toán Dynamic Programming có nhiều hơn hai biến trạng thái, nhằm tránh tình trạng rò rỉ bộ nhớ (Memory Leak) trong các ứng dụng chạy dài hạn (Long-running processes)?

Question

Accepted Answer

Bản chất vấn đề
Khi giải quyết các bài toán Dynamic Programming đa biến trạng thái (ví dụ: dp(i, j, k)), lập trình viên thường dùng mảng đa chiều hoặc đối tượng băm (Hash Map / Dictionary). Trong các ứng dụng chạy dài hạn như Microservices hoặc Web Servers, nếu bộ nhớ Cache này không được dọn dẹp hoặc không giới hạn kích thước, nó sẽ gây ra hiện tượng rò rỉ bộ nhớ (Memory Leak), làm đầy Heap Memory của ứng dụng.
Giải pháp kỹ thuật

Sử dụng cấu trúc khóa chuỗi (String Serialization): Khi có nhiều biến trạng thái, gom các biến thành một khóa chuỗi duy nhất để lưu vào Hash Map chuẩn.
Áp dụng chiến lược giới hạn Cache (LRU Cache): Đối với các hàm tính toán động không cố định phạm vi, nên sử dụng thuật toán Least Recently Used (LRU) để tự động loại bỏ các trạng thái cũ ít được truy cập.
Làm sạch Cache theo phiên làm việc (Request-scoped Cache): Đảm bảo mảng Memoization chỉ tồn tại trong phạm vi của một phiên xử lý yêu cầu (Request lifecycle) và bị hủy khi request kết thúc, thay vì dùng biến toàn cục (Global variable).

Ví dụ minh họa (Sử dụng Map với khóa chuỗi trong phạm vi Request)
function solveProblem(params) {
    const memo = new Map();

function dp(i, j, remainingCapacity) {
        const key = `${i}-${j}-${remainingCapacity}`;
        if (memo.has(key)) {
            return memo.get(key);
        }

// Logic tính toán trạng thái...
        let result = /* tính toán */;

memo.set(key, result);
        return result;
    }

return dp(params.i, params.j, params.capacity);
    // Biến memo sẽ được Garbage Collection thu hồi ngay khi hàm solveProblem kết thúc
}
Kinh nghiệm thực chiến cho Junior

Tuyệt đối tránh khai báo biến Memoization ở phạm vi Global (Toàn cục) trong các ứng dụng Web Server (như Express.js, Spring Boot) trừ khi đó là dữ liệu tĩnh Read-only.
Luôn kiểm tra biểu đồ giám sát bộ nhớ (Memory Profiling) khi viết các hàm đệ quy có Memoization để đảm bảo không bị tích lũy rác theo thời gian.

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 dynamic programming liên quan cùng chủ đề