Tối ưu hóa bộ nhớ

Trong quy hoạch động, chúng ta thường dùng bảng hoặc ma trận để lưu lời giải cho các bài toán con. Tuy nhiên, trong một số trường hợp, bảng có thể quá lớn và tiêu tốn quá nhiều bộ nhớ. Đây là lúc kỹ thuật tối ưu hóa bộ nhớ phát huy tác dụng. Các kỹ thuật tối ưu hóa bộ nhớ giúp giảm lượng bộ nhớ cần thiết để giải một bài toán quy hoạch động.

Một kỹ thuật tối ưu hóa bộ nhớ phổ biến là dùng mảng cuộn, còn gọi là mảng trượt. Thay vì lưu toàn bộ bảng, ta chỉ lưu một phần của bảng tại mỗi thời điểm và loại bỏ các giá trị trước đó khi tính các giá trị mới. Cách này có thể giảm đáng kể lượng bộ nhớ cần thiết để giải bài toán.