Dynamic Programming —
Lengkap & Contoh
Definisi, Karakteristik, Pendekatan
(Top‑Down & Bottom‑Up), Contoh,
dan Visual
Dibuat untuk presentasi singkat dan
1. Definisi
• Dynamic Programming (DP) adalah teknik pemecahan masalah dengan cara
memecah problem menjadi submasalah yang lebih kecil,
• menyimpan hasil submasalah (cache) sehingga tidak perlu dihitung ulang, dan
menggunakan hasil tersebut untuk membangun solusi akhir.
• Cocok untuk masalah yang memiliki: optimal substructure dan overlapping
subproblems.
2. Karakteristik Pemrograman
Dinamis
• • Optimal substructure: solusi optimal masalah dapat dibentuk dari solusi optimal
submasalahnya.
• • Overlapping subproblems: submasalah yang sama muncul berulang-ulang.
• • Dua teknik implementasi: Memoization (Top-Down) & Tabulation (Bottom-Up).
• • Mempercepat perhitungan dengan menyimpan hasil submasalah (time-space
tradeoff).
3. Pendekatan DP — Penjelasan
Lengkap
• Top‑Down (Backward) / Memoization:
• • Mulai dari masalah utama, pecah menjadi submasalah rekursif.
• • Simpan (cache) hasil submasalah saat pertama kali dihitung.
• • Biasanya implementasi rekursif.
• Bottom‑Up (Forward) / Tabulation:
• • Bangun solusi dari submasalah terkecil ke yang lebih besar.
• • Gunakan tabel/array untuk menyimpan hasil.
• • Biasanya implementasi iteratif, lebih hemat overhead stack.
4. Kapan Pakai Top‑Down vs
Bottom‑Up?
• Top‑Down (Memoization):
• • Kode lebih mudah ditulis dari solusi rekursif.
• • Berguna kalau hanya sebagian submasalah yang diperlukan.
• • Potensi overhead rekursi dan memori untuk call stack.
• Bottom‑Up (Tabulation):
• • Lebih cepat pada umumnya (tanpa overhead rekursi).
• • Kontrol memori dan urutan komputasi lebih jelas.
• • Kadang lebih sulit merancang urutan pengisian tabel.
Contoh 1: Fibonacci (kursus
singkat)
• Masalah: F(n) = F(n-1) + F(n-2), dengan F(0)=0, F(1)=1.
• Top‑Down (Memoization) — Python:
– def fib_td(n, memo={}):
• if n in memo:
• return memo[n]
• if n < 2:
• return n
– memo[n] = fib_td(n-1, memo) + fib_td(n-2, memo)
• return memo[n]
• Bottom‑Up (Tabulation) — Python:
– def fib_bu(n):
• if n < 2:
• return n
– table = [0]*(n+1)
– table[0], table[1] = 0, 1
– for i in range(2, n+1):
– table[i] = table[i-1] + table[i-2]
• return table[n]
Contoh 2: 0/1 Knapsack (Ide &
Pseudocode)
• Masalah: Pilih item (weight, value) untuk maks. value tanpa melebihi kapasitas W.
• Karena subproblem berulang (kapasitas dan item indeks), DP cocok.
• Tabulation (iteratif) — konsep:
• • Buat tabel dp[i][w] = maksimum nilai menggunakan item 0..i dengan kapasitas
w.
• • Transisi: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi) jika wi<=w.
• Top‑Down (rekursif) — konsep:
• • Rec(i, w) = max( Rec(i-1, w), Rec(i-1, w-wi) + vi )
Kompleksitas & Trade‑offs
• • Time complexity: sering O(#subproblems × cost_per_transition). Contoh:
knapsack O(n*W).
• • Space complexity: ukuran tabel/memo (bisa dioptimalkan dengan rolling array).
• • Trade‑off: waktu vs memori — DP menyimpan hasil untuk mempercepat
eksekusi.
• • Debugging: mulai dengan definisi subproblem yang jelas dan transisi rekurens.
Tips untuk Presentasi & Visual
• • Gunakan diagram panah untuk tunjukkan hubungan submasalah.
• • Bandingkan rekursi vs tabel dengan gambar call tree dan matrix.
• • Sertakan satu contoh kecil (n=6) dan tunjukkan pengisian tabel step ‑by ‑step.
• • Gunakan warna untuk menyoroti subproblem yang berulang.
Ringkasan
• • DP = pecah masalah → simpan hasil → gabungkan.
• • Dua pendekatan: Top‑Down (memo) & Bottom‑Up (tabulasi).
• • Pilih pendekatan sesuai masalah: kemudahan implementasi atau efisiensi.
• • Contoh: Fibonacci (sederhana) dan Knapsack (nyata).