Dynamic Programming (DP) adalah teknik penyelesaian masalah yang memecah masalah menjadi submasalah yang tumpang tindih lalu menyimpan hasil submasalah agar tidak dihitung ulang. DP menjembatani recursion murni yang lambat karena overlapping subproblems dan greedy yang tidak selalu optimal. Pada chapter ini kita akan membandingkan dua gaya implementasi di Kotlin—memoization (top-down) dan tabulation (bottom-up)—lalu menerapkannya pada Fibonacci, 0/1 knapsack, Longest Common Subsequence, dan minimum coin change. Pembaca akan melihat bagaimana DP mengubah kompleksitas Fibonacci dari O(2ⁿ) menjadi O(n).

Dua Pendekatan DP #

AspekMemoization (Top-down)Tabulation (Bottom-up)
ArahDari masalah utama ke base caseDari base case ke masalah utama
ImplementasiRecursion + cacheLoop iteratif + tabel
KomputasiHanya submasalah yang dibutuhkanSemua submasalah sampai target
Memori call stackBerisiko overflow untuk n besarAman (tanpa recursion)
KeterbacaanLebih dekat ke rumus rekursifLebih eksplisit
kotlin Memoization vs tabulation 
// Top-down: simpan hasil di map, panggil rekursif
val memo = mutableMapOf<Int, Long>()
fun fibMemo(n: Int): Long {
    if (n <= 1) return n.toLong()
    if (n in memo) return memo[n]!!
    val r = fibMemo(n - 1) + fibMemo(n - 2)
    memo[n] = r
    return r
}

// Bottom-up: isi tabel dari awal
fun fibTab(n: Int): Long {
    val dp = LongArray(n + 1)
    dp[0] = 0; dp[1] = 1
    for (i in 2..n) dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
}

Implementasi Dynamic Programming #

kotlin 
// Demo Dynamic Programming: memoization vs tabulation, dengan contoh Fibonacci, knapsack, longest common subsequence.

// === Top-down: Fibonacci dengan memoization ===
val memoFib = mutableMapOf<Int, Long>()
fun fibMemo(n: Int): Long {
    if (n <= 1) return n.toLong()
    if (memoFib.containsKey(n)) return memoFib[n]!!
    val result = fibMemo(n - 1) + fibMemo(n - 2)
    memoFib[n] = result
    return result
}

// === Bottom-up: Fibonacci dengan tabulation ===
fun fibTab(n: Int): Long {
    if (n <= 1) return n.toLong()
    val dp = LongArray(n + 1)
    dp[0] = 0
    dp[1] = 1
    for (i in 2..n) dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
}

// === Bottom-up dengan space optimization ===
fun fibOptimized(n: Int): Long {
    if (n <= 1) return n.toLong()
    var prev2 = 0L
    var prev1 = 1L
    for (i in 2..n) {
        val curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    }
    return prev1
}

// === 0/1 Knapsack DP ===
fun knapsack01(berat: IntArray, nilai: IntArray, kapasitas: Int): Int {
    val n = berat.size
    // dp[i][w] = nilai maksimum memilih dari item 0..i-1 dengan kapasitas w
    val dp = Array(n + 1) { IntArray(kapasitas + 1) }
    for (i in 1..n) {
        for (w in 0..kapasitas) {
            dp[i][w] = if (berat[i - 1] <= w) {
                maxOf(dp[i - 1][w], dp[i - 1][w - berat[i - 1]] + nilai[i - 1])
            } else {
                dp[i - 1][w]
            }
        }
    }
    return dp[n][kapasitas]
}

// === Longest Common Subsequence (LCS) ===
fun lcs(a: String, b: String): Int {
    val m = a.length
    val n = b.length
    val dp = Array(m + 1) { IntArray(n + 1) }
    for (i in 1..m) {
        for (j in 1..n) {
            dp[i][j] = if (a[i - 1] == b[j - 1]) {
                dp[i - 1][j - 1] + 1
            } else {
                maxOf(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }
    return dp[m][n]
}

// === Coin change: minimum koin untuk jumlah tertentu ===
fun minCoinDP(amount: Int, pecahan: IntArray): Int {
    val dp = IntArray(amount + 1) { Int.MAX_VALUE }
    dp[0] = 0
    for (i in 1..amount) {
        for (p in pecahan) {
            if (p <= i && dp[i - p] != Int.MAX_VALUE) {
                dp[i] = minOf(dp[i], dp[i - p] + 1)
            }
        }
    }
    return if (dp[amount] == Int.MAX_VALUE) -1 else dp[amount]
}

fun main() {
    println("=== Demo Dynamic Programming ===")

    println("--- Fibonacci ---")
    println("Top-down (memoization):")
    for (n in listOf(10, 20, 30, 40, 50)) {
        memoFib.clear()
        println("  fib($n) = ${fibMemo(n)}")
    }

    println()
    println("Bottom-up (tabulation):")
    for (n in listOf(10, 20, 30, 40, 50)) {
        println("  fib($n) = ${fibTab(n)}")
    }

    println()
    println("Bottom-up optimized (space O(1)):")
    for (n in listOf(50, 90)) {
        println("  fib($n) = ${fibOptimized(n)}")
    }

    println()
    println("--- 0/1 Knapsack ---")
    val berat = intArrayOf(2, 3, 4, 5)
    val nilai = intArrayOf(3, 4, 5, 6)
    val kapasitas = 5
    println("Berat: ${berat.toList()}, Nilai: ${nilai.toList()}, Kapasitas: $kapasitas")
    println("Nilai maksimum: ${knapsack01(berat, nilai, kapasitas)}")

    println()
    println("--- Longest Common Subsequence ---")
    val pairs = listOf(
        "ABCBDAB" to "BDCAB",
        "kotlin" to "otin",
        "AGGTAB" to "GXTXAYB"
    )
    pairs.forEach { (a, b) ->
        println("LCS(\"$a\", \"$b\") = ${lcs(a, b)}")
    }

    println()
    println("--- Coin change (minimum koin) ---")
    val pecahan = intArrayOf(1, 3, 4)
    for (amt in listOf(6, 7, 10, 11)) {
        println("Amount $amt dengan pecahan ${pecahan.toList()}: ${minCoinDP(amt, pecahan)} koin")
    }

    println()
    println("--- Perbandingan: greedy vs DP untuk pecahan [1,3,4], target 6 ---")
    println("Greedy (akan salah): 3 koin (4+1+1)")
    println("DP (optimal): ${minCoinDP(6, intArrayOf(1, 3, 4))} koin (3+3)")
}

Output yang Dihasilkan:

text 
=== Demo Dynamic Programming ===
--- Fibonacci ---
Top-down (memoization):
  fib(10) = 55
  fib(20) = 6765
  fib(30) = 832040
  fib(40) = 102334155
  fib(50) = 12586269025

Bottom-up (tabulation):
  fib(10) = 55
  fib(20) = 6765
  fib(30) = 832040
  fib(40) = 102334155
  fib(50) = 12586269025

Bottom-up optimized (space O(1)):
  fib(50) = 12586269025
  fib(90) = 2880067194370816120

--- 0/1 Knapsack ---
Berat: [2, 3, 4, 5], Nilai: [3, 4, 5, 6], Kapasitas: 5
Nilai maksimum: 7

--- Longest Common Subsequence ---
LCS("ABCBDAB", "BDCAB") = 4
LCS("kotlin", "otin") = 4
LCS("AGGTAB", "GXTXAYB") = 4

--- Coin change (minimum koin) ---
Amount 6 dengan pecahan [1, 3, 4]: 2 koin
Amount 7 dengan pecahan [1, 3, 4]: 2 koin
Amount 10 dengan pecahan [1, 3, 4]: 3 koin
Amount 11 dengan pecahan [1, 3, 4]: 3 koin

--- Perbandingan: greedy vs DP untuk pecahan [1,3,4], target 6 ---
Greedy (akan salah): 3 koin (4+1+1)
DP (optimal): 2 koin (3+3)

Bedah Kode Baris-per-Baris #

Mari kita amati bagian kunci:

  1. fibMemo (baris 5-11): Cache memoFib menyimpan hasil perhitungan per indeks. Sebelum menjumlahkan fibMemo(n-1) + fibMemo(n-2), function memeriksa apakah n sudah ada di map. Bila ada, hasil langsung dikembalikan tanpa rekursi tambahan—kompleksitas turun dari O(2ⁿ) menjadi O(n).
  2. fibTab (baris 14-21): Membangun array dp dari indeks 0 hingga n secara berurutan. Setiap dp[i] dihitung dari dp[i-1] + dp[i-2] yang sudah pasti tersedia. Tanpa recursion, tidak ada risiko stack overflow dan overhead pemanggilan function lebih rendah.
  3. fibOptimized (baris 24-34): Karena Fibonacci hanya butuh dua nilai sebelumnya, array penuh tidak perlu. Cukup dua variabel prev1 dan prev2 yang diperbarui tiap iterasi. Memori turun dari O(n) menjadi O(1).
  4. knapsack01 (baris 37-51): Tabel dp[i][w] menyimpan nilai maksimum yang dapat dicapai dengan memilih dari item pertama hingga ke-i-1 dan kapasitas w. Transisi: bila berat item ke-i muat, pilih maksimum antara tidak ambil (dp[i-1][w]) atau ambil (dp[i-1][w-berat[i-1]] + nilai[i-1]). Kompleksitas O(n * kapasitas).
  5. lcs (baris 54-68): Tabel dp[i][j] menyimpan panjang LCS dari a[0..i-1] dan b[0..j-1]. Bila a[i-1] == b[j-1], tambah 1 ke dp[i-1][j-1]. Bila beda, ambil maksimum dp[i-1][j] (buang karakter a) atau dp[i][j-1] (buang karakter b). Kompleksitas O(m * n).
  6. minCoinDP (baris 71-82): Inisialisasi dp[0] = 0 (0 koin untuk jumlah 0) dan sisanya Int.MAX_VALUE. Untuk setiap jumlah i, coba setiap pecahan p; bila dp[i-p] valid, dp[i] = min(dp[i], dp[i-p] + 1). Hasil 2 koin untuk amount 6 dengan pecahan [1,3,4] membuktikan DP menemukan solusi optimal yang greedy lewatkan.

Memoization atau Tabulation? #

Memoization lebih intuitif karena langsung mengikuti rumus rekursif dan hanya menghitung submasalah yang benar-benar dibutuhkan—efisien untuk masalah dengan state jarang dicapai. Tabulation lebih cepat secara konstan karena tidak ada overhead pemanggilan function, dan aman dari stack overflow. Untuk produksi, tabulation umumnya lebih disukai kecuali struktur transisi sangat kompleks dan sulit diiterasikan.

Penutup #

Dynamic Programming mengubah algoritma eksponensial menjadi polinomial dengan menyimpan hasil submasalah. Pilihan antara memoization dan tabulation bergantung pada kebutuhan keterbacaan, efisiensi konstan, dan kedalaman recursion. Pada chapter berikutnya kita akan membahas algoritma graph seperti BFS, DFS, dan Dijkstra yang juga banyak memanfaatkan prinsip DP.

Referensi #

Referensi Lanjutan #