Divide and conquer pada chapter sebelumnya menuntut subproblem yang saling lepas. Fibonacci melanggarnya dengan elegan: menghitung fib(19) dan fib(18) sama-sama membutuhkan fib(17), sehingga subproblem yang sama dihitung ulang ribuan kali. Dynamic programming (DP) adalah divide and conquer yang diberi ingatan — setiap subproblem dihitung sekali, hasilnya disimpan, dan panggilan berikutnya langsung membaca cache. Chapter ini mengukur selisihnya dalam angka nyata: 21.891 pemanggilan fungsi turun menjadi 39. Setelah itu kita menerapkan pola yang sama pada dua masalah klasik, coin change minimum dan longest increasing subsequence (LIS), yang jawabannya juga kita rekonstruksi — bukan hanya angkanya.

Mengukur Pemborosan Rekursi Polos #

Rekursi Fibonacci polos terlihat polos dan terlihat benar — dan memang benar, hanya saja sangat lambat. Program berikut menghitung fib(20) dengan tiga cara pada definisi yang sama, sembari menghitung berapa kali setiap fungsi dipanggil:

cpp 
// Dynamic programming: memoization, tabulation, coin change min, dan LIS.
#include <iostream>
#include <vector>

// Rekursi polos: subproblem yang sama dihitung berulang-ulang.
long long fibPolos(int n, long long& panggilan) {
    ++panggilan;
    if (n <= 1) return n;
    return fibPolos(n - 1, panggilan) + fibPolos(n - 2, panggilan);
}

// Memoization (top-down): hasil disimpan, panggilan ulang langsung kembali.
long long fibMemo(int n, std::vector<long long>& memo, long long& panggilan) {
    ++panggilan;
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // cache hit
    return memo[n] = fibMemo(n - 1, memo, panggilan) +
                     fibMemo(n - 2, memo, panggilan);
}

// Tabulation (bottom-up): isi tabel dari kasus terkecil, tanpa rekursi.
long long fibTabulasi(int n) {
    std::vector<long long> tabel(static_cast<std::size_t>(n) + 1);
    tabel[0] = 0;
    if (n >= 1) tabel[1] = 1;
    for (int i = 2; i <= n; ++i) tabel[i] = tabel[i - 1] + tabel[i - 2];
    return tabel[n];
}

// Coin change minimum: tabel[nominal] = koin terkecil utk membentuk nominal.
// sumber[nominal] mencatat koin terakhir yang dipakai, untuk rekonstruksi.
std::vector<int> koinMin(const std::vector<int>& koin, int jumlah,
                         std::vector<int>& sumber) {
    const int BESAR = 1000000;
    std::vector<int> tabel(static_cast<std::size_t>(jumlah) + 1, BESAR);
    sumber.assign(static_cast<std::size_t>(jumlah) + 1, -1);
    tabel[0] = 0;
    for (int nominal = 1; nominal <= jumlah; ++nominal) {
        for (int k : koin) {
            if (k <= nominal && tabel[nominal - k] + 1 < tabel[nominal]) {
                tabel[nominal] = tabel[nominal - k] + 1;
                sumber[nominal] = k;
            }
        }
    }
    return tabel;
}

// LIS O(n^2): panjangDi[i] = LIS terpanjang yang berakhir di indeks i.
std::vector<int> lis(const std::vector<int>& data, int& panjang) {
    int n = static_cast<int>(data.size());
    std::vector<int> panjangDi(n, 1), pendahulu(n, -1);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (data[j] < data[i] && panjangDi[j] + 1 > panjangDi[i]) {
                panjangDi[i] = panjangDi[j] + 1;
                pendahulu[i] = j;
            }
        }
    }
    int akhir = 0;
    for (int i = 1; i < n; ++i) {
        if (panjangDi[i] > panjangDi[akhir]) akhir = i;
    }
    panjang = panjangDi[akhir];
    std::vector<int> urutan;  // rekonstruksi: telusuri pendahulu mundur
    for (int i = akhir; i != -1; i = pendahulu[i]) urutan.push_back(data[i]);
    return std::vector<int>(urutan.rbegin(), urutan.rend());
}

void cetakVektor(const std::vector<int>& data) {
    for (std::size_t i = 0; i < data.size(); ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << data[i];
    }
}

int main() {
    // Fibonacci tiga cara pada n yang sama.
    long long polos = 0, memo = 0;
    std::vector<long long> cache(21, -1);
    long long a = fibPolos(20, polos);
    long long b = fibMemo(20, cache, memo);
    long long c = fibTabulasi(20);
    std::cout << "fib(20):\n";
    std::cout << "  rekursi polos : " << a << "  (" << polos
              << " pemanggilan fungsi)\n";
    std::cout << "  memoization   : " << b << "  (" << memo
              << " pemanggilan fungsi)\n";
    std::cout << "  tabulation    : " << c
              << "  (20 langkah tabel, tanpa rekursi)\n";

    // Coin change minimum dengan rekonstruksi kombinasi koinnya.
    std::vector<int> koin = {1, 4, 5};
    std::vector<int> sumber;
    std::vector<int> tabel = koinMin(koin, 13, sumber);
    std::cout << "Coin change min, koin {1,4,5}, jumlah 13: " << tabel[13]
              << " koin -> ";
    std::vector<int> kombinasi;
    for (int s = 13; s > 0; s -= sumber[s]) kombinasi.push_back(sumber[s]);
    cetakVektor(kombinasi);
    std::cout << '\n';

    // Longest Increasing Subsequence (LIS) dengan jejak pendahulu.
    std::vector<int> deret = {3, 10, 2, 1, 20, 4, 8, 9};
    int panjang = 0;
    std::vector<int> urutan = lis(deret, panjang);
    std::cout << "LIS dari {3,10,2,1,20,4,8,9}: panjang " << panjang
              << " -> ";
    cetakVektor(urutan);
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
fib(20):
  rekursi polos : 6765  (21891 pemanggilan fungsi)
  memoization   : 6765  (39 pemanggilan fungsi)
  tabulation    : 6765  (20 langkah tabel, tanpa rekursi)
Coin change min, koin {1,4,5}, jumlah 13: 3 koin -> 4 4 5
LIS dari {3,10,2,1,20,4,8,9}: panjang 4 -> 3 4 8 9

Bedah baris penting:

  1. Baris 6-11 (fibPolos): setiap pemanggilan bertambah penghitung; cabang rekursif memanggil n-1 dan n-2 tanpa ingatan apa pun.
  2. Baris 13-19 (fibMemo): tiga baris berbeda dari versi polos — array memo sebagai cache, dan pemeriksaan memo[n] != -1 yang mengembalikan hasil sebelum sempat menghitung ulang.
  3. Baris 22-29 (fibTabulasi): tabel diisi dari tabel[0] dan tabel[1] ke atas; tanpa rekursi, tanpa risiko stack.
  4. Baris 32-46 (koinMin): tabel[nominal] menyimpan koin paling sedikit untuk membentuk nominal; sumber[nominal] mencatat koin terakhir yang dipakai.
  5. Baris 50-70 (lis): panjangDi[i] adalah panjang LIS yang berakhir tepat di indeks i; pendahulu[i] mengingat elemen apa yang mendahuluinya.
  6. Baris 96-99: rekonstruksi coin change — melangkah dari 13 turun lewat sumber sampai 0, mengumpulkan koin di jalan.

Angka pertama pada output adalah bukti pemborosan: fib(20) polos melakukan 21.891 pemanggilan fungsi, padahal hanya ada 21 subproblem unik (fib(0) sampai fib(20)). Hampir semua pekerjaan adalah penghitungan ulang yang bisa dihindari.

Memoization: Top-Down dengan Cache #

Memoization mempertahankan struktur rekursi persis seperti semula, lalu menyisipkan ingatan: sebelum menghitung, periksa cache; setelah menghitung, simpan. Hasilnya pada output: 39 pemanggilan — kira-kira dua kali jumlah subproblem, karena setiap fib(k) kecil dipanggil sekali dari rantai utama dan sekali sebagai panggilan yang langsung kembali dari cache. Biaya memorinya O(n), dan perubahan kodenya minimal — inilah cara tercepat menyelamatkan rekursi yang sudah ada.

Pola top-down seperti ini punya keunggulan praktis: ia hanya menghitung subproblem yang benar-benar dibutuhkan. Pada masalah dengan ruang state besar tetapi jarang tersentuh, memoization bisa jauh lebih hemat daripada mengisi seluruh tabel.

Tabulation: Bottom-Up Tanpa Rekursi #

Tabulation membalik arah: mulai dari kasus terkecil, isi tabel secara berurutan sampai jawaban akhir tercapai. Tidak ada rekursi berarti tidak ada tumpukan pemanggilan yang bisa tumpah pada input besar, dan urutan akses tabel yang berjalan maju ramah terhadap cache. Untuk Fibonacci bahkan tabel penuh pun tidak perlu — dua variabel cukup, karena hanya dua nilai terakhir yang dibutuhkan.

Kapan memilih yang mana? Memoization cepat ditulis dari rekursi yang sudah ada; tabulation lebih cepat dijalankan dan lebih mudah dioptimalkan ruangnya. Keduanya menghasilkan kompleksitas waktu yang sama — yang penting adalah idenya: subproblem dihitung sekali.

Dua DP Klasik: Coin Change Minimum dan LIS #

Dua bagian terakhir program menerapkan resep DP pada masalah yang tidak sepele Fibonacci. Coin change minimum mendefinisikan state sebagai “koin paling sedikit untuk membentuk nominal n”, dengan transisi tabel[n] = 1 + min(tabel[n - k]) untuk setiap koin k. Untuk jumlah 13 dengan koin {1, 4, 5}, tabel tiba pada jawaban 3, dan array sumber memungkinkan rekonstruksi 4 4 5 — bukti bahwa jawabannya masuk akal, bukan angka tanpa wajah. Bandingkan dengan greedy pada chapter Greedy Algorithms yang mengambil tiga koin untuk sistem {4, 3, 1}: DP tidak peduli sistem koinnya kanonik atau tidak, ia memeriksa semua kemungkinan secara sistematis.

LIS (longest increasing subsequence) mencari subderet menaik terpanjang yang boleh tidak berurutan. State-nya lebih halus: panjangDi[i] harus berakhir tepat di indeks i, sehingga transisinya membandingkan semua elemen sebelumnya yang lebih kecil. Pada deret {3, 10, 2, 1, 20, 4, 8, 9}, jawabannya panjang 4 — 3 4 8 9 — yang direkonstruksi lewat jejak pendahulu.

Kompleksitas dan Resep Merancang DP #

MasalahRekursi polosDengan DP
Fibonacci fib(n)O(2^n)O(n)
Coin change min (jumlah n, k koin)eksponensialO(n * k)
LIS (n elemen)eksponensialO(n²)

Langkah merancang solusi DP sendiri bisa dirangkum menjadi empat pertanyaan:

  • State: apa arti satu sel tabel? (“koin minimum untuk nominal n”, “LIS yang berakhir di i”)
  • Transisi: bagaimana sel dihitung dari sel yang lebih kecil?
  • Basis: nilai mana yang diketahui tanpa perhitungan?
  • Urutan: memoization menjawab saat diminta; tabulation mengisi dari basis ke atas.

Sebagai penutup, perhatikan bahwa menyimpan “jawaban terbaik sejauh ini lalu memperbaikinya” bukan milik DP saja. Algoritma jarak terpendek pada graph bekerja dengan ide yang serupa — jarak sementara disimpan dan terus diperbaiki — dan itulah yang kita kerjakan di chapter berikutnya, Graph Algorithms.

Rujukan resmi: std::vector dan std::size_t .