Belajar Algoritm - Dynamic Programming: Fundamentals

#Pendahuluan

Setelah di episode 13 kita membahas Greedy Algorithms dan keterbatasannya, pada episode ini kita masuk ke Dynamic Programming (DP) — paradigma yang paling powerful untuk masalah dengan overlapping subproblems. DP pada dasarnya adalah divide & conquer yang dioptimasi: alih-alih menghitung ulang sub-masalah yang sama berkali-kali, kita menyimpan hasilnya dan menggunakan kembali.

DP adalah paradigma yang paling sering muncul di coding interview karena ia menguji kemampuan berpikir sistematis: mendefinisikan state, menulis transition equation, dan memilih urutan evaluasi. Pada episode ini kita memahami fondasi; episode 15-17 akan membahas pola DP yang lebih spesifik.

#Dua Pilar Dynamic Programming

#Overlapping Subproblems

Sub-masalah yang sama muncul berulang kali dalam rekursi. Tanpa DP, setiap kemunculan dihitung ulang → waktu eksponensial. Dengan DP, setiap sub-masalah hanya dihitung sekali.

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)  ← sub-masalah yang sama muncul berulang

#Optimal Substructure

Solusi optimal masalah besar mengandung solusi optimal dari sub-masalah. Ini memungkinkan kita membangun solusi dari bawah ke atas (tabulation) atau atas ke bawah (memoization).

#Memoization vs Tabulation

#Memoization (Top-Down)

Rekursif dengan cache: hitung secara rekursif, simpan hasil di memo, return dari memo jika sudah dihitung.

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

#Tabulation (Bottom-Up)

Iteratif: bangun tabel dari sub-masalah terkecil ke terbesar, tanpa rekursi.

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

#Perbandingan

#Pola 1D State

Masalah DP 1D: state hanya bergantung pada satu indeks — dp[i] merepresentasikan solusi optimal untuk prefix/suffix hingga posisi i.

#Coin Change (Minimum Koin)

Diberikan denominasi koin dan target amount, cari jumlah minimum koin yang dibutuhkan.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0 koin untuk amount 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    
    return dp[amount] if dp[amount] != float('inf') else -1
 
# coins = [1, 3, 4], amount = 6
# dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=1, dp[4]=1, dp[5]=2, dp[6]=2
# 6 = 3 + 3 → 2 koin (bukan 4+1+1=3 koin seperti greedy)

Transition equation: dp[i] = min(dp[i - coin] + 1) untuk semua coin ≤ i.

Mengapa greedy gagal (episode 13) tetapi DP berhasil: DP mengevaluasi semua kombinasi koin secara sistematis, sedangkan greedy hanya mempertimbangkan koin terbesar. Dengan denominasi [1, 3, 4], greedy memilih 4 dulu (dp[6] = dp[2] + 1 = 3 koin), tetapi DP menemukan 3+3 (dp[6] = dp[3] + 1 = 2 koin).

#Menghitung Jumlah State

Jumlah state = jumlah sub-masalah unik yang harus diselesaikan. Untuk coin change:

• State space: 0 sampai amount → amount + 1 state.
• Per state: loop melalui semua coin → O(coins).
• Total: O(amount × coins).

Memori: O(amount) untuk tabel dp.

#Pola Umum DP 1D

#Penutup

Pada episode 14 ini, kalian telah memahami:

• Dua pilar DP: overlapping subproblems + optimal substructure.
• Memoization (top-down, rekursif + cache) vs tabulation (bottom-up, iteratif).
• Pola 1D state: dp[i] merepresentasikan solusi prefix hingga posisi i.
• Coin change: transition dp[i] = min(dp[i-coin]+1) mengalahkan greedy.
• Menghitung state: langkah pertama untuk menentukan feasibility DP.

Di episode 15 selanjutnya kita akan membahas DP Klasik: Knapsack, LCS, dan Edit Distance — tiga masalah fundamental yang sering muncul di interview dan production. Sampai jumpa di episode 15!