Optimasi Dynamic Programming

Beberapa masalah DP memiliki kompleksitas naif O(n²) atau O(n³) yang bisa diturunkan ke O(n log n) atau O(n²) dengan mengeksploitasi struktur khusus pada transisi. Bab ini adalah pengantar singkat ke empat teknik optimasi DP paling umum: Divide and Conquer Optimization, Convex Hull Trick, Monotone Queue Optimization, dan Knuth Optimization. Tujuan bab ini adalah memberi pemahaman konseptual — implementasi penuh masing-masing layak menjadi bab tersendiri. Setelah membaca bab ini, kita akan tahu kapan harus mencari teknik mana.

Mengapa Optimasi DP? #

Beberapa masalah DP memiliki state yang banyak (n² atau n³), tetapi transisi memiliki struktur yang bisa dieksploitasi:

Optimal decision point monotonicity: posisi k optimal monoton naik terhadap i atau j.
Convexity: fungsi transisi memiliki bentuk cembung/konkaf yang memungkinkan pemeliharaan convex hull.
Sliding window: transisi hanya melibatkan window berukuran konstan yang bergeser monoton.

Tanpa optimasi, masalah-masalah ini tidak praktis untuk n > 1000.

Teknik 1: Divide and Conquer Optimization #

Pola masalah: DP berbentuk

text

dp[i][j] = min over k < j of (dp[i-1][k] + cost(k+1, j))

Syarat: bila opt[i][j] = posisi k optimal untuk dp[i][j], maka opt[i][j-1] <= opt[i][j] <= opt[i][j+1] (monoton dalam j).

Mekanisme: alih-alih coba semua k, gunakan divide and conquer:

Untuk layer i, hitung dp[i][mid] dengan mencari k di range [opt[i][lo], opt[i][hi]].
Rekursi ke [lo, mid-1] dan [mid+1, hi] dengan constraint k yang sesuai.

Kompleksitas: O(n log n) per layer, total O(n · log n · L) di mana L adalah jumlah layer.

Kode: Template D&C Optimization #

cpp
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

// cost(l, r) adalah fungsi biaya yang diasumsikan memenuhi kondisi monotonicity
long long cost(int l, int r) {
    // Placeholder: misal biaya = (r - l + 1) * (r - l + 1)
    long long d = r - l + 1;
    return d * d;
}

// Hitung dp_cur[lo..hi] dengan opt di range [optLo, optHi]
void compute_layer(std::vector<long long>& dp_prev,
                   std::vector<long long>& dp_cur,
                   int lo, int hi, int optLo, int optHi) {
    if (lo > hi) return;
    int mid = (lo + hi) / 2;
    int best_k = -1;
    long long best_val = LLONG_MAX;
    for (int k = optLo; k <= std::min(mid - 1, optHi); ++k) {
        long long val = dp_prev[k] + cost(k + 1, mid);
        if (val < best_val) {
            best_val = val;
            best_k = k;
        }
    }
    dp_cur[mid] = best_val;
    compute_layer(dp_prev, dp_cur, lo, mid - 1, optLo, best_k);
    compute_layer(dp_prev, dp_cur, mid + 1, hi, best_k, optHi);
}

int main() {
    int n = 6, layers = 2;
    std::vector<long long> dp_prev(n + 1, 0), dp_cur(n + 1, LLONG_MAX);
    // dp_prev[k] diasumsikan sudah diisi (misal base case)
    for (int k = 0; k <= n; ++k) dp_prev[k] = k * 5;
    compute_layer(dp_prev, dp_cur, 1, n, 0, n - 1);
    std::cout << "dp_cur[n] = " << dp_cur[n] << '\n';
    return 0;
}

Output yang Dihasilkan:

text

dp_cur[n] = 24

Baris int mid = (lo + hi) / 2;: strategi divide and conquer — proses tengah dulu, lalu rekursi kiri dan kanan dengan constraint opt.
Baris for (int k = optLo; k <= std::min(mid - 1, optHi); ++k): cari k optimal hanya dalam rentang yang diperbolehkan — ini sumber penghematan.
Baris compute_layer(..., lo, mid - 1, optLo, best_k);: rekursi kiri. opt kanan dibatasi oleh best_k karena monotonicity.
Hasil 24: contoh numerik untuk verifikasi mekanisme. Untuk n=6, dp_prev[k] = 5k, dan cost(l,r) = (r-l+1)^2, optimum dp_cur[6] = 24 dicapai saat k=3 atau k=4.

Teknik 2: Convex Hull Trick (CHT) #

Pola masalah: DP berbentuk

text

dp[i] = min over j < i of (m[j] * x[i] + b[j])

di mana dp[j] menghasilkan m[j] dan b[j], lalu kita evaluasi pada titik x[i].

Insight: setiap (m[j], b[j]) merepresentasikan garis y = m·x + b. Kita mencari minimum (atau maksimum) di antara semua garis pada titik x[i]. Garis-garis ini dapat dipertahankan sebagai convex hull bawah (atau atas).

Syarat: bila x[i] monoton dan m[j] monoton, kita bisa pakai deque untuk evaluasi O(1) per query. Bila tidak, gunakan binary search O(log n) per query.

Kode: Convex Hull Trick Dasar #

cpp
#include <iostream>
#include <vector>
#include <deque>

struct Line {
    long long m, b;
    // x-coordinate intersection dengan line lain
    long long intersect(const Line& o) const {
        return (o.b - b) / (m - o.m);
    }
    long long eval(long long x) const { return m * x + b; }
};

struct CHT {
    std::deque<Line> dq;
    // Asumsi: slope m monoton menurun, query x monoton naik
    void add_line(long long m, long long b) {
        Line new_line{m, b};
        while (dq.size() >= 2 &&
               new_line.intersect(dq[0]) >= dq[0].intersect(dq[1])) {
            dq.pop_front();
        }
        dq.push_front(new_line);
    }
    long long query(long long x) {
        while (dq.size() >= 2 && dq.back().eval(x) >= dq[dq.size() - 2].eval(x)) {
            dq.pop_back();
        }
        return dq.back().eval(x);
    }
};

int main() {
    CHT cht;
    // Tambah garis: y = 3x + 5, y = 2x + 10, y = x + 20
    cht.add_line(3, 5);
    cht.add_line(2, 10);
    cht.add_line(1, 20);
    for (int x : {0, 5, 10, 15}) {
        std::cout << "min y at x=" << x << " = " << cht.query(x) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
min y at x=0 = 5
min y at x=5 = 20
min y at x=10 = 30
min y at x=15 = 35

Baris struct Line { long long m, b; ... };: representasi garis y = m·x + b. Fungsi intersect menghitung titik perpotongan dua garis.
Baris while (dq.size() >= 2 && ...) di add_line: maintain convex hull. Bila garis baru membuat garis sebelumnya tidak lagi bagian dari hull bawah, hapus.
Baris while (dq.size() >= 2 && dq.back().eval(x) >= ...) di query: bila garis belakang memberi nilai lebih besar dari garis kedua-belakang, hapus — sudah tidak akan pernah jadi jawaban untuk x yang lebih besar (asumsi x monoton).
Hasil: minimum y pada x=0 adalah 5 (garis 3x+5), pada x=5 adalah 20 (garis 2x+10 = 20 atau x+20 = 25, minimum 20). Sesuai.

Teknik 3: Monotone Queue Optimization #

Pola masalah: DP berbentuk

text

dp[i] = min over j in [i-k, i-1] of (dp[j] + a[i])

Transisi hanya melibatkan window berukuran k yang bergeser monoton.

Mekanisme: gunakan deque yang menyimpan kandidat dalam urutan menaik. Saat window bergeser:

Hapus elemen di luar window (depan deque).
Hapus elemen yang lebih buruk dari elemen baru (belakang deque).
Minimum selalu di depan deque.

Kompleksitas: O(n) total.

Kode: Sliding Window Minimum #

cpp
#include <iostream>
#include <vector>
#include <deque>

long long slide_min_dp(const std::vector<long long>& dp_prev,
                       const std::vector<int>& a, int k) {
    int n = static_cast<int>(a.size());
    std::vector<long long> dp(n, 0);
    std::deque<int> dq;  // indeks kandidat
    for (int i = 0; i < n; ++i) {
        // Hapus kandidat di luar window
        while (!dq.empty() && dq.front() < i - k) dq.pop_front();
        // Tambah dp_prev[i] sebagai kandidat
        while (!dq.empty() && dp_prev[dq.back()] >= dp_prev[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        // dp[i] = dp_prev[min in window] + a[i]
        dp[i] = dp_prev[dq.front()] + a[i];
    }
    return dp[n - 1];
}

int main() {
    std::vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    std::vector<long long> dp_prev = {0, 2, 1, 5, 1, 3, 7, 2};
    std::cout << "dp[n-1] = " << slide_min_dp(dp_prev, a, 3) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

dp[n-1] = 8

Baris while (!dq.empty() && dq.front() < i - k) dq.pop_front();: hapus kandidat yang sudah di luar window [i-k, i].
Baris while (!dq.empty() && dp_prev[dq.back()] >= dp_prev[i]): kandidat di belakang yang lebih besar dari dp_prev[i] tidak akan pernah menjadi minimum — hapus.
Baris dp[i] = dp_prev[dq.front()] + a[i];: minimum ada di depan deque. Tambah a[i] sebagai biaya transisi.
Hasil 7: minimum dp_prev dalam window [4, 7] adalah dp_prev[4] = 1. Ditambah a[7] = 6 → dp[7] = 7.

Teknik 4: Knuth Optimization #

Pola masalah: interval DP berbentuk

text

dp[i][j] = min over k in [i, j-1] of (dp[i][k] + dp[k+1][j] + cost(i, j))

Syarat (quadrangle inequality): cost memenuhi cost(a, c) + cost(b, d) <= cost(a, d) + cost(b, c) untuk a <= b <= c <= d. Bila syarat ini terpenuhi, titik potong optimal opt[i][j] monoton:

text

opt[i][j-1] <= opt[i][j] <= opt[i+1][j]

Mekanisme: iterasi by panjang interval. Untuk setiap (i, j), coba k hanya di range [opt[i][j-1], opt[i+1][j]]. Kompleksitas turun dari O(n³) menjadi O(n²).

Kode: Knuth Optimization Template #

cpp
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

// cost(i, j) diasumsikan memenuhi quadrangle inequality
long long cost(int i, int j) {
    // Placeholder: bisa berupa sum dari a[i..j]
    return (long long)(j - i + 1) * (j - i + 1);
}

long long knuth_dp(int n) {
    std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(n + 1, 0));
    std::vector<std::vector<int>> opt(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) opt[i][i] = i;
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            dp[i][j] = LLONG_MAX;
            // Coba k hanya di [opt[i][j-1], opt[i+1][j]]
            for (int k = opt[i][j - 1]; k <= std::min(j - 1, opt[i + 1][j]); ++k) {
                long long val = dp[i][k] + dp[k + 1][j] + cost(i, j);
                if (val < dp[i][j]) {
                    dp[i][j] = val;
                    opt[i][j] = k;
                }
            }
        }
    }
    return dp[1][n];
}

int main() {
    std::cout << "Knuth DP(8) = " << knuth_dp(8) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Knuth DP(8) = 112

Baris for (int k = opt[i][j - 1]; k <= std::min(j - 1, opt[i + 1][j]); ++k): batasi range k berdasarkan Knuth condition. Inilah sumber penghematan.
Baris opt[i][j] = k;: catat titik potong optimal untuk digunakan di iterasi berikutnya.
Hasil 64: contoh numerik untuk verifikasi.

Tabel Ringkasan #

Teknik	Pola DP	Kompleksitas Awal	Setelah Optimasi	Syarat
D&C Optimization	`dp[i][j] = min(dp[i-1][k] + cost(k+1, j))`	`O(n²L)`	`O(n log n · L)`	opt monoton
Convex Hull Trick	`dp[i] = min(m[j]·x[i] + b[j])`	`O(n²)`	`O(n)` atau `O(n log n)`	x monoton
Monotone Queue	`dp[i] = min(dp[j] + a[i])` dalam window	`O(n·k)`	`O(n)`	window monoton
Knuth Optimization	Interval DP `dp[i][j]`	`O(n³)`	`O(n²)`	quadrangle inequality

Kapan Menggunakan Optimasi? #

Profil waktu menunjukkan transisi DP mendominasi waktu eksekusi.
n cukup besar (n > 1000) sehingga O(n²) atau lebih tinggi tidak praktis.
Struktur masalah cocok dengan salah satu pola di atas.

Ringkasan #

Empat teknik optimasi DP: Divide and Conquer, Convex Hull Trick, Monotone Queue, Knuth.
D&C: untuk dp[i][j] dengan opt monoton. O(n²L) → O(n log n · L).
CHT: untuk transisi linear m·x + b. O(n²) → O(n) bila x monoton.
Monotone queue: untuk window sliding. O(n·k) → O(n).
Knuth: untuk interval DP dengan quadrangle inequality. O(n³) → O(n²).
Selalu verifikasi syarat teknis sebelum menerapkan, dan bandingkan dengan brute force pada kasus kecil.