Pemrograman dinamis: memo dan tabel

Pemrograman dinamis dipakai ketika masalah punya dua ciri. Pertama, jawaban optimum tersusun dari jawaban optimum submasalahnya. Kedua, submasalah yang sama muncul berulang kali. Rekursi biasa menghitung ulang setiap submasalah setiap kali ia muncul. Pemrograman dinamis menghitungnya sekali, menyimpannya, dan membacanya kembali.

Contohnya menghitung banyaknya cara menaiki n anak tangga bila setiap langkah naik satu atau dua anak tangga. Cara untuk n adalah cara untuk n − 1 ditambah cara untuk n − 2. Ditulis rekursif apa adanya, menghitung n = 30 membuat 2.692.537 panggilan fungsi, karena cara untuk 28, 27, dan seterusnya dihitung ulang berkali-kali. Padahal hanya ada 31 nilai n yang berbeda.

from functools import lru_cache

@lru_cache(maxsize=None)
def cara_dua(n):
    if n <= 1:
        return 1
    return cara_dua(n - 1) + cara_dua(n - 2)

print(cara_dua(30))   # 1346269, dengan 31 perhitungan saja

Ada dua cara menyimpan. Memo (memoization) mempertahankan bentuk rekursif dan menyimpan hasil setiap panggilan; di Python dekorator functools.lru_cache atau functools.cache melakukannya. Tabel (tabulation) membalik arah: isi larik dari submasalah terkecil ke yang terbesar dengan perulangan biasa, sehingga tidak ada rekursi sama sekali. Tabel juga menghindari batas kedalaman rekursi untuk n yang besar. Kelas Riset Operasi Dasar memakai cara yang sama untuk keputusan knapsack; di sini fokusnya pada biaya hitungnya.