Pemrograman dinamis (DP) menyelesaikan masalah dengan submasalah yang tumpang tindih dan sustruktur optimal dengan menghitung setiap submasalah sekali dan menggunakan kembali hasilnya. Dua gaya adalah memoization (atas-bawah) dan tabulation (bawah-atas).
Rekursi naif menghitung ulang submasalah yang sama secara eksponensial. DP menyimpannya, mengubah pekerjaan eksponensial menjadi polinomial.
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| Memoization | Tabulation | |
|---|---|---|
| Arah | rekursi atas-bawah | iterasi bawah-atas |
| Menghitung | hanya keadaan yang diperlukan | semua keadaan |
| Risiko | stack overflow | tidak ada |
| Ruang | dapat dipangkas | sering dapat dikurangi ke O(1) baris |
Fibonacci: dari O(2ⁿ) naif ke O(n) waktu, O(n) (atau O(1)) ruang.
Gunakan DP ketika submasalah tumpang tindih. Tentukan keadaan dan pengulangan dengan hati-hati — itulah bagian yang sulit. Jika submasalah tidak tumpang tindih, divide-and-conquer biasa sudah cukup.
DP mengubah masalah eksponensial yang tidak dapat ditangani — jalur terpendek, jarak edit, knapsack — menjadi masalah yang efisien.
Kemampuan mengidentifikasi keadaan dan pengulangan adalah salah satu yang paling dihargai dalam wawancara algoritma.
Ini mendasari sistem nyata dari alat diff hingga penyelarasan urutan bioinformatika.