🧩
Desain dan Analisis Algoritma

Dynamic Programming

Optimal Substructure · Overlapping Subproblems

Fokus
Optimisasi
Meminimalkan biaya, memaksimalkan nilai
Teknik
Memoization
Top-down dengan cache
Teknik
Tabulation
Bottom-up dengan tabel
Definisi & Intuisi

Apa itu Dynamic Programming?

Dynamic Programming (DP) adalah teknik untuk menyelesaikan masalah kompleks dengan memecahnya menjadi submasalah yang saling tumpang tindih, menyelesaikan setiap submasalah sekali, lalu menyimpan hasilnya agar bisa digunakan kembali. [web:111][web:116]

DP biasanya digunakan pada masalah optimisasi atau penghitungan, ketika:

  • • Masalah memiliki optimal substructure. [web:110][web:113]
  • • Masalah memiliki overlapping subproblems. [web:107][web:116]

Alih‑alih menghitung ulang subproblem yang sama berkali‑kali (seperti recursion naif), DP menyimpan jawaban subproblem di tabel/array. [web:111][web:108]

Optimal Substructure & Overlapping

  • Optimal Substructure: solusi optimal masalah dapat dibangun dari solusi optimal submasalahnya (contoh: shortest path, knapsack, LCS). [web:110][web:113][web:111]
  • Overlapping Subproblems: recursive solution yang naif akan menghitung subproblem yang sama berkali‑kali. [web:107][web:116]

Jika kedua sifat ini ada, biasanya DP adalah kandidat kuat. [web:110][web:116]

DP vs Divide and Conquer

Hubungan dengan Divide and Conquer

DP bisa dianggap sebagai Divide and Conquer + caching, ketika submasalah saling tumpang tindih dan kita ingin menghindari perhitungan ulang. [web:112][web:115]

Aspek Divide and Conquer Dynamic Programming
Submasalah Cenderung independen (jarang dipakai ulang). [web:112][web:115] Sering berulang (overlapping). [web:107][web:116]
Teknik Top‑down rekursif tanpa cache. Top‑down dengan memoization atau bottom‑up dengan tabulation. [web:111][web:108]
Contoh Merge Sort, Quick Sort, Closest Pair. [web:112] Fibonacci, Knapsack, LCS, Matrix Chain, Shortest Path. [web:111][web:108][web:114]
Kinerja Sering O(n log n) atau sejenis. Sering mengubah exponential → polynomial. [web:111][web:108]
Dua Teknik Implementasi

Memoization vs Tabulation

Memoization (Top‑Down)

  • • Tulis solusi rekursif seperti biasa. [web:111]
  • • Tambahkan struktur data (array/map) untuk menyimpan hasil subproblem. [web:111]
  • • Sebelum menghitung subproblem, cek dulu apakah nilai sudah pernah dihitung. [web:111]
  • • Menjaga alur pikir rekursif, mudah dihubungkan dengan definisi matematis. [web:111]

Tabulation (Bottom‑Up)

  • • Tentukan urutan pengisian tabel sehingga ketika menghitung dp[i], semua subproblem yang diperlukan sudah terisi. [web:111][web:108]
  • • Biasanya memakai loop iteratif (for/while). [web:108]
  • • Tidak menggunakan call stack yang dalam, sering lebih hemat overhead. [web:111]
  • • Mudah dioptimasi ruang (space optimization) karena pola akses teratur. [web:108]
Contoh 1 — Fibonacci

Dari Rekursi Eksponensial ke Linear

Deret Fibonacci didefinisikan sebagai: F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2) untuk n ≥ 2. [web:111]

Implementasi rekursif naif memiliki kompleksitas O(2ⁿ) karena banyak subproblem berulang (misal F(3) dihitung berkali‑kali). [web:111][web:107]

Dengan DP, kita simpan hasil F(k) untuk semua k ≤ n sehingga setiap nilai dihitung sekali → O(n) waktu, bisa dioptimasi jadi O(1) ruang. [web:111][web:108]

// Versi tabulation (bottom-up) function fib(n): if n ≤ 1: return n dp[0] ← 0 dp[1] ← 1 for i ← 2 to n: dp[i] ← dp[i-1] + dp[i-2] return dp[n] // Kompleksitas waktu: O(n), ruang: O(n) (bisa O(1) jika hanya simpan 2 nilai)
Contoh 2 — 0/1 Knapsack

Optimisasi Nilai dalam Batas Kapasitas

Diberikan n item, masing‑masing dengan berat wᵢ dan nilai vᵢ, serta kapasitas knapsack W. Cari subset item untuk memaksimalkan nilai total dengan total berat ≤ W. [web:111][web:108]

Definisi state: dp[i][w] = nilai maksimum yang bisa didapat dengan mempertimbangkan item 1..i dan kapasitas w. [web:108][web:114]

Transisi:

  • • Jika wᵢ > w → tidak bisa ambil item i → dp[i][w] = dp[i−1][w]. [web:108]
  • • Jika wᵢ ≤ w → dp[i][w] = max(dp[i−1][w], vᵢ + dp[i−1][w−wᵢ]). [web:108][web:111]
// DP bottom-up untuk 0/1 Knapsack function knapsack(weights, values, W): n ← panjang(weights) buat array dp[0..n][0..W] berisi 0 for i ← 1 to n: for w ← 0 to W: if weights[i-1] > w: dp[i][w] ← dp[i-1][w] else: dp[i][w] ← max( dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]] ) return dp[n][W] // Kompleksitas: O(nW) waktu, O(nW) ruang
Contoh 3 — Longest Common Subsequence

LCS: Menemukan Kemiripan Dua String

LCS dari dua string X dan Y adalah subsekuens terpanjang yang muncul di keduanya (tidak harus kontigu). Contoh: LCS("ABCDGH", "AEDFHR") = "ADH". [web:111][web:108]

Definisi state: dp[i][j] = panjang LCS dari X[1..i] dan Y[1..j]. [web:108][web:111]

  • • Jika X[i] = Y[j] → dp[i][j] = 1 + dp[i−1][j−1]. [web:108]
  • • Jika X[i] ≠ Y[j] → dp[i][j] = max(dp[i−1][j], dp[i][j−1]). [web:108]
  • • Basis: dp[i][0] = dp[0][j] = 0. [web:108]

Kompleksitas: O(mn) waktu dan ruang, di mana m, n panjang kedua string. [web:111][web:108]

// DP bottom-up untuk LCS length function LCS(X, Y): m ← panjang(X); n ← panjang(Y) buat array dp[0..m][0..n] berisi 0 for i ← 1 to m: for j ← 1 to n: if X[i-1] = Y[j-1]: dp[i][j] ← 1 + dp[i-1][j-1] else: dp[i][j] ← max(dp[i-1][j], dp[i][j-1]) return dp[m][n]
Langkah Umum Merancang DP

Recipe Dynamic Programming

  1. 1. Identifikasi optimal substructure dan overlapping subproblems. Analisis solusi rekursif: apakah solusi besar dapat ditulis dari solusi kecil, dan apakah subproblem berulang? [web:110][web:107][web:116]
  2. 2. Definisikan state DP yang tepat. Misalnya dp[i], dp[i][j], dp[pos][state_bitmask], dll. Pastikan state cukup untuk mewakili “keadaan” yang diperlukan. [web:111][web:114]
  3. 3. Tulis relasi rekurens (transition). Bagaimana dp state besar dinyatakan dari kombinasi beberapa state yang lebih kecil. [web:108][web:111]
  4. 4. Tentukan base case. Nilai dp untuk kasus terkecil (misal 0 elemen, string kosong, kapasitas 0). [web:111]
  5. 5. Pilih memoization atau tabulation. Implementasikan sesuai kebutuhan (rekursif/top‑down atau iteratif/bottom‑up). [web:111][web:108]
  6. 6. (Opsional) Rekonstruksi solusi. Simpan pointer/keputusan agar bisa mengembalikan solusi konkret, bukan hanya nilai optimum. [web:111][web:114]
Aplikasi DP Populer

Beberapa Problem Klasik Dynamic Programming

🔢

Fibonacci & Deret

Menghitung suku ke‑n deret rekursif dengan time O(n) alih‑alih eksponensial. [web:111][web:108]

🧳

0/1 Knapsack

Optimisasi pilihan item dalam batas kapasitas. [web:111][web:108]

📏

Matrix Chain Multiplication

Cari urutan pengalian matriks dengan biaya minimum. [web:111]

📄

LCS & Edit Distance

Mengukur kemiripan string, dipakai untuk DNA alignment dan diff. [web:111][web:108]

🛣️

Shortest Path (DAG / Floyd‑Warshall)

Hitung jarak terpendek di graf dengan teknik DP di atas edge/vertex. [web:111][web:114]

🧠

DP di Competitive Programming

Problem kombinatorial (counting, path, subsets, bitmask, dll.). [web:114]

Kesimpulan

Inti Dynamic Programming

Dynamic Programming memanfaatkan struktur optimal dan submasalah yang tumpang tindih untuk mengurangi kompleksitas waktu secara drastis. Kunci keberhasilan DP adalah merancang state dan relasi rekurens yang tepat.

🧠
Paradigma
Pikirkan dari sudut pandang “state” dan “transition”.
📊
Tabel
Gunakan tabel atau cache untuk menyimpan jawaban subproblem.
🚀
Dampak
Mengubah solusi eksponensial menjadi polinomial di banyak problem klasik.
1 / 10