Apa Itu Dynamic Programming? Penjelasan Simpel Buat Pemula

Table of Contents

Dynamic Programming, atau sering disingkat DP, adalah salah satu teknik atau paradigma desain algoritma yang sangat powerful dan sering ditemui dalam ilmu komputer, terutama saat memecahkan masalah optimasi. Secara garis besar, DP adalah cara untuk memecahkan masalah kompleks dengan memecahnya menjadi sub-masalah yang lebih kecil. Solusi dari sub-masalah ini kemudian disimpan agar tidak perlu dihitung ulang jika sub-masalah yang sama muncul lagi. Ini inti utamanya: menghindari perhitungan berulang untuk sub-masalah yang sama.

Jadi, kalau diibaratkan, DP itu seperti seorang koki cerdas yang sedang memasak banyak hidangan. Daripada memotong bawang setiap kali dibutuhkan untuk satu hidangan, dia memotong semua bawang sekaligus di awal, menyimpannya, dan tinggal mengambilnya setiap kali resep membutuhkan bawang. Ini jauh lebih efisien daripada memotong sedikit demi sedikit berkali-kali.

Image just for illustration

Konsep Dasar: Memecah Masalah Besar Menjadi Kecil¶

Inti dari Dynamic Programming adalah ide bahwa banyak masalah kompleks bisa dipecah menjadi masalah-masalah yang lebih kecil dan serupa. Yang membedakan DP dengan teknik pemecahan masalah lain seperti Divide and Conquer adalah sifat overlapping subproblems. Artinya, ketika masalah besar dipecah, sub-masalah yang sama akan muncul berulang kali di cabang-cabang yang berbeda dari pemecahan masalah tersebut.

Misalnya, untuk menghitung Fibonacci ke-5, kita butuh Fibonacci ke-4 dan ke-3. Untuk menghitung Fibonacci ke-4, kita butuh Fibonacci ke-3 dan ke-2. Perhatikan bahwa Fibonacci ke-3 muncul dua kali: satu sebagai bagian dari perhitungan F(5) dan satu lagi sebagai bagian dari F(4). Inilah overlapping subproblems yang menjadi ciri khas masalah yang bisa dipecahkan dengan DP.

Teknik DP memanfaatkan sifat overlapping subproblems ini dengan menyimpan hasil perhitungan sub-masalah. Penyimpanan hasil ini bisa dilakukan dengan dua cara utama, yang akan kita bahas nanti: memoization (pendekatan top-down) dan tabulation (pendekatan bottom-up). Dengan menyimpan hasil sub-masalah, saat sub-masalah yang sama perlu dihitung lagi, kita tinggal mengambil nilai yang sudah disimpan, tanpa perlu menghitung ulang dari awal.

Selain overlapping subproblems, ciri kedua dari masalah yang bisa dipecahkan dengan DP adalah optimal substructure. Ini berarti solusi optimal dari masalah yang lebih besar bisa dibangun dari solusi optimal dari sub-masalahnya. Jika kita menemukan solusi terbaik untuk semua sub-masalah, menggabungkannya akan memberikan solusi terbaik untuk masalah keseluruhan.

Dua Pendekatan Utama: Top-Down vs Bottom-Up¶

Dalam mengimplementasikan Dynamic Programming, ada dua pendekatan utama yang bisa dipilih. Keduanya memiliki kelebihan dan kekurangan masing-masing, dan pemilihannya seringkali tergantung pada preferensi programmer atau sifat spesifik masalahnya. Dua pendekatan itu adalah Top-Down (dengan Memoization) dan Bottom-Up (dengan Tabulation).

Top-Down (Memoization)¶

Pendekatan Top-Down mengikuti cara berpikir alami saat memecah masalah secara rekursif. Kita mulai dari masalah utama yang ingin diselesaikan, lalu kita pecah menjadi sub-masalah yang lebih kecil sesuai dengan relasi rekursifnya. Jika kita perlu menghitung solusi untuk sub-masalah tertentu, kita cek dulu apakah solusi itu sudah pernah dihitung dan disimpan.

Jika sudah ada, kita langsung gunakan nilainya. Jika belum, baru kita hitung solusi untuk sub-masalah tersebut (mungkin dengan memecahnya lagi menjadi sub-sub-masalah yang lebih kecil, dan seterusnya), dan setelah mendapatkan hasilnya, kita simpan hasilnya sebelum mengembalikannya. Proses penyimpanan hasil ini disebut memoization.

Pendekatan ini biasanya diimplementasikan menggunakan fungsi rekursif dengan tambahan struktur data (seperti array atau hash map) untuk menyimpan hasil yang sudah dihitung. Keuntungan Top-Down adalah seringkali lebih mudah diimplementasikan karena langsung mengikuti definisi rekursif masalah. Selain itu, hanya sub-masalah yang benar-benar dibutuhkan saja yang akan dihitung solusinya.

Namun, kelemahannya adalah penggunaan memori untuk call stack rekursi yang bisa menyebabkan stack overflow untuk masalah yang sangat besar. Ada juga sedikit overhead karena panggilan fungsi rekursif itu sendiri.

Image just for illustration

Bottom-Up (Tabulation)¶

Kebalikan dari Top-Down, pendekatan Bottom-Up memulai perhitungan dari sub-masalah yang paling dasar atau paling kecil, yang solusinya sudah diketahui (kasus dasar/base cases). Kemudian, kita secara iteratif menghitung solusi untuk sub-masalah yang lebih besar, menggunakan solusi sub-masalah yang lebih kecil yang sudah dihitung dan disimpan sebelumnya. Hasil dari setiap sub-masalah disimpan dalam sebuah tabel atau array, itulah mengapa pendekatan ini juga sering disebut tabulation.

Prosesnya terus berlanjut hingga kita mencapai solusi untuk masalah utama yang paling besar. Misalnya, untuk Fibonacci, kita hitung F(0) dan F(1) (base cases), lalu gunakan hasilnya untuk menghitung F(2) = F(1) + F(0), lalu gunakan F(1) dan F(2) untuk menghitung F(3), dan seterusnya, sampai F(n).

Keuntungan Bottom-Up adalah bersifat iteratif, sehingga tidak ada risiko stack overflow seperti pada rekursi. Umumnya, pendekatan ini juga lebih efisien dalam hal runtime karena tidak ada overhead panggilan fungsi rekursif, dan penggunaan memorinya (untuk tabel) biasanya lebih terkontrol. Kelemahannya adalah kita perlu memikirkan urutan perhitungan sub-masalah dengan benar agar saat menghitung sub-masalah tertentu, semua sub-masalah yang lebih kecil yang dibutuhkan sudah tersedia solusinya. Kadang-kadang, kita mungkin menghitung solusi untuk sub-masalah yang sebenarnya tidak diperlukan untuk solusi akhir (meskipun ini jarang terjadi pada masalah klasik DP).

Image just for illustration

Kapan Kita Pakai Dynamic Programming?¶

Tidak semua masalah optimasi bisa diselesaikan dengan efisien menggunakan Dynamic Programming. Ada dua karakteristik utama yang harus dimiliki sebuah masalah agar bisa dipecahkan dengan baik oleh DP, seperti yang sudah disinggung sebelumnya:

1. Optimal Substructure¶

Sebuah masalah dikatakan memiliki optimal substructure jika solusi optimal dari masalah besar dapat dibangun dari solusi optimal dari sub-masalahnya. Artinya, jika Anda memiliki solusi terbaik untuk seluruh masalah, maka solusi terbaik tersebut pastilah menggunakan solusi terbaik untuk setiap bagian (sub-masalah) dari masalah tersebut.

Contohnya pada masalah jalur terpendek di graf tanpa bobot negatif: jika jalur terpendek dari titik A ke C melewati titik B, maka bagian jalur dari A ke B pastilah jalur terpendek dari A ke B, dan bagian jalur dari B ke C pastilah jalur terpendek dari B ke C. Ini adalah contoh sifat optimal substructure. Jika masalah tidak memiliki sifat ini, DP mungkin tidak cocok atau tidak akan menghasilkan solusi yang optimal.

2. Overlapping Subproblems¶

Ini adalah karakteristik kunci yang membedakan DP dari Divide and Conquer murni. Overlapping subproblems terjadi ketika dalam proses memecah masalah besar menjadi sub-masalah yang lebih kecil, sub-masalah yang sama muncul dan perlu dipecahkan berkali-kali.

Misalnya, dalam menghitung Fibonacci ke-n, sub-masalah untuk menghitung Fibonacci ke-(n-2) akan muncul baik saat menghitung F(n-1) maupun F(n). Jika sub-masalah yang sama dihitung berulang kali, maka ada pemborosan waktu komputasi. DP mengatasi ini dengan menyimpan hasil sub-masalah yang sudah dihitung (memoization atau tabulation) sehingga sub-masalah yang sama tidak perlu dihitung ulang. Jika sub-masalahnya independen (tidak tumpang tindih), maka teknik Divide and Conquer mungkin lebih tepat.

Image just for illustration

Jika sebuah masalah memiliki kedua karakteristik ini, kemungkinan besar Dynamic Programming adalah teknik yang cocok untuk menyelesaikannya secara efisien. DP mengubah algoritma eksponensial (karena perhitungan berulang) menjadi polinomial (karena setiap sub-masalah dihitung paling banyak satu kali).

Contoh Klasik Masalah Dynamic Programming¶

Untuk lebih memahami DP, mari kita lihat beberapa contoh masalah klasik yang sering diselesaikan menggunakan teknik ini.

Deret Fibonacci¶

Deret Fibonacci adalah contoh paling sederhana dan sering digunakan untuk memperkenalkan konsep overlapping subproblems. Definisi rekursifnya adalah F(n) = F(n-1) + F(n-2), dengan base cases F(0) = 0 dan F(1) = 1.

Secara rekursif naive, kita bisa menulis fungsi seperti ini:

def fib_naive(n):
    if n <= 1:
        return n
    else:
        return fib_naive(n-1) + fib_naive(n-2)

Ini sangat tidak efisien. Untuk menghitung fib_naive(5), kita butuh fib_naive(4) dan fib_naive(3). fib_naive(4) butuh fib_naive(3) dan fib_naive(2). fib_naive(3) butuh fib_naive(2) dan fib_naive(1), dan fib_naive(2) butuh fib_naive(1) dan fib_naive(0). Perhatikan fib_naive(3) dihitung dua kali dan fib_naive(2) dihitung tiga kali. Semakin besar n, semakin banyak perhitungan berulang yang eksponensial.

Mari kita ilustrasikan pohon rekursinya:
mermaid graph TD F(5) --> F(4) F(5) --> F(3) F(4) --> F(3) F(4) --> F(2) F(3) --> F(2) F(3) --> F(1) F(2) --> F(1) F(2) --> F(0) classDef overlap fill:#f9f,stroke:#333,stroke-width:2px; class F(3),F(2) overlap;
Seperti terlihat, node F(3) dan F(2) dihitung berulang.

Menggunakan DP (Top-Down/Memoization):
Kita bisa simpan hasil F(n) dalam array atau dictionary setelah dihitung.

memo = {}
def fib_memo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        result = n
    else:
        result = fib_memo(n-1) + fib_memo(n-2)
    memo[n] = result
    return result

Dengan memoization, jika fib_memo(3) atau fib_memo(2) sudah pernah dipanggil dan hasilnya disimpan di memo, panggilan berikutnya akan langsung mengambil dari sana tanpa menghitung ulang.

Menggunakan DP (Bottom-Up/Tabulation):
Kita bisa menggunakan array untuk menyimpan hasil dari F(0) hingga F(n).

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Kita mulai dari nilai dasar yang diketahui (dp[0]=0, dp[1]=1), lalu secara iteratif menghitung nilai berikutnya menggunakan nilai yang sudah dihitung sebelumnya, hingga mencapai dp[n].

Knapsack Problem (0/1 Knapsack)¶

Ini adalah masalah optimasi klasik: diberikan sebuah tas (knapsack) dengan kapasitas maksimum tertentu dan sekumpulan barang, di mana setiap barang punya bobot dan nilai. Kita ingin memilih barang mana saja yang akan dimasukkan ke dalam tas agar total nilai barang maksimal, tanpa melebihi kapasitas tas. Dalam versi 0/1, setiap barang hanya bisa diambil seluruhnya atau tidak sama sekali.

Masalah ini punya optimal substructure: solusi optimal untuk tas dengan kapasitas W dan mempertimbangkan N barang bisa diturunkan dari solusi optimal untuk tas dengan kapasitas yang sama atau berbeda dan mempertimbangkan N-1 barang. Masalah ini juga punya overlapping subproblems: sub-masalah “kapasitas sekian dengan item sampai index ini” akan muncul berulang.

Pendekatan DP biasanya melibatkan pembuatan tabel (array 2D) dp[i][w] yang menyimpan nilai maksimum yang bisa diperoleh dengan mempertimbangkan barang hingga index i dan dengan kapasitas tas w.

Image just for illustration

Longest Common Subsequence (LCS)¶

Diberikan dua buah sekuens (misalnya string), kita ingin mencari subsekuens terpanjang yang sama-sama muncul di kedua sekuens tersebut. Subsekuens tidak harus berurutan secara consecutive (berdampingan) seperti substring, tapi urutannya harus tetap sama.

Contoh: LCS dari “AGGTAB” dan “GXTXAYB” adalah “GTAB”, panjangnya 4.
Masalah ini memiliki optimal substructure (LCS dari dua sekuens tergantung pada LCS dari prefiks/bagian awal sekuens tersebut) dan overlapping subproblems (sub-masalah LCS dari prefiks-prefiks yang sama akan dihitung berulang).

Solusi DP biasanya menggunakan tabel 2D dp[i][j] yang menyimpan panjang LCS dari prefiks pertama sepanjang i dan prefiks kedua sepanjang j.

Image just for illustration

Coin Change Problem¶

Diberikan sekumpulan denominasi koin dan sebuah jumlah target, kita ingin mengetahui ada berapa banyak cara berbeda untuk mendapatkan jumlah target tersebut menggunakan koin-koin yang tersedia. Atau, versi lain: berapa jumlah minimum koin yang dibutuhkan untuk mendapatkan jumlah target tersebut.

Masalah ini juga punya optimal substructure (solusi untuk jumlah target tertentu tergantung pada solusi untuk jumlah target yang lebih kecil) dan overlapping subproblems (jumlah-jumlah target yang sama akan muncul saat mencoba menggunakan koin-koin yang berbeda).

Pendekatan DP melibatkan tabel 1D dp[i] yang menyimpan solusi (jumlah cara atau jumlah minimum koin) untuk mencapai jumlah i.

Image just for illustration

Langkah-Langkah Menyelesaikan Masalah dengan Dynamic Programming¶

Menerapkan DP bisa terasa menantang di awal, tapi ada beberapa langkah sistematis yang bisa diikuti:

1. Identifikasi apakah masalah memiliki Optimal Substructure: Bisakah solusi optimal dari masalah besar dibangun dari solusi optimal sub-masalahnya? Jika tidak, DP mungkin bukan teknik yang tepat.
2. Identifikasi apakah masalah memiliki Overlapping Subproblems: Saat memecah masalah secara rekursif, apakah sub-masalah yang sama akan muncul berulang kali? Menggambar pohon rekursi sering membantu melihat ini. Jika sub-masalahnya independen, pertimbangkan Divide and Conquer.
3. Definisikan State DP: Tentukan apa yang akan disimpan dalam tabel DP Anda. Ini biasanya merupakan nilai solusi untuk sub-masalah. Misalnya, dp[i] bisa berarti “solusi untuk sub-masalah berukuran i” atau dp[i][j] berarti “solusi untuk sub-masalah melibatkan elemen hingga index i dan j”. Pemilihan state yang tepat sangat krusial.
4. Definisikan Relasi Rekursif (Transition): Temukan bagaimana solusi untuk state saat ini bisa dihitung dari solusi state-state yang lebih kecil atau sebelumnya. Ini adalah ‘rumus’ utama DP Anda. Contoh: dp[i] = dp[i-1] + dp[i-2] untuk Fibonacci.
5. Identifikasi Kasus Dasar (Base Cases): Tentukan nilai awal tabel DP untuk sub-masalah terkecil yang solusinya sudah diketahui tanpa perlu perhitungan lebih lanjut.
6. Pilih Pendekatan (Top-Down atau Bottom-Up) dan Implementasikan:
   • Top-Down: Implementasikan fungsi rekursif dengan memoization. Cek tabel memo sebelum menghitung, simpan hasil setelah menghitung.
   • Bottom-Up: Inisialisasi tabel dengan base cases, lalu gunakan loop(s) untuk mengisi tabel secara iteratif berdasarkan relasi rekursif, memastikan state yang dibutuhkan sudah terisi.
7. Optimasi (Opsional): Setelah mendapatkan solusi yang benar, lihat apakah bisa dioptimasi, misalnya mengurangi penggunaan memori (kadang tabel 2D bisa diubah jadi 1D).

Image just for illustration

Fakta Menarik dan Tips Belajar DP¶

• Nama “Dynamic Programming”: Nama ini diberikan oleh Richard Bellman pada tahun 1950-an. Konon, kata “Dynamic” dipilih karena terdengar keren dan tidak terkait dengan riset operasi atau matematika (bidang yang sering didanai saat itu, Bellman ingin menjauh dari asosiasi tersebut agar lebih mudah mendapatkan dana penelitian). Tidak ada hubungannya dengan “dinamis” dalam arti waktu nyata atau perubahan cepat.
• Bukan Algoritma Spesifik: Dynamic Programming bukanlah sebuah algoritma tunggal seperti Quicksort atau Dijkstra. Ia adalah sebuah metode atau paradigma untuk merancang algoritma.
• Sering Muncul dalam Interview: DP adalah topik favorit dalam soal-soal interview kerja di perusahaan teknologi, terutama untuk posisi yang berhubungan dengan algoritma dan struktur data. Menguasainya sangat penting.
• DP vs Memoization: Memoization sebenarnya adalah teknik spesifik yang digunakan dalam pendekatan Top-Down DP. DP adalah konsep yang lebih luas.
• Tips Belajar:
  1. Mulai dari yang Sederhana: Pahami dulu Fibonacci, Coin Change, dan masalah 0/1 Knapsack.
  2. Gambar: Gambarlah pohon rekursi untuk melihat overlapping subproblems. Gambarlah tabel DP untuk memahami bagaimana state dihitung pada pendekatan Bottom-Up.
  3. Pahami Relasi Rekursif: Ini adalah bagian terpenting. Jika Anda bisa mendefinisikan sub-masalah dan bagaimana solusinya terkait dengan sub-masalah yang lebih kecil, Anda sudah setengah jalan.
  4. Coba Kedua Pendekatan: Cobalah selesaikan masalah yang sama dengan Top-Down dan Bottom-Up untuk memahami perbedaan dan kelebihan masing-masing.
  5. Latihan Rutin: Seperti skill lainnya, DP butuh latihan. Cari soal-soal DP di platform coding online dan coba selesaikan sendiri.

Image just for illustration

Perbedaan DP dengan Teknik Lain (Greedy, Divide and Conquer)¶

Penting untuk bisa membedakan DP dari teknik desain algoritma lainnya yang mungkin terdengar mirip:

• Greedy: Algoritma Greedy membuat pilihan terbaik lokal pada setiap langkah dengan harapan akan mengarah pada solusi terbaik global. Greedy bekerja untuk beberapa masalah optimasi (misalnya, memilih koin dengan nilai terbesar terlebih dahulu untuk kembalian), tetapi tidak menjamin solusi optimal untuk semua masalah. DP, di sisi lain, mengeksplorasi semua kemungkinan sub-masalah (secara implisit) dan menjamin solusi optimal jika masalahnya memiliki optimal substructure dan overlapping subproblems. Jika masalah bisa diselesaikan dengan Greedy, biasanya lebih sederhana dan efisien dari DP, tetapi Greedy hanya bisa diterapkan pada masalah dengan “sifat serakah” (greedy property).
• Divide and Conquer: Teknik ini juga memecah masalah besar menjadi sub-masalah yang lebih kecil, menyelesaikan sub-masalah tersebut secara rekursif, dan menggabungkan hasilnya. Contoh: Merge Sort, QuickSort. Perbedaan utamanya dengan DP adalah pada Divide and Conquer, sub-masalahnya biasanya independen (tidak tumpang tindih). Artinya, memecah masalah A menjadi B dan C, penyelesaian B tidak memerlukan penyelesaian C dengan input yang sama, dan sebaliknya. Jika ada overlapping subproblems, Divide and Conquer murni akan menghitung ulang sub-masalah yang sama berulang kali, menyebabkan inefisiensi. DP secara eksplisit menangani overlapping subproblems dengan menyimpan dan menggunakan kembali hasil.

Fitur	Dynamic Programming	Greedy Algorithm	Divide and Conquer (Pure)
Pendekatan	Memecah masalah, simpan hasil sub-masalah	Membuat pilihan lokal terbaik	Memecah masalah independen, gabung hasil
Optimalitas Dijamin	Ya (jika sifat DP terpenuhi)	Belum tentu	Ya (jika implementasi benar)
Overlapping Subproblems	Ditangani secara eksplisit (memoization/tabulation)	Tidak ada atau tidak relevan	Tidak ditangani (akan dihitung ulang)
Optimal Substructure	Diperlukan	Kadang diperlukan	Diperlukan
Contoh	Fibonacci, Knapsack, LCS, Coin Change	Minimum Spanning Tree (Prim, Kruskal), Huffman Coding	Merge Sort, QuickSort, Binary Search

Kesimpulan¶

Dynamic Programming adalah teknik fundamental dalam ilmu komputer yang sangat berguna untuk memecahkan masalah optimasi yang memiliki optimal substructure dan overlapping subproblems. Dengan secara cerdas menyimpan dan menggunakan kembali solusi sub-masalah yang sama, DP mengubah algoritma yang tadinya bisa eksponensial menjadi jauh lebih efisien, biasanya dalam waktu polinomial.

Memahami DP melibatkan penguasaan dua pendekatan utamanya, Top-Down (Memoization) dan Bottom-Up (Tabulation), serta mengenali ciri-ciri masalah yang cocok untuk diselesaikan dengan teknik ini. Meskipun awalnya mungkin terasa sulit, dengan latihan dan pemahaman konsep dasarnya, DP akan menjadi salah satu alat paling berharga dalam toolbox penyelesaian masalah Anda.

Nah, sekarang giliran Anda! Apakah Anda pernah mencoba menyelesaikan masalah menggunakan Dynamic Programming? Masalah apa yang paling menarik atau menantang bagi Anda? Bagikan pengalaman atau pertanyaan Anda di kolom komentar di bawah!