Làm thế nào để áp dụng kỹ thuật Space Optimization trong Dynamic Programming để giảm thiểu độ phức tạp bộ nhớ cho bài toán tính số Fibonacci hoặc bài toán đường đi ngắn nhất?

Question

Accepted Answer

Bản chất vấn đề
Khi giải quyết các bài toán Dynamic Programming, lập trình viên thường khởi tạo một mảng hai chiều hoặc một mảng một chiều lớn để lưu trữ trạng thái. Tuy nhiên, trong nhiều trường hợp, để tính toán trạng thái hiện tại, chúng ta chỉ cần một vài trạng thái liền kề trước đó (ví dụ như i-1 và i-2).
Giải pháp tối ưu
Thay vì duy trì toàn bộ bảng (table) kích thước O(N) hoặc O(N*M), chúng ta chỉ giữ lại các biến đơn lẻ hoặc mảng kích thước tối thiểu cần thiết để cập nhật vòng lặp tiếp theo.
Ví dụ mã nguồn minh họa
# Tối ưu hóa không gian cho bài toán Fibonacci từ O(N xuống O(1))
def fibonacci_optimized(n):
    if n <= 1:
        return n
    prev_2 = 0
    prev_1 = 1
    current = 0
    for i in range(2, n + 1):
        current = prev_1 + prev_2
        prev_2 = prev_1
        prev_1 = current
    return current
Lưu ý kinh nghiệm thực chiến
Ở cấp độ Junior, việc hiểu cách cắt giảm bộ nhớ từ O(N) xuống O(1) thể hiện tư duy tối ưu phần cứng từ gốc, giúp ứng dụng tránh được lỗi Out of Memory khi xử lý dữ liệu lớn trên các hệ thống Enterprise.

Làm thế nào để áp dụng kỹ thuật Space Optimization trong Dynamic Programming để giảm thiểu độ phức tạp bộ nhớ cho bài toán tính số Fibonacci hoặc bài toán đường đi ngắn nhấ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 dynamic programming liên quan cùng chủ đề