Dynamic Programming — Penjelasan Memoization & Tabulation

Dynamic programming adalah cara menyelesaikan masalah dengan menyimpan jawaban untuk submasalah yang lebih kecil lalu menggunakannya kembali nanti. Metode ini membantu ketika submasalah yang sama muncul lagi dan jawaban akhir dapat dibangun dari jawaban-jawaban kecil tersebut.

Dua gaya utamanya adalah memoization dan tabulation. Memoization menyimpan jawaban selama proses solusi rekursif. Tabulation mengisi jawaban dari bawah ke atas, biasanya dengan array atau tabel.

Kapan dynamic programming bekerja

Dynamic programming berguna ketika dua kondisi terpenuhi.

Pertama, submasalah saling tumpang tindih. Artinya, hasil antara yang sama dibutuhkan lebih dari sekali. Kedua, jawaban yang lebih besar dapat dibangun dari jawaban yang lebih kecil dengan cara yang konsisten.

Jika kondisi-kondisi itu tidak terpenuhi, menyimpan hasil lama bisa menambah biaya memori tanpa banyak membantu.

Memoization vs. tabulation

Memoization: penyimpanan top-down

Memoization dimulai dari ide rekursif. Ketika algoritma menyelesaikan sebuah submasalah untuk pertama kali, hasilnya disimpan. Pemanggilan berikutnya menggunakan nilai yang sudah disimpan alih-alih menghitung ulang.

Gaya ini sering lebih mudah ketika relasi rekurensinya jelas tetapi urutan semua state yang dibutuhkan belum jelas.

Tabulation: penyusunan bottom-up

Tabulation dimulai dari base case lalu mengisi state dalam urutan yang membuat dependensi tersedia saat dibutuhkan.

Gaya ini sering lebih mudah ketika Anda sudah mengetahui urutan iterasi yang rapi dan ingin kendali yang eksplisit atas tabel.

Contoh dynamic programming: Fibonacci

Barisan Fibonacci didefinisikan oleh

$$F(0) = 0, \quad F(1) = 1$$

dan, untuk $n \ge 2$,

$$F(n) = F(n-1) + F(n-2)$$

Solusi rekursif biasa mengulang pekerjaan. Misalnya, menghitung $F(5)$ membutuhkan $F(4)$ dan $F(3)$, lalu menghitung $F(4)$ membutuhkan $F(3)$ lagi. Pemanggilan $F(3)$ yang berulang itulah jenis pemborosan yang dihilangkan oleh dynamic programming.

Memoization pada Fibonacci

Dengan memoization, relasi rekurensinya tetap sama, tetapi setiap nilai disimpan setelah pertama kali dihitung.

Untuk $F(5)$, urutan yang berguna adalah:

• hitung dan simpan $F(0)=0$
• hitung dan simpan $F(1)=1$
• hitung dan simpan $F(2)=1$
• hitung dan simpan $F(3)=2$
• hitung dan simpan $F(4)=3$
• hitung dan simpan $F(5)=5$

Poin utamanya adalah setiap state dihitung satu kali. Permintaan berikutnya tinggal membaca nilai yang sudah disimpan.

Tabulation pada Fibonacci

Dengan tabulation, Anda membangun dari base case ke atas:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

Versi ini membuat urutan dependensi terlihat jelas: setiap nilai baru memakai entri yang sudah diketahui.

Mengapa dynamic programming bisa lebih cepat

Jika sebuah masalah hanya memiliki $k$ state berbeda yang penting, dynamic programming berusaha menyelesaikan masing-masing dari $k$ state itu satu kali. Ini bisa mengubah pohon rekursi yang besar menjadi komputasi yang jauh lebih kecil.

Percepatan pastinya bergantung pada masalahnya. Dynamic programming tidak otomatis cepat. Metode ini membantu ketika pekerjaan berulang memang merupakan bagian nyata dari solusi awal.

Kesalahan umum dalam dynamic programming

Menggunakannya saat submasalah tidak tumpang tindih

Tidak semua masalah rekursif adalah masalah dynamic programming. Jika hampir setiap submasalah berbeda, menyimpan hasil mungkin tidak menghemat cukup banyak pekerjaan untuk menjadi berarti.

Mendefinisikan state yang salah

State harus memuat semua informasi yang dibutuhkan untuk langkah berikutnya. Jika ada informasi penting yang hilang, relasi rekurensi bisa tampak benar tetapi menghasilkan jawaban yang salah.

Salah menentukan base case

Base case menjadi fondasi seluruh metode. Jika nilai awalnya salah, semua state berikutnya yang dibangun darinya juga akan salah.

Mengisi tabel dalam urutan yang salah

Tabulation hanya bekerja jika setiap state diisi setelah state yang menjadi dependensinya. Relasi rekurensi yang benar pun tetap bisa gagal jika urutan pengisiannya salah.

Menganggap dynamic programming selalu berarti optimasi

Banyak contoh terkenal memaksimalkan atau meminimalkan sesuatu, tetapi dynamic programming juga dipakai untuk masalah penghitungan dan pengambilan keputusan. Tanda utamanya adalah submasalah yang bisa digunakan ulang, bukan kata "terbaik".

Di mana dynamic programming digunakan

Dynamic programming muncul dalam masalah seperti edit distance, longest common subsequence, menghitung jumlah jalur, optimasi gaya knapsack, dan beberapa kasus shortest path.

Saat Anda memutuskan apakah metode ini layak dicoba, ajukan dua pertanyaan:

• apakah submasalah yang lebih kecil berulang?
• apakah jawaban yang lebih besar bisa dibangun dari jawaban-jawaban kecil itu?

Jika kedua jawabannya ya, dynamic programming adalah kandidat yang kuat.

Coba masalah serupa

Cobalah versi Anda sendiri untuk menghitung banyaknya cara menaiki $n$ anak tangga jika setiap langkah bisa berupa $1$ anak tangga atau $2$ anak tangga. Relasi rekurensinya sederhana, submasalah berulangnya mudah dikenali, dan ini adalah contoh lanjutan yang bagus setelah Fibonacci.