Rangkuman: Dynamic Programming

1. Pengertian

Dynamic Programming (DP) adalah sebuah teknik optimasi matematis dan metode pemrograman komputer. Ini adalah paradigma desain algoritma yang digunakan untuk memecahkan masalah kompleks dengan memecahnya menjadi sub-masalah yang lebih sederhana dan tumpang tindih. Hasil dari sub-masalah yang sudah dipecahkan disimpan (memoized) untuk menghindari perhitungan berulang.

DP sangat efektif ketika masalah menunjukkan dua karakteristik utama: **Optimal Substructure** dan **Overlapping Subproblems**.

2. Dua Karakteristik Kunci

• Optimal Substructure (Struktur Optimal Sub-masalah):

  Solusi optimal dari masalah besar dapat dibangun dari solusi optimal sub-masalahnya. Artinya, jika kita tahu solusi terbaik untuk bagian-bagian kecil, kita bisa menggabungkannya untuk mendapatkan solusi terbaik masalah keseluruhan.

• Overlapping Subproblems (Sub-masalah Tumpang Tindih):

  Ketika memecahkan masalah besar, algoritma yang efisien akan menemukan sub-masalah yang sama berulang kali. DP menyimpan solusi dari sub-masalah ini di memori (misalnya, dalam tabel atau array) agar tidak perlu dihitung ulang.

3. Pendekatan Implementasi

Ada dua pendekatan utama untuk mengimplementasikan solusi Dynamic Programming:

a. Memoization (Top-Down)

• Pendekatan rekursif.
• Dimulai dari masalah besar dan memecahnya menjadi sub-masalah.
• Solusi dari sub-masalah disimpan (memoized) saat pertama kali dihitung. Jika sub-masalah yang sama muncul lagi, hasilnya langsung diambil dari penyimpanan.
• Mirip dengan rekursi murni, tetapi dengan "cache" hasil.

b. Tabulation (Bottom-Up)

• Pendekatan iteratif.
• Dimulai dengan menyelesaikan sub-masalah terkecil terlebih dahulu.
• Secara iteratif membangun solusi untuk sub-masalah yang lebih besar berdasarkan solusi sub-masalah yang lebih kecil yang sudah dihitung.
• Biasanya melibatkan pengisian tabel secara sistematis.

4. Contoh Algoritma Dynamic Programming

a. Deret Fibonacci

Menghitung $F(N)$ (bilangan Fibonacci ke-N).

• Masalah Rekursif Murni (tanpa DP): Sangat tidak efisien karena menghitung ulang banyak $F(k)$ yang sama berulang kali. Kompleksitas $O(2^N)$.
• Dengan DP (Memoization/Tabulation):
  • $F(N) = F(N-1) + F(N-2)$
  • Kita menyimpan $F(0), F(1), \dots, F(N-1)$ untuk menghitung $F(N)$.
  • Kompleksitas Waktu: $O(N)$
  • Kompleksitas Ruang: $O(N)$

b. Longest Common Subsequence (LCS)

Mencari urutan karakter terpanjang yang sama yang ada di dua string (tidak harus berurutan). Misal: LCS dari "AGGTAB" dan "GXTXAYB" adalah "GTAB".

• Masalah ini memiliki Overlapping Subproblems dan Optimal Substructure.
• Biasanya diselesaikan dengan Tabulation (mengisi matriks).
• Kompleksitas Waktu: $O(M \times N)$, di mana M dan N adalah panjang string.

c. 0/1 Knapsack Problem

Mencari kombinasi item dengan nilai total maksimum yang bisa dimasukkan ke dalam tas dengan kapasitas terbatas, di mana item tidak bisa dipecah (hanya bisa diambil utuh atau tidak sama sekali).

• Sering diselesaikan dengan Tabulation (mengisi tabel `dp[i][w]` yang menunjukkan nilai maksimum dengan `i` item dan kapasitas `w`).
• Kompleksitas Waktu: $O(N \times W)$, di mana $N$ adalah jumlah item dan $W$ adalah kapasitas tas.

5. Keuntungan & Kerugian

Keuntungan:

• Mengoptimalkan algoritma eksponensial menjadi polinomial (pseudo-polinomial).
• Menghindari perhitungan ulang yang tidak perlu.

Kerugian:

• Bisa membutuhkan banyak ruang memori untuk menyimpan solusi sub-masalah.
• Tidak semua masalah cocok untuk DP (harus memiliki struktur optimal dan sub-masalah tumpang tindih).
• Implementasi bisa lebih kompleks daripada rekursi sederhana.