Penjelasan dynamic programming: cara kerja, kode, dan contoh

Masalah yang diselesaikan dynamic programming

Banyak masalah menanyakan yang terbaik, termurah, atau jumlah cara: koin paling sedikit untuk membentuk suatu nominal, longest common subsequence dari dua string, himpunan barang paling bernilai yang muat di dalam tas, jumlah jalur melintasi grid. Solusi rekursif langsung sering menghitung ulang kasus kecil yang sama sebanyak eksponensial. DP menghilangkan pengulangan itu.

Namanya berasal dari Richard Bellman, yang mengembangkan metode ini pada 1950-an. "Programming" di sini berarti perencanaan atau pengisian tabel, bukan menulis kode.

Ide dasar dengan kata-kata sederhana

Fibonacci rekursif yang naif memperlihatkan masalahnya. fib(5) memanggil fib(4) dan fib(3), lalu fib(4) memanggil fib(3) lagi, dan seterusnya: jumlah pemanggilan tumbuh secara eksponensial. Menyimpan setiap hasil saat pertama kali dihitung membuat setiap pemanggilan berikutnya instan.

1. Tentukan state: seperti apa sebuah subproblem? Misalnya best[a] = koin paling sedikit untuk membentuk nominal a.
2. Tulis rekurensi: bagaimana sebuah state dihitung dari state yang lebih kecil? best[a] = 1 + min(best[a - c] for each coin c).
3. Tetapkan kasus dasar: best[0] = 0.
4. Pilih urutan: top-down dengan memoization, atau bottom-up sehingga state yang lebih kecil selalu terisi lebih dulu.
5. Baca jawaban dari state yang tepat, dan rekonstruksi pilihan sebenarnya bila diperlukan.

Top-down: memoization dengan functools

Di Python, functools.cache (Python 3.9+) atau functools.lru_cache menambahkan memoization pada fungsi hanya dengan satu baris:

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(80))  # 23416728348467685

Tanpa decorator, fib(80) akan melakukan lebih dari 10¹⁶ pemanggilan rekursif. Dengan decorator, setiap nilai dari 0 sampai 80 dihitung sekali.

Contoh: coin change, bottom-up

Koin 1, 3, dan 4; nominal 6. Pendekatan greedy mengambil 4 lebih dulu dan membutuhkan 4 + 1 + 1 = 3 koin, padahal 3 + 3 hanya memakai 2. DP menemukan minimum sebenarnya dengan mengisi best[a] untuk a = 0 sampai 6:

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

print(min_coins([1, 3, 4], 6))  # 2
print(min_coins([2], 3))        # -1

nominal

O(nominal × jumlah koin)

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

print(lcs("ABCBDAB", "BDCABA"))  # 4

O(nominal)

LCS / edit distance

The general rule: time = number of states × work per state; space = number of states stored.

Tidak. Rekursi adalah cara menulis kode; DP adalah gagasan menyelesaikan setiap subproblem sekali dan memakai ulang hasilnya. Solusi DP bisa rekursif dengan memoization atau iteratif dengan tabel.

Apa perbedaan dynamic programming dan algoritma greedy?

• Algoritma greedy mengambil satu pilihan terbaik secara lokal di setiap langkah dan tidak pernah menimbang ulang. DP mempertimbangkan semua pilihan yang relevan untuk setiap subproblem dan menyimpan yang terbaik, sehingga benar pada kasus ketika greedy gagal.
• Apa perbedaan dynamic programming dan divide and conquer?
• Keduanya membagi masalah menjadi subproblem. Divide and conquer bekerja pada subproblem yang independen, sedangkan DP untuk subproblem yang tumpang tindih, sehingga menyimpan hasilnya menghemat kerja.
• Deep recursion: a memoized recursion over 10,000 states can exceed Python's recursion limit; switch to bottom-up.
• Unhashable arguments: functools.cache needs hashable arguments, so pass tuples instead of lists.

Typical interview and real-world uses: climbing stairs, house robber, longest increasing subsequence, word break, unique paths in a grid, edit distance, knapsack, matrix chain multiplication; in practice, sequence alignment in bioinformatics, diff tools, spell checkers, speech recognition (the Viterbi algorithm) and shortest paths such as Bellman-Ford.