Greedy pada Bab sebelumnya mengambil keputusan lokal tanpa pernah menghitung ulang. Sekarang kita menghadapi keluarga persoalan yang strukturnya berbeda: rekursi yang tampak wajar justru menghitung subpersoalan yang sama berulang kali, hingga waktu eksekusi melonjak eksponensial. Dynamic programming (DP) menyembuhkan pemborosan itu dengan satu ide sederhana: simpan hasil subpersoalan yang sudah dihitung, lalu pakai kembali saat dibutuhkan. Bab ini membuktikan efeknya dengan penghitung panggilan yang eksak, membedah dua gaya implementasi — top-down memoization dan bottom-up tabulation — lalu menerapkannya pada persoalan rod cutting dengan tabel yang bisa kita amati baris demi baris.

Subpersoalan yang Sama Dihitung Berulang Kali #

Mari kita mulai dari bukti terukur. Fibonacci rekursif naif terlihat tidak berbahaya, tetapi setiap panggilan memecah diri menjadi dua panggilan baru tanpa memeriksa apakah hasilnya pernah dihitung sebelumnya. Program berikut memasang penghitung statis pada versi naif dan versi dengan memo, lalu membandingkan keduanya untuk fib(30):

java FibonacciMemo.java 
public class FibonacciMemo {

    // Penghitung panggilan untuk naive dan memo versi.
    static long panggilNaive = 0;
    static long panggilMemo = 0;

    // Versi naive: menghitung ulang subpersoalan yang sama berkali-kali.
    static long fibNaive(int n) {
        panggilNaive++;
        if (n <= 1) {
            return n;
        }
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    // Versi top-down dengan memo: hasil subpersoalan disimpan di array memo.
    static long fibMemo(int n, long[] memo) {
        panggilMemo++;
        if (n <= 1) {
            return n;
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 30;

        System.out.println("=== Naive rekursif vs memoization, fib(" + n + ") ===");
        System.out.println("fibNaive(" + n + ") = " + fibNaive(n));
        System.out.println("Jumlah panggilan naive : " + panggilNaive);
        System.out.println("fibMemo(" + n + ")  = " + fibMemo(n, new long[n + 1]));
        System.out.println("Jumlah panggilan memo  : " + panggilMemo);
        System.out.println();
        System.out.println("Perbandingan panggilan : " + panggilNaive + " vs " + panggilMemo
                + " (sekitar " + (panggilNaive / panggilMemo) + "x lebih banyak)");
    }
}

Output yang Dihasilkan:

text 
=== Naive rekursif vs memoization, fib(30) ===
fibNaive(30) = 832040
Jumlah panggilan naive : 2692537
fibMemo(30)  = 832040
Jumlah panggilan memo  : 59

Perbandingan panggilan : 2692537 vs 59 (sekitar 45636x lebih banyak)

Angka pada output itu layak direnungkan: versi naif memanggil dirinya 2.692.537 kali untuk fib(30), sedangkan versi memo hanya 59 kali — sekitar 45.000x lebih hemat. Pohon rekursi naif mengandung overlapping subproblems: fib(28) dihitung berulang di banyak cabang, fib(27) juga, dan seterusnya ke bawah. Memoization memotong seluruh cabang duplikat itu karena subpersoalan hanya dihitung sekali, kemudian dibaca dari tabel.

Mari kita bedah baris-baris kuncinya:

  1. Baris 5-6 (static long panggilNaive dan panggilMemo): dua penghitung statis dinaikkan setiap kali method terkait dipanggil, sehingga angka pada output mencerminkan jumlah panggilan yang sesungguhnya, bukan perkiraan.
  2. Baris 19-22 (if (memo[n] != 0)): pemeriksaan tabel ini adalah inti DP top-down. Nilai 0 pada array long menandakan sel kosong; jika sel sudah terisi, subpersoalan dijawab langsung tanpa rekursi.
  3. Baris 23 (memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo)): hasil penjumlahan disimpan sebelum dikembalikan. Tanpa baris penyimpanan ini, program kembali menjadi versi naif meskipun parameter memo tetap diteruskan.
  4. Baris 40 (new long[n + 1]): tabel dialokasikan seukuran n + 1 karena nilai fibonacci yang dibutuhkan berkisar dari fib(0) hingga fib(n). Java otomatis mengisi array long dengan nol, yang sekaligus menjadi penanda sel kosong.

Bottom-Up dengan Tabulation pada Rod Cutting #

Gaya kedua membalik arah: alih-alih turun dari fib(30) lalu mengisi tabel saat dibutuhkan, kita mengisi tabel dari sel terkecil hingga terbesar. Persoalan rod cutting cocok untuk demonstrasi: sebuah besi panjang 8 meter harus dipotong menjadi beberapa bagian yang memaksimalkan pendapatan, dengan daftar harga per panjang yang tidak sebanding lurus. Program berikut mengisi tabel pendapatan[k] secara bottom-up sekaligus merekam potongan pertama agar solusi optimal dapat direkonstruksi:

java PotongBesi.java 
public class PotongBesi {

    // Harga jual besi per panjang 1..8 (meter), index 0 tidak dipakai.
    static final int[] HARGA = {0, 1000, 5000, 8000, 9000, 10000, 17000, 17000, 20000};

    public static void main(String[] args) {
        int n = HARGA.length - 1;

        int[] pendapatan = new int[n + 1]; // pendapatan[k] = hasil terbaik untuk besi panjang k
        int[] potonganPertama = new int[n + 1]; // potongan pertama pada solusi terbaik panjang k

        for (int k = 1; k <= n; k++) {
            int terbaik = Integer.MIN_VALUE;
            for (int p = 1; p <= k; p++) {
                int kandidat = HARGA[p] + pendapatan[k - p];
                if (kandidat > terbaik) {
                    terbaik = kandidat;
                    potonganPertama[k] = p;
                }
            }
            pendapatan[k] = terbaik;
        }

        System.out.println("=== Rod cutting bottom-up, panjang total " + n + " meter ===");
        System.out.println("Harga  : " + java.util.Arrays.toString(java.util.Arrays.copyOfRange(HARGA, 1, n + 1)));
        System.out.println();
        System.out.printf("%-9s %-11s%n", "Panjang", "Pendapatan");
        for (int k = 1; k <= n; k++) {
            System.out.printf("%-9d Rp%-10d%n", k, pendapatan[k]);
        }
        System.out.println();
        System.out.println("Rekonstruksi potongan untuk besi 8 meter:");
        int sisa = n;
        while (sisa > 0) {
            System.out.println("  potong " + potonganPertama[sisa] + " meter -> Rp" + HARGA[potonganPertama[sisa]]);
            sisa -= potonganPertama[sisa];
        }
        System.out.println("Total: Rp" + pendapatan[n]);
    }
}

Output yang Dihasilkan:

text 
=== Rod cutting bottom-up, panjang total 8 meter ===
Harga  : [1000, 5000, 8000, 9000, 10000, 17000, 17000, 20000]

Panjang   Pendapatan 
1         Rp1000      
2         Rp5000      
3         Rp8000      
4         Rp10000     
5         Rp13000     
6         Rp17000     
7         Rp18000     
8         Rp22000     

Rekonstruksi potongan untuk besi 8 meter:
  potong 2 meter -> Rp5000
  potong 6 meter -> Rp17000
Total: Rp22000

Tabel pada output memperlihatkan optimal substructure bekerja: pendapatan[8] sebesar Rp22000 terbentuk dari harga potongan 2 meter (Rp5000) ditambah pendapatan[6] (Rp17000) — solusi panjang 8 memang terbaik bila tersusun dari solusi terbaik panjang 6. Daftar harga yang aneh (besi 6 meter lebih mahal daripada 7 meter) sengaja dipilih agar solusi optimal tidak intuitif: potongan 2+6 mengalahkan membiarkan besi utuh senilai Rp20000.

Bedah baris-per-baris untuk loop utamanya:

  1. Baris 12 (for (int k = 1; k <= n; k++)): loop luar mengisi tabel dari kecil ke besar. Saat menghitung sel k, seluruh sel k - p di bawahnya sudah final — tidak ada perhitungan yang belum selesai dibaca.
  2. Baris 15 (int kandidat = HARGA[p] + pendapatan[k - p]): setiap kandidat memotong p meter pertama, lalu memercayakan sisa k - p meter pada tabel. Harga potongan pertama dibaca dari HARGA[p], sedangkan nilai sisanya dibaca dari pendapatan[k - p].
  3. Baris 17 (potonganPertama[k] = p): kandidat terbaik sengaja direkam agar solusi dapat direkonstruksi. Tanpa array ini kita hanya tahu nilai optimal Rp22000, tanpa tahu bagaimana memotongnya.
  4. Baris 33-38 (loop rekonstruksi): potongan pertama dibaca dari tabel, panjang sisa dikurangi, proses berulang hingga sisa habis. Rekonstruksi berjalan O(n) karena setiap langkah mengurangi sisa.

Memilih Antara Kedua Pendekatan #

Kedua gaya menghasilkan kompleksitas yang sama — O(n) ruang dan O(n) waktu untuk fibonacci, O(n²) waktu untuk rod cutting — tetapi karakter implementasinya berbeda:

AspekTop-Down (Memoization)Bottom-Up (Tabulation)
Arah pengisian tabelMenurun dari persoalan utamaMenaik dari kasus dasar
Subpersoalan dihitungHanya yang benar-benar dibutuhkanSemua, termasuk yang tak terpakai
Bentuk kodeRekursi + cek tabelLoop bersarang eksplisit
RisikoStackOverflow pada n besarKetergantungan urutan sel harus benar

Top-down menang ketika hanya sebagian kecil subpersoalan yang relevan — misalnya persoalan dengan status jarang tercapai. Bottom-up menang ketika kita ingin kode bebas rekursi, urutan pengisian mudah dibuktikan, dan tabel dapat dipangkas menjadi beberapa variabel (misalnya cukup dua nilai terakhir untuk fibonacci).

Dynamic programming menuntaskan kisah algoritma klasik pada Section ini — dari kompleksitas, struktur data, sorting, searching, hingga greedy. Satu wilayah besar masih tersisa: persoalan yang hidup pada jaringan hubungan antar entitas. Bab berikutnya masuk ke graph algorithm — BFS, DFS, dan Dijkstra — tempat ide menyimpan hasil antara (jarak sementara, status kunjungan) kembali muncul dalam wujud berbeda.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

FibonacciMemo.java

Unduh berkas
java 
public class FibonacciMemo {

    // Penghitung panggilan untuk naive dan memo versi.
    static long panggilNaive = 0;
    static long panggilMemo = 0;

    // Versi naive: menghitung ulang subpersoalan yang sama berkali-kali.
    static long fibNaive(int n) {
        panggilNaive++;
        if (n <= 1) {
            return n;
        }
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    // Versi top-down dengan memo: hasil subpersoalan disimpan di array memo.
    static long fibMemo(int n, long[] memo) {
        panggilMemo++;
        if (n <= 1) {
            return n;
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 30;

        System.out.println("=== Naive rekursif vs memoization, fib(" + n + ") ===");
        System.out.println("fibNaive(" + n + ") = " + fibNaive(n));
        System.out.println("Jumlah panggilan naive : " + panggilNaive);
        System.out.println("fibMemo(" + n + ")  = " + fibMemo(n, new long[n + 1]));
        System.out.println("Jumlah panggilan memo  : " + panggilMemo);
        System.out.println();
        System.out.println("Perbandingan panggilan : " + panggilNaive + " vs " + panggilMemo
                + " (sekitar " + (panggilNaive / panggilMemo) + "x lebih banyak)");
    }
}

PotongBesi.java

Unduh berkas
java 
public class PotongBesi {

    // Harga jual besi per panjang 1..8 (meter), index 0 tidak dipakai.
    static final int[] HARGA = {0, 1000, 5000, 8000, 9000, 10000, 17000, 17000, 20000};

    public static void main(String[] args) {
        int n = HARGA.length - 1;

        int[] pendapatan = new int[n + 1]; // pendapatan[k] = hasil terbaik untuk besi panjang k
        int[] potonganPertama = new int[n + 1]; // potongan pertama pada solusi terbaik panjang k

        for (int k = 1; k <= n; k++) {
            int terbaik = Integer.MIN_VALUE;
            for (int p = 1; p <= k; p++) {
                int kandidat = HARGA[p] + pendapatan[k - p];
                if (kandidat > terbaik) {
                    terbaik = kandidat;
                    potonganPertama[k] = p;
                }
            }
            pendapatan[k] = terbaik;
        }

        System.out.println("=== Rod cutting bottom-up, panjang total " + n + " meter ===");
        System.out.println("Harga  : " + java.util.Arrays.toString(java.util.Arrays.copyOfRange(HARGA, 1, n + 1)));
        System.out.println();
        System.out.printf("%-9s %-11s%n", "Panjang", "Pendapatan");
        for (int k = 1; k <= n; k++) {
            System.out.printf("%-9d Rp%-10d%n", k, pendapatan[k]);
        }
        System.out.println();
        System.out.println("Rekonstruksi potongan untuk besi 8 meter:");
        int sisa = n;
        while (sisa > 0) {
            System.out.println("  potong " + potonganPertama[sisa] + " meter -> Rp" + HARGA[potonganPertama[sisa]]);
            sisa -= potonganPertama[sisa];
        }
        System.out.println("Total: Rp" + pendapatan[n]);
    }
}