Deque Optimizasyonu: Dinamik Programlamayı Kuyrukla Hızlandırmak

Dinamik programlama bazen doğru bağıntıyı bulduğumuz anda bitmiş gibi görünür. Sonra zaman karmaşıklığını hesaplarız ve karşımıza tatsız bir $O(nk)$ çıkar! Neyse ki geçişler belirli bir pencere içindeki minimum veya maksimum değere dayanıyorsa, çift uçlu kuyruk yani deque yardımımıza yetişebilir. ``

Temel problem nerede?

Şöyle bir DP bağıntısı düşünelim:

Burada dp[i], önceki en fazla $k$ durumdan birine geçilerek hesaplanıyor. Her i için geriye dönüp $k$ elemanı tek tek incelersek toplam karmaşıklık:

olur. $n$ ve $k$ yüz binler seviyesindeyse programımız kahvesini içip dönmemizi beklemeden zaman aşımına uğrar.

Aslında her adımda ihtiyacımız olan şey bütün pencere değil, yalnızca pencerenin minimum elemanıdır. Ayrıca pencere ilerledikçe bazı eski indeksler geçersiz hâle gelir. Deque, bu iki gereksinimi aynı anda yönetir.

Monoton deque mantığı

Deque içinde DP değerleri artan sırada olacak biçimde indeksler saklarız. Böylece kuyruğun önündeki indeks her zaman geçerli pencerenin minimum değerini temsil eder.

Her yeni i için üç işlem yapılır:

1. Pencerenin dışında kalan indeksleri önden çıkar.
2. Öndeki indeksle dp[i] değerini hesapla.
3. Arkadan, dp[i] değerinden büyük veya eşit değerleri çıkar ve i indeksini ekle.

Neden büyük değerleri siliyoruz? Yeni değer hem daha küçük hem de daha yeni olduğundan, büyük olan eski değer gelecekte hiçbir zaman minimum seçilemez. Kısacası onu kuyrukta tutmak yalnızca kalabalık yapar.

C++ uygulaması

Aşağıdaki kod, her konuma ulaşma maliyetini hesaplar. Bir konuma yalnızca önceki $k$ konumdan geçilebildiğini varsayıyoruz:

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<long long> cost(n), dp(n);
    for (long long &x : cost) cin >> x;

    deque<int> dq;
    dp[0] = cost[0];
    dq.push_back(0);

    for (int i = 1; i < n; ++i) {
        // Artık pencereye ait olmayan indeksleri temizle.
        while (!dq.empty() && dq.front() < i - k)
            dq.pop_front();

        // Öndeki indeks, penceredeki minimum DP değeridir.
        dp[i] = cost[i] + dp[dq.front()];

        // Artan monotonluğu bozan değerleri kaldır.
        while (!dq.empty() && dp[dq.back()] >= dp[i])
            dq.pop_back();

        dq.push_back(i);
    }

    cout << dp[n - 1] << '\n';
}

Kodda her indeks deque’e yalnızca bir kez girer ve en fazla bir kez çıkar. Bazı iterasyonlarda çok sayıda pop_back görülse bile toplam çıkarma sayısı $n$ değerini aşmaz. Bu nedenle işlem maliyeti amortize olarak $O(1)$ kabul edilir.

Ne zaman kullanılabilir?

Deque optimizasyonu her DP bağıntısına sihirli değnek sallamaz. Geçiş kümesi kayan bir aralık olmalı ve bu aralıktan minimum ya da maksimum gibi monoton biçimde yönetilebilen bir sonuç aranmalıdır.

Maksimum arıyorsak yalnızca karşılaştırmaları tersine çevirerek deque’i azalan sırada tutarız. Özetle fikir basittir: Gelecekte kazanma ihtimali kalmayan adayları erkenden ele. Dinamik programlama böylece gereksiz geçmişi taşımayı bırakır ve $O(nk)$ çözüm, zarif bir $O(n)$ algoritmaya dönüşür.