Konsep Dynamic Programming

Dynamic programming (DP) adalah paradigma algoritma yang menyelesaikan masalah dengan memecahnya menjadi sub-masalah yang lebih kecil, lalu menyimpan hasil sub-masalah tersebut agar tidak dihitung ulang. DP menjadi senjata utama ketika rekursi naif terlalu lambat karena mengulang perhitungan yang sama berulang kali. Pada Chapter ini kita akan memahami dua properti inti yang membuat sebuah masalah bisa diselesaikan dengan DP, membandingkan DP dengan divide & conquer serta greedy, dan melihat contoh sederhana yang memperjelas kapan DP menjadi pilihan yang tepat.

Dua Properti Inti DP #

Sebuah masalah cocok diselesaikan dengan DP bila memenuhi dua properti berikut:

1. Optimal substructure: solusi optimal dari masalah dapat dibangun dari solusi optimal sub-masalahnya.
2. Overlapping subproblems: sub-masalah yang sama muncul berulang kali selama komputasi.

Tanpa properti pertama, kita tidak bisa menyusun solusi dari bagian-bagiannya. Tanpa properti kedua, menyimpan hasil tidak memberi penghematan apa pun.

Optimal Substructure #

Properti ini menyatakan: solusi optimal untuk masalah ukuran n mengandung solusi optimal untuk sub-masalah yang lebih kecil.

Contoh klasik: shortest path. Jalur terpendek dari A ke C yang melewati B pasti terdiri dari jalur terpendek A → B dan jalur terpendek B → C. Bila ada sub-jalur yang tidak optimal, kita bisa menggantinya dengan yang optimal dan memperbaiki total — kontradiksi.

Contoh lawan: longest simple path pada graph berbobot. Sub-jalur terpanjang belum tentu bisa digabungkan menjadi jalur terpanjang menyeluruh karena bisa terjadi siklus. Inilah sebabnya masalah ini tidak memiliki optimal substructure dan DP tidak bisa diterapkan secara langsung.

Overlapping Subproblems #

Properti ini menyatakan: jumlah sub-masalah yang berbeda jauh lebih kecil daripada jumlah total pemanggilan rekursif.

Mari kita lihat Fibonacci fib(n) = fib(n-1) + fib(n-2):

Perhatikan fib(3) dan fib(2) muncul beberapa kali. Hanya ada n+1 sub-masalah unik (fib(0) sampai fib(n)), tetapi rekursi naif melakukan ~φ^n panggilan. Inilah sumber inefisiensi yang DP eliminasi.

DP vs Divide & Conquer vs Greedy #

Perbedaan kunci:

• Divide & Conquer: setiap sub-masalah independen (misal merge sort — bagian kiri dan kanan tidak berbagi data). Tidak perlu menyimpan hasil.
• Greedy: mengambil keputusan lokal terbaik tanpa pernah kembali. Cepat (sering O(n log n)) tetapi tidak selalu optimal.
• DP: menyimpan hasil semua sub-masalah, secara konseptual “mencoba semua pilihan” tetapi menghindari recomputation.

Mekanisme DP: Dua Pendekatan #

DP memiliki dua gaya implementasi:

1. Top-down (memoization): tulis rekursi natural, simpan hasil di cache (array/map) sebelum return. Sub-masalah dievaluasi hanya saat dibutuhkan.
2. Bottom-up (tabulation): bangun tabel dari sub-masalah terkecil ke terbesar secara iteratif. Seringkali lebih cepat karena menghindari overhead pemanggilan fungsi.

Kedua pendekatan menghasilkan kompleksitas asimptotik yang sama, namun konstanta faktor dan kemudahan implementasi bisa berbeda tergantung masalah. Bab-bab berikutnya akan membahas masing-masing secara mendalam.

Kode: Fibonacci Naif vs DP #

Kode berikut membandingkan Fibonacci naif (tanpa DP) dengan versi yang menyimpan hasil (DP):

#include <iostream>
#include <vector>

long long g_naive_calls = 0;
long long g_dp_calls = 0;

long long fib_naive(int n) {
    ++g_naive_calls;
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib_naive(n - 1) + fib_naive(n - 2);
}

long long fib_dp(int n, std::vector<long long>& memo) {
    ++g_dp_calls;
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib_dp(n - 1, memo) + fib_dp(n - 2, memo);
    return memo[n];
}

int main() {
    int n = 35;

    g_naive_calls = 0;
    long long r1 = fib_naive(n);
    std::cout << "Naif    : fib(" << n << ") = " << r1
              << " | panggilan: " << g_naive_calls << '\n';

    std::vector<long long> memo(n + 1, -1);
    g_dp_calls = 0;
    long long r2 = fib_dp(n, memo);
    std::cout << "DP/memo : fib(" << n << ") = " << r2
              << " | panggilan: " << g_dp_calls << '\n';
    return 0;
}

Output yang Dihasilkan:

Naif    : fib(35) = 9227465 | panggilan: 29860703
DP/memo : fib(35) = 9227465 | panggilan: 69

1. Baris if (memo[n] != -1) return memo[n];: cek apakah sub-masalah fib(n) sudah pernah dihitung. Bila sudah, kembalikan langsung tanpa rekursi.
2. Baris memo[n] = fib_dp(n - 1, memo) + fib_dp(n - 2, memo);: hitung sekali, simpan ke memo. Inilah inti DP — tidak ada recomputation.
3. Perbandingan panggilan: naif melakukan ~29,9 juta panggilan, DP hanya 69 panggilan. Penghematan ~430.000×.
4. Hasil identik: kedua pendekatan menghasilkan 9227465 — DP tidak mengubah jawaban, hanya mempercepat.

Kapan Tidak Menggunakan DP #

• Tidak ada overlapping subproblems: misal binary search — setiap sub-masalah unik. DP tidak membantu.
• State space terlalu besar: bila tabel DP berukuran n^5 atau lebih, DP tidak praktis meski teoritis polinomial.
• Sub-masalah independen: gunakan divide & konquer saja — lebih sederhana.

Ringkasan #

• DP butuh dua properti: optimal substructure dan overlapping subproblems.
• Berbeda dari divide & conquer (sub-masalah independen) dan greedy (tidak backtrack).
• Dua implementasi: top-down (memoization) dan bottom-up (tabulation).
• Fibonacci contoh sederhana: naif O(φ^n) → DP O(n). Penghematan bisa ratusan ribu kali.
• Bab berikutnya akan membahas memoization dan tabulation secara mendalam.