Interval DP

Interval DP adalah pola dynamic programming di mana state berbentuk interval [i, j] (atau [i, j)) pada sebuah array, dan transisi mencoba semua titik potong k antara i dan j untuk menggabungkan solusi sub-interval. Pola ini muncul pada masalah seperti matrix chain multiplication, burst balloons, optimal binary search tree, dan minimum score triangulation. Pada Chapter ini kita akan membedah struktur umum interval DP, urutan iterasi yang benar, dan implementasi untuk matrix chain multiplication.

Aturan: Gabungkan Sub-Interval #

Pada interval DP, kita menyelesaikan masalah pada interval [i, j] dengan mencoba semua titik potong k antara i dan j. Untuk setiap k, masalah dibagi menjadi [i, k] dan [k+1, j] (atau [i, k-1] dan [k, j], tergantung konteks).

State: dp[i][j] — solusi optimal untuk interval [i, j].

Recurrence umum:

text

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

Mekanisme: Urutan Iterasi Penting #

Karena dp[i][j] bergantung pada interval yang lebih pendek, kita harus mengisi tabel berdasarkan panjang interval terlebih dahulu, lalu posisi. Urutan iterasi:

Panjang len = 1 (interval [i, i]) — base case.
Panjang len = 2, 3, ..., n — isi untuk setiap i dengan j = i + len - 1.

flowchart TD A[Iterasi by panjang interval] --> B[len = 1: base case] B --> C[len = 2] C --> D[len = 3] D --> E[...] E --> F[len = n: solusi penuh]

Kompleksitas: O(n³) karena tiga loop bersarang (panjang, posisi i, titik potong k).

Contoh: Matrix Chain Multiplication #

Masalah: kalikan n matriks A_1, A_2, ..., A_n dengan dimensi p_0 × p_1, p_1 × p_2, ..., p_{n-1} × p_n. Perkalian dua matriks a×b dan b×c membutuhkan a·b·c operasi. Cari urutan pengelompokan yang meminimalkan jumlah operasi.

State: dp[i][j] — biaya minimum mengalikan A_i, A_{i+1}, ..., A_j.

Base case: dp[i][i] = 0 (satu matriks, tidak ada perkalian).

Recurrence: untuk setiap k antara i dan j-1, coba bagi menjadi (A_i..A_k) × (A_{k+1}..A_j). Biaya tambahan dari perkalian terakhir adalah p_{i-1} · p_k · p_j.

text

dp[i][j] = min over k in [i, j-1] of:
              dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]

Kode: Matrix Chain Multiplication #

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

long long mcm(const std::vector<int>& p) {
    // p[0..n] dimana matriks A_i berukuran p[i-1] x p[i]
    int n = static_cast<int>(p.size()) - 1;
    std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(n + 1, 0));
    // Iterasi by panjang interval
    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;
            for (int k = i; k < j; ++k) {
                long long cost = dp[i][k] + dp[k + 1][j]
                               + (long long)p[i - 1] * p[k] * p[j];
                dp[i][j] = std::min(dp[i][j], cost);
            }
        }
    }
    return dp[1][n];
}

int main() {
    // 4 matriks: A1 (40x20), A2 (20x30), A3 (30x10), A4 (10x30)
    std::vector<int> p = {40, 20, 30, 10, 30};
    std::cout << "Minimum operasi perkalian = " << mcm(p) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Minimum operasi perkalian = 26000

Baris int n = static_cast<int>(p.size()) - 1;: n matriks perlu n+1 dimensi. p[i-1] × p[i] adalah ukuran A_i.
Baris for (int len = 2; len <= n; ++len): loop panjang interval dari 2 hingga n. Panjang 1 adalah base case (sudah 0).
Baris int j = i + len - 1;: hitung j untuk posisi i. Interval [i, j] berukuran len.
Baris for (int k = i; k < j; ++k): coba setiap titik potong. Bagi [i, j] menjadi [i, k] dan [k+1, j].
Baris dp[i][k] + dp[k + 1][j] + (long long)p[i - 1] * p[k] * p[j]: total = biaya kiri + biaya kanan + biaya menggabungkan dua hasil (matriks p[i-1] × p[k] dikali p[k] × p[j]).
Hasil 26000: urutan optimal ((A1·(A2·A3))·A4). Hitung: A2·A3 (cost 20·30·10=6000), lalu A1·(hasil) (cost 40·20·10=8000), lalu ·A4 (cost 40·10·30=12000). Total 6000+8000+12000=26000.

Rekonstruksi Urutan Optimal #

Simpan titik potong terbaik di tabel s[i][j], lalu traceback secara rekursif:

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

long long g_mcm_calls = 0;  // untuk mencegah warning unused (tidak dipakai)

void print_parens(const std::vector<std::vector<int>>& s, int i, int j) {
    if (i == j) {
        std::cout << "A" << i;
    } else {
        std::cout << "(";
        print_parens(s, i, s[i][j]);
        std::cout << " x ";
        print_parens(s, s[i][j] + 1, j);
        std::cout << ")";
    }
}

int main() {
    std::vector<int> p = {40, 20, 30, 10, 30};
    int n = static_cast<int>(p.size()) - 1;
    std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(n + 1, 0));
    std::vector<std::vector<int>> s(n + 1, std::vector<int>(n + 1, 0));

    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;
            for (int k = i; k < j; ++k) {
                long long cost = dp[i][k] + dp[k + 1][j]
                               + (long long)p[i - 1] * p[k] * p[j];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    s[i][j] = k;
                }
            }
        }
    }
    std::cout << "Minimum = " << dp[1][n] << '\n';
    std::cout << "Urutan: ";
    print_parens(s, 1, n);
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Minimum = 26000
Urutan: ((A1 x (A2 x A3)) x A4)

Baris std::vector<std::vector<int>> s(n + 1, std::vector<int>(n + 1, 0));: tabel s menyimpan titik potong terbaik untuk setiap interval.
Baris s[i][j] = k;: setiap kali dp[i][j] diupdate, catat k yang memberi nilai minimum.
Baris print_parens(s, i, j): rekursi. Bila i == j, cetak nama matriks. Bila tidak, cetak ( lalu kiri + x + kanan + )`.
Hasil ((A1 x (A2 x A3)) x A4): urutan optimal yang menghasilkan 26.000 operasi.

Contoh Lain: Burst Balloons #

Masalah: ada n balon dengan nilai nums[i]. Saat balon i dipecah, kita dapat nums[i-1] * nums[i] * nums[i+1] koin (dengan asumsi nums[-1] = nums[n] = 1). Tentukan urutan pecah untuk maksimumkan total koin.

Insight kunci: pikirkan terbalik — balon mana yang dipecah terakhir dalam interval [i, j]. Saat balon k dipecah terakhir di interval [i, j] (dengan balon i-1 dan j+1 masih ada), koin yang didapat = nums[i-1] * nums[k] * nums[j+1].

text

dp[i][j] = max over k in [i, j] of:
              dp[i][k-1] + dp[k+1][j] + nums[i-1] * nums[k] * nums[j+1]

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

int max_coins(std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    // Tambah sentinel 1 di kiri dan kanan
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    // dp[i][j] = max koin dari pecah semua balon di (i, j) eksklusif
    std::vector<std::vector<int>> dp(n + 2, std::vector<int>(n + 2, 0));
    for (int len = 1; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            for (int k = i; k <= j; ++k) {
                int coins = dp[i][k - 1] + dp[k + 1][j]
                          + nums[i - 1] * nums[k] * nums[j + 1];
                dp[i][j] = std::max(dp[i][j], coins);
            }
        }
    }
    return dp[1][n];
}

int main() {
    std::vector<int> nums = {3, 1, 5, 8};
    std::cout << "Max coins = " << max_coins(nums) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Max coins = 167

Baris nums.insert(nums.begin(), 1); nums.push_back(1);: tambahkan sentinel 1 di kiri dan kanan untuk memudahkan perhitungan balon terakhir.
Baris dp[i][k - 1] + dp[k + 1][j]: sub-interval kiri dan kanan balon k.
Baris nums[i - 1] * nums[k] * nums[j + 1]: koin dari memecah k terakhir. nums[i-1] dan nums[j+1] adalah “tetap” karena semua balon dalam [i, j] sudah dipecah.
Hasil 167: urutan pecah optimal (by value) adalah 1 → 5 → 3 → 8. Pecah balon nilai 1 (koin 3·1·5=15), lalu 5 (koin 3·5·8=120), lalu 3 (koin 1·3·8=24), lalu 8 (koin 1·8·1=8). Total 15+120+24+8=167.

Tabel Kompleksitas Interval DP #

Masalah	Waktu	Ruang	Catatan
Matrix chain multiplication	`O(n³)`	`O(n²)`	Rekonstruksi dengan `s[][]`
Burst balloons	`O(n³)`	`O(n²)`	Inverted thinking
Optimal BST	`O(n³)`	`O(n²)`	Knuth optimization → `O(n²)`
Min score triangulation	`O(n³)`	`O(n²)`	Poligon → interval

Pola Umum Interval DP #

Untuk mengenali masalah yang cocok dengan interval DP:

Masalah melibatkan operasi pada interval/subarray contiguous.
Solusi dapat dibagi menjadi sub-interval kiri dan kanan dengan satu titik potong.
Iterasi harus by panjang interval terlebih dahulu.

Ringkasan #

Interval DP: state dp[i][j], transisi mencoba semua titik potong k.
Urutan iterasi: by panjang interval terlebih dahulu, lalu posisi.
Kompleksitas umum: O(n³) waktu, O(n²) ruang.
Contoh: matrix chain multiplication, burst balloons, optimal BST.
Rekonstruksi solusi: simpan s[i][j] = titik potong terbaik, lalu traceback rekursif.