Tóm tắt: Ta chỉ nên dùng cấu trúc dữ liệu để tối ưu quy hoạch động khi bước chuyển trạng thái tương đương với một bài toán truy vấn đoạn quen thuộc.

Giả sử bạn cần tính mảng quy hoạch động (DP) với \(dp[i]\) là chi phí nhỏ nhất để đi đến vị trí \(i\). Từ một vị trí \(j\) bất kỳ trong đoạn \([i-k, i-1]\), bạn có thể nhảy thẳng đến \(i\). Công thức chuyển trạng thái được viết là \(dp[i] = \min(dp[j]) + a[i]\) với mọi \(i-k \le j \le i-1\).

Nếu duyệt lại toàn bộ các vị trí \(j\) cho từng \(i\), bạn mất \(O(k)\) phép so sánh ở mỗi bước. Khi \(n = 10^5\) và \(k = 10^5\), tổng thời gian chạy lên tới \(O(n \cdot k)\) và chắc chắn sẽ bị quá thời gian.

Cấu trúc nào trả lời được truy vấn này? Khi \(i\) tăng dần, đoạn \([i-k, i-1]\) chỉ dịch sang phải một bước: một phần tử cũ ở bên trái bị đẩy ra ngoài, và một giá trị \(dp\) mới được thêm vào bên phải.

Với dạng cửa sổ trượt tịnh tiến này, ta chỉ cần một hàng đợi hai đầu (deque) để lưu các chỉ số \(j\) có \(dp[j]\) tăng dần. Quy trình cập nhật cho mỗi \(i\) gồm 3 bước:

• Rút các chỉ số \(j < i - k\) ra khỏi đầu deque.
• Lấy \(dp[j]\) nhỏ nhất tại đầu deque để tính \(dp[i] = dp[j] + a[i]\).
• Rút các chỉ số ở cuối deque có \(dp[j] \ge dp[i]\), rồi thêm \(i\) vào cuối deque.

Khi gặp một bài quy hoạch động, bạn hãy viết biểu thức phụ thuộc của \(dp[i]\) theo \(j\) ra nháp trước. Nếu vùng \(j\) cần lấy \(\min\), \(\max\) hoặc lấy tổng là một đoạn trượt hoặc một khoảng giá trị liên tục, bạn hãy nghĩ ngay đến việc dùng deque, cây phân đoạn (Segment Tree) hoặc bảng Fenwick thay vì chạy vòng lặp duyệt trâu.