Beranda algoritma pemrograman pemrograman dinamis tutorial

Dynamic Programming: Panduan Mudah Pahami Konsep & Contohnya!

Updated: • 0 • min read
Table of Contents

Oke, mari kita bedah satu per satu tentang apa sih yang dinamakan Dynamic Programming (DP) itu. Secara sederhana, Dynamic Programming adalah salah satu teknik atau metode dalam pemrograman komputer dan matematika untuk memecahkan masalah yang kompleks dengan memecahnya menjadi sub-masalah yang lebih kecil dan menyimpannya agar tidak perlu dihitung ulang. Jadi, kalau ada masalah besar yang solusinya bisa didapat dari solusi masalah-masalah kecil di dalamnya, dan masalah-masalah kecil itu ada yang overlap (berulang), nah DP ini bisa jadi jagoannya.

Bayangkan kamu sedang menghitung sesuatu yang besar, dan untuk menghitungnya, kamu perlu hasil dari perhitungan lain yang lebih kecil. Ternyata, perhitungan kecil ini ada banyak yang sama, harus dihitung berkali-kali. Dynamic Programming datang menyelamatkan dengan bilang, “Hei, kenapa dihitung ulang terus? Simpan saja hasilnya pertama kali dihitung, nanti kalau butuh lagi tinggal ambil!”

Dynamic Programming Illustration
Image just for illustration

Konsep utama DP ini adalah menghindari perhitungan yang berulang-ulang tadi. Dengan menyimpan hasil perhitungan sub-masalah, kita bisa mendapatkan solusi untuk masalah yang lebih besar dengan jauh lebih efisien, baik dari segi waktu eksekusi maupun sumber daya komputasi. Teknik ini sangat powerful dan sering digunakan dalam berbagai bidang ilmu komputer, mulai dari algoritma, kecerdasan buatan, hingga optimasi.

Mengapa Disebut “Dynamic Programming”?

Nama “Dynamic Programming” ini sebenarnya punya cerita unik lho. Konon, nama ini diciptakan oleh Richard Bellman di tahun 1950-an. Beliau menjelaskan bahwa istilah “dynamic” dipilih karena masalah yang dihadapi biasanya melibatkan waktu atau tahapan yang dinamis, berubah seiring waktu atau tahapan perhitungan. Sedangkan “programming” di sini tidak merujuk pada coding dalam arti membuat program komputer modern, melainkan lebih ke perencanaan atau penjadwalan langkah-langkah (seperti di “linear programming” atau “mathematical programming”).

Bellman memilih nama yang terdengar “wah” ini juga karena alasan politis dan pendanaan saat itu. Dia merasa istilah “programming” terdengar lebih menarik dan penting bagi para pemberi dana dibandingkan hanya menyebutnya sebagai “multi-stage decision process”. Jadi, nama itu sendiri mungkin sedikit misleading kalau kamu membayangkannya hanya tentang menulis kode, tapi esensinya adalah tentang perencanaan solusi secara bertahap.

Nama yang mungkin sedikit membingungkan ini menutupi konsep yang sebenarnya cukup elegan dan powerful. Intinya, DP adalah tentang memecah, menyelesaikan sub-masalah, dan menyimpan hasilnya untuk efisiensi.

Dua Pilar Utama Dynamic Programming

Dynamic Programming bisa diterapkan pada masalah yang memenuhi dua syarat utama:

1. Optimal Substructure (Struktur Optimal)

Artinya, solusi optimal dari masalah besar bisa dibangun dari solusi optimal dari sub-masalahnya yang lebih kecil. Kalau dianalogikan, anggap saja seperti menyusun LEGO. Bangunan LEGO yang besar dan optimal (paling kokoh atau paling indah) bisa tersusun dari balok-balok LEGO yang juga optimal (dalam artian diletakkan di posisi terbaiknya untuk membentuk bagian yang lebih kecil).

Contoh klasik adalah mencari jalur terpendek dari titik A ke titik B di sebuah peta. Jika jalur terpendek dari A ke B melewati titik C, maka jalur dari A ke C pastilah jalur terpendek dari A ke C, dan jalur dari C ke B pastilah jalur terpendek dari C ke B. Solusi optimal (jalur terpendek A ke B) bergantung pada solusi optimal sub-masalah (jalur terpendek A ke C dan C ke B).

Optimal Substructure Diagram
Image just for illustration

2. Overlapping Subproblems (Sub-masalah Berulang)

Ini adalah syarat yang membedakan DP dengan teknik Divide and Conquer biasa (seperti Merge Sort atau Quick Sort). Pada DP, ketika kita memecah masalah besar menjadi sub-masalah, sub-masalah yang sama muncul berulang kali dalam proses pemecahan tersebut.

Kembali ke analogi, jika menyusun LEGO membutuhkan balok biru ukuran 2x2, dan di bagian lain bangunan yang sama juga membutuhkan balok biru ukuran 2x2, maka itu adalah sub-masalah yang sama (memasang balok biru 2x2 di tempat yang tepat). Kalau kita harus “menghitung” cara memasang balok itu setiap kali dibutuhkan di tempat berbeda, itu tidak efisien. DP akan “menghitung” cara memasangnya sekali, menyimpan hasil/konfigurasinya, dan menggunakannya lagi di tempat lain tanpa perlu menghitung ulang.

Contoh paling populer untuk menunjukkan ini adalah deret Fibonacci. Untuk menghitung F(n), kita butuh F(n-1) dan F(n-2). Untuk F(n-1), kita butuh F(n-2) dan F(n-3). Perhatikan F(n-2) muncul di perhitungan F(n) dan juga di perhitungan F(n-1). Semakin besar ‘n’, semakin banyak sub-masalah yang sama (seperti F(n-2), F(n-3), dst.) muncul berulang kali dalam pohon rekursi.

Tanpa DP (dengan rekursi naif), banyak perhitungan yang sama akan diulang. Dengan DP, kita simpan F(k) setelah pertama kali dihitung, dan ketika dibutuhkan lagi, kita tinggal ambil nilai yang sudah disimpan.

Dua Pendekatan Dynamic Programming

Ada dua cara utama untuk mengimplementasikan Dynamic Programming:

1. Top-Down (dengan Memoization)

Pendekatan ini dimulai dari masalah besar dan secara rekursif memecahnya menjadi sub-masalah yang lebih kecil, persis seperti cara kerja rekursi biasa. Bedanya, pendekatan Top-Down menyimpan hasil dari setiap sub-masalah yang sudah dipecahkan (biasanya dalam sebuah array, map, atau tabel yang disebut “memo”). Ketika fungsi rekursif dipanggil untuk sub-masalah yang hasilnya sudah ada di memo, fungsi tersebut tidak melakukan perhitungan ulang, melainkan langsung mengembalikan nilai yang tersimpan. Proses penyimpanan hasil ini dinamakan memoization.

Cara Kerjanya:
* Fungsi dipanggil untuk masalah N.
* Cek apakah solusi N sudah ada di memo.
* Jika sudah ada, langsung kembalikan nilai dari memo.
* Jika belum ada, hitung solusi N dengan memanggil fungsi secara rekursif untuk sub-masalah yang lebih kecil (N-1, N-2, dst).
* Simpan hasil perhitungan N di memo.
* Kembalikan hasil N.

Keunggulan:
* Lebih intuitif, karena mengikuti struktur rekursi alami dari masalah.
* Hanya sub-masalah yang benar-benar dibutuhkan yang dihitung.

Kelemahan:
* Bisa membutuhkan call stack yang dalam jika rekursinya sangat dalam (potensi stack overflow).
* Overhead pemanggilan fungsi rekursif.

Top-Down DP Illustration
Image just for illustration

Contoh kode pseudocode untuk Fibonacci dengan Top-Down:

memo = map Kosong

fib(n):
  jika n <= 1:
    kembalikan n
  jika memo[n] sudah ada:
    kembalikan memo[n]

  hasil = fib(n-1) + fib(n-2)
  memo[n] = hasil
  kembalikan hasil

2. Bottom-Up (dengan Tabulation)

Pendekatan ini kebalikannya. Dimulai dari menyelesaikan sub-masalah yang paling kecil terlebih dahulu, kemudian menggunakan hasil dari sub-masalah tersebut untuk membangun solusi sub-masalah yang lebih besar, dan seterusnya, sampai akhirnya mendapatkan solusi untuk masalah besar. Hasil dari setiap sub-masalah disimpan dalam sebuah tabel (biasanya array) secara sistematis. Proses mengisi tabel ini dinamakan tabulation.

Cara Kerjanya:
* Buat tabel (misalnya array dp) untuk menyimpan solusi sub-masalah. Ukuran tabel disesuaikan dengan rentang sub-masalah yang mungkin.
* Inisialisasi nilai dasar (basis) pada tabel (misalnya dp[0], dp[1] untuk Fibonacci).
* Iterasi (biasanya menggunakan loop) dari sub-masalah terkecil hingga terbesar.
* Untuk setiap sub-masalah i, hitung solusinya menggunakan nilai-nilai yang sudah ada di tabel pada indeks yang lebih kecil (misalnya dp[i-1], dp[i-2]).
* Simpan hasil perhitungan dp[i] di tabel.
* Solusi untuk masalah besar ada di entri tabel terakhir yang dihitung.

Keunggulan:
* Tidak ada overhead rekursi.
* Tidak ada risiko stack overflow.
* Performa runtime biasanya sedikit lebih cepat karena menggunakan iterasi.

Kelemahan:
* Bisa kurang intuitif untuk dipahami dibandingkan Top-Down, karena perlu memikirkan urutan pengisian tabel dari bawah ke atas.
* Mungkin perlu menghitung solusi untuk sub-masalah yang sebenarnya tidak dibutuhkan untuk solusi akhir (walaupun ini tergantung struktur masalahnya).

Bottom-Up DP Illustration
Image just for illustration

Contoh kode pseudocode untuk Fibonacci dengan Bottom-Up:

dp = array berukuran (n+1)

dp[0] = 0
dp[1] = 1

untuk i dari 2 sampai n:
  dp[i] = dp[i-1] + dp[i-2]

kembalikan dp[n]

Kedua pendekatan ini akan menghasilkan solusi yang sama, namun dengan cara implementasi dan karakteristik performa yang sedikit berbeda. Pemilihan antara Top-Down dan Bottom-Up seringkali tergantung pada preferensi programmer atau sifat spesifik masalahnya.

Contoh Masalah yang Bisa Diselesaikan dengan Dynamic Programming

Banyak sekali masalah dalam ilmu komputer yang merupakan kandidat kuat untuk diselesaikan menggunakan DP. Beberapa yang paling terkenal antara lain:

  1. Deret Fibonacci: Seperti yang sudah dibahas, menghitung F(n) secara efisien.
  2. Knapsack Problem: Diberikan sebuah “ransel” dengan kapasitas maksimum dan sekumpulan barang dengan berat dan nilai tertentu, bagaimana memilih barang-barang yang akan dimasukkan ke ransel agar total nilai maksimal tanpa melebihi kapasitas.
  3. Longest Common Subsequence (LCS): Mencari sub-urutan terpanjang yang sama antara dua urutan (string) yang diberikan. Misalnya, LCS dari “AGGTAB” dan “GXTXAYB” adalah “GTAB”.
  4. Shortest Path Problems: Algoritma seperti Floyd-Warshall atau Bellman-Ford yang digunakan untuk mencari jalur terpendek di graf berbobot menggunakan prinsip DP.
  5. Matrix Chain Multiplication: Menentukan urutan perkalian matriks yang paling efisien untuk meminimalkan jumlah operasi perkalian skalar.
  6. Coin Change Problem: Menemukan berapa banyak cara berbeda untuk menghasilkan jumlah uang kembalian tertentu menggunakan kumpulan koin yang tersedia (atau jumlah minimum koin).

Setiap masalah ini memiliki struktur optimal dan sub-masalah yang tumpang tindih, menjadikannya cocok untuk dipecahkan dengan DP.

Kapan Menggunakan Dynamic Programming?

Jadi, bagaimana cara mengenali apakah suatu masalah bisa diselesaikan dengan DP? Caranya adalah dengan mencari dua karakteristik utama tadi:

  • Apakah solusi masalah besar bisa dibangun dari solusi sub-masalah yang lebih kecil? Coba pecah masalah menjadi bagian-bagian yang lebih kecil. Apakah solusi optimal untuk bagian besar bergantung pada solusi optimal untuk bagian-bagian kecil itu?
  • Apakah sub-masalah yang sama muncul berulang kali saat kamu memecahnya? Gambarkan “pohon rekursi” dari masalah tersebut. Lihat apakah ada cabang yang perhitungannya sama.

Jika kedua syarat ini terpenuhi, kemungkinan besar masalah tersebut bisa dipecahkan secara efisien menggunakan Dynamic Programming.

Tips dan Trik Menerapkan Dynamic Programming

Menerapkan DP bisa jadi sedikit tricky di awal. Ini beberapa tips yang bisa membantu:

  1. Pahami Struktur Rekursif: Sebelum memikirkan DP, coba pikirkan dulu solusi rekursif (mungkin yang naif) untuk masalah tersebut. Ini akan membantumu melihat bagaimana masalah dipecah menjadi sub-masalah.
  2. Identifikasi Parameter yang Berubah: Dalam solusi rekursif, perhatikan parameter apa saja yang berubah dalam setiap panggilan rekursif. Ini biasanya akan menjadi “state” atau “keadaan” yang perlu kamu simpan di tabel/memo DP.
  3. Definisikan State DP: Tentukan dengan jelas apa arti dari dp[i] atau dp[i][j] dalam tabel/memo DP kamu. Misalnya, dp[i] mungkin berarti “solusi untuk sub-masalah berukuran i” atau dp[i][j] berarti “solusi untuk sub-masalah menggunakan elemen i hingga j”.
  4. Temukan Relasi Rekurensi: Ini adalah bagian paling krusial. Bagaimana kamu menghitung dp[state] menggunakan nilai-nilai dp pada state yang lebih kecil atau sebelumnya? Ini adalah “rumus transisi” DP-mu.
  5. Tentukan Basis Kasus: Apa solusi untuk sub-masalah terkecil yang tidak bisa dipecah lagi? Ini adalah nilai awal yang akan kamu gunakan untuk mengisi tabel Bottom-Up atau kondisi berhenti untuk Top-Down.
  6. Pilih Pendekatan: Putuskan mau menggunakan Top-Down (memoization) atau Bottom-Up (tabulation). Bottom-Up seringkali lebih disukai untuk masalah yang “state”nya bisa diiterasi dengan mudah, sementara Top-Down bisa lebih mudah diimplementasikan jika struktur rekursifnya kompleks.
  7. Optimasi Ruang (Space Optimization): Kadang-kadang, untuk menghitung dp[i], kamu hanya butuh hasil dari beberapa state sebelumnya (misalnya dp[i-1] dan dp[i-2] seperti Fibonacci). Dalam kasus ini, kamu tidak perlu menyimpan seluruh tabel DP, cukup beberapa nilai terakhir. Ini bisa menghemat banyak memori, terutama untuk masalah dengan state yang besar.

Contoh sederhana optimasi ruang pada Fibonacci (Bottom-Up):

// Untuk menghitung F(n), hanya butuh F(n-1) dan F(n-2)
// Jadi, cukup simpan 2 nilai terakhir

a = 0 // F(0)
b = 1 // F(1)

jika n == 0: kembalikan a
jika n == 1: kembalikan b

untuk i dari 2 sampai n:
  c = a + b // F(i) = F(i-1) + F(i-2)
  a = b     // geser F(i-1) ke 'a' untuk iterasi berikutnya
  b = c     // geser F(i) ke 'b' untuk iterasi berikutnya

kembalikan b // F(n)

Perbedaan DP dengan Teknik Lain

Penting untuk membedakan DP dengan beberapa teknik algoritmik lainnya:

  • Dynamic Programming vs. Divide and Conquer: Keduanya memecah masalah besar menjadi sub-masalah. Bedanya, Divide and Conquer memecah menjadi sub-masalah yang independen (tidak tumpang tindih), lalu menggabungkan solusinya (contoh: Merge Sort). DP memecah menjadi sub-masalah yang tumpang tindih dan menyimpan solusinya untuk menghindari perhitungan ulang.
  • Dynamic Programming vs. Greedy Algorithms: Algoritma Greedy membuat pilihan lokal yang optimal pada setiap langkah dengan harapan menghasilkan solusi global yang optimal. Ini tidak selalu berhasil. DP mempertimbangkan semua kemungkinan sub-masalah dan relasinya untuk menjamin solusi global yang optimal (jika masalah memenuhi syarat struktur optimal).

Fakta Menarik tentang Dynamic Programming

  • Istilah “Dynamic Programming” sebenarnya awalnya tidak terkait langsung dengan optimasi di komputer, melainkan lebih pada perencanaan keputusan sekuensial seiring waktu.
  • DP pertama kali diformalkan oleh Richard Bellman di tahun 1950-an, seorang matematikawan terkemuka.
  • Teknik DP memiliki aplikasi luas, tidak hanya di Computer Science. DP juga digunakan di bidang Ekonomi (misalnya untuk model pertumbuhan atau konsumsi), Biologi (misalnya untuk sequence alignment DNA/protein), dan bahkan Operation Research.

Kesimpulan

Dynamic Programming adalah teknik algoritmik yang elegan dan sangat ampuh untuk menyelesaikan kelas masalah tertentu yang memiliki struktur optimal dan sub-masalah yang tumpang tindih. Dengan memecah masalah, menyelesaikan sub-masalah terkecil terlebih dahulu (Bottom-Up) atau menyimpan hasil sub-masalah saat pertama kali dihitung (Top-Down), kita bisa menghindari perhitungan yang berulang dan mencapai efisiensi yang jauh lebih baik dibandingkan solusi rekursif naif. Menguasai DP memang butuh latihan, tapi begitu kamu paham konsepnya, banyak masalah kompleks akan terasa lebih mudah dipecahkan.

Nah, itu dia penjelasan singkat (tapi lumayan detail ya!) tentang apa itu Dynamic Programming. Semoga bisa memberikan gambaran yang jelas buat kamu.

Bagaimana? Ada bagian yang masih bingung atau ingin kamu tanyakan lebih lanjut? Atau mungkin kamu punya contoh masalah DP lain yang menarik? Jangan ragu untuk tinggalkan komentar di bawah ya! Kita bisa diskusi bareng di sini.

Posting Komentar