Menentukan State DP

Menentukan state adalah langkah paling kritis dalam merancang solusi DP. State adalah himpunan parameter yang cukup untuk menggambarkan sub-masalah secara lengkap, tanpa perlu tahu “bagaimana kita sampai ke sini”. Pemilihan state yang tepat menentukan kompleksitas waktu dan ruang algoritma. Pada Chapter ini kita akan mempelajari cara berpikir saat merancang state, teknik reduksi dimensi, dan contoh-contoh konkret dari masalah klasik DP.

Aturan: Apa yang Perlu Diketahui untuk Keputusan Berikutnya? #

Pertanyaan kunci saat merancang state: informasi apa yang harus kita ketahui untuk mengambil keputusan berikutnya? Setiap parameter state harus menjawab bagian dari pertanyaan tersebut. Parameter yang tidak memengaruhi keputusan harus dibuang.

Contoh pertanyaan:

• “Saya di indeks i dengan kapasitas tas w — apakah cukup untuk memutuskan ambil atau lewati item berikutnya?” → state (i, w).
• “Saya sedang mengevaluasi karakter ke-i dari string s dan ke-j dari t — apa lagi yang perlu?” → state (i, j) saja cukup.
• “Saya di posisi i dan boleh melompat ke i+1 atau i+2 — apakah perlu tahu asal?” → tidak perlu, state i saja cukup.

Mekanisme: Dimensi State dan Kompleksitas #

Jumlah state menentukan kompleksitas DP: bila state memiliki k dimensi dengan masing-masing n1, n2, ..., nk nilai, total ada n1 × n2 × ... × nk state. Kompleksitas waktu DP biasanya O(jumlah_state × biaya_transisi_per_state).

Prinsip reduksi dimensi: bila sebuah parameter dapat dihitung dari parameter lain atau tidak mengubah keputusan optimal, hilangkan. Setiap dimensi yang dibuang memperkecil tabel DP secara faktorial.

Contoh: Knapsack 0/1 #

Masalah: diberikan n item dengan bobot w[i] dan nilai v[i], serta kapasitas tas W. Pilih subset dengan total bobot ≤ W sehingga total nilai maksimal.

Pertanyaan keputusan: untuk item berikutnya, ambil atau lewati?

Informasi yang dibutuhkan:

1. Indeks item yang sedang dipertimbangkan (i).
2. Sisa kapasitas tas (w).

State: (i, w) — “saya sedang mempertimbangkan item ke-i dengan sisa kapasitas w”.

Parameter seperti “total nilai sejauh ini” tidak perlu di state karena bukan pertanyaan keputusan — kita akan memaksimalkan nilai sebagai nilai dari dp(i, w), bukan sebagai parameter.

Contoh: Longest Common Subsequence #

Masalah: cari subsequence terpanjang yang sama pada dua string s dan t.

Pertanyaan keputusan: untuk pasangan karakter saat ini, samakan atau skip salah satu?

Informasi yang dibutuhkan:

1. Indeks di string s (i).
2. Indeks di string t (j).

State: (i, j) — “LCS dari s[0..i-1] dan t[0..j-1]”. Tidak perlu tahu LCS yang sudah cocok sejauh ini — itu jadi nilai dp(i, j).

Contoh: Edit Distance #

Masalah: berapa operasi minimum (insert, delete, replace) untuk mengubah s menjadi t?

State: (i, j) — “edit distance dari s[0..i-1] menjadi t[0..j-1]”. Sama seperti LCS, dua indeks cukup.

Kode: Template Knapsack State #

#include <iostream>
#include <vector>

int knapsack(const std::vector<int>& w, const std::vector<int>& v, int W) {
    int n = static_cast<int>(w.size());
    // dp[i][cap] = nilai maksimum mempertimbangkan item 0..i-1 dengan kapasitas cap
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int cap = 0; cap <= W; ++cap) {
            // Opsi 1: lewati item i-1
            dp[i][cap] = dp[i - 1][cap];
            // Opsi 2: ambil item i-1 (jika muat)
            if (w[i - 1] <= cap) {
                dp[i][cap] = std::max(dp[i][cap],
                                     dp[i - 1][cap - w[i - 1]] + v[i - 1]);
            }
        }
    }
    return dp[n][W];
}

int main() {
    std::vector<int> w = {2, 3, 4, 5};
    std::vector<int> v = {3, 4, 5, 6};
    int W = 8;
    std::cout << "Nilai maksimum = " << knapsack(w, v, W) << '\n';
    return 0;
}

Output yang Dihasilkan:

Nilai maksimum = 10

1. Baris std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));: tabel DP 2D berukuran (n+1) × (W+1). Baris i menyimpan keputusan setelah mempertimbangkan item 0..i-1.
2. Baris dp[i][cap] = dp[i - 1][cap];: opsi default — lewati item i-1. Nilai sama dengan sebelumnya.
3. Baris if (w[i - 1] <= cap): cek apakah item muat di kapasitas saat ini.
4. Baris dp[i - 1][cap - w[i - 1]] + v[i - 1]: transisi ambil item — sub-masalah dp[i-1][cap - w[i-1]] ditambah nilai item ini.
5. Hasil 10: item dengan bobot (3, 5) dan nilai (4, 6) → total bobot 8, nilai 10. Optimal.

Reduksi Dimensi: Prinsip dan Contoh #

Beberapa parameter bisa dihilangkan dengan transformasi masalah. Contoh:

Subset sum: “Apakah ada subset dengan total = K?” — state natural (i, s) = “apakah ada subset dari item 0..i-1 dengan total s?”. Total state n × K. Bila K besar (misal 10^9) DP tidak praktis — harus pakai meet-in-the-middle.

Coin change minimum koin: state (amount) saja cukup karena koin boleh diulang. Tidak perlu indeks koin karena urutan tidak penting.

State Berdimensi Banyak: Hati-hati Curse of Dimensionality #

Kompleksitas DP tumbuh eksponensial terhadap dimensi state:

Untuk state dengan dimensi ≥ 4, pertimbangkan:

• Apakah ada parameter yang bisa direduksi?
• Apakah masalah bisa dipecah menjadi DP yang lebih kecil?
• Apakah ada struktur khusus (monoton, tree, interval) yang bisa dieksploitasi?

Ringkasan #

• State = himpunan parameter minimum untuk mengambil keputusan berikutnya.
• Tanya: “informasi apa yang dibutuhkan?” — buang parameter yang tidak memengaruhi keputusan.
• Jumlah state menentukan kompleksitas waktu: O(jumlah_state × biaya_transisi).
• Reduksi dimensi: bila urutan parameter tidak penting, gabungkan.
• Hati-hati curse of dimensionality: state ≥ 4D sering tidak praktis.