Dynamic programming

Dynamic programming (DP) dipakai untuk masalah dengan dua sifat:

• Submasalah tumpang tindih: submasalah yang sama muncul berkali-kali.
• Substruktur optimal: solusi optimal tersusun dari solusi optimal submasalahnya.

DP menyimpan hasil setiap submasalah supaya cukup dihitung sekali.

Memoisasi dan tabulasi

1from functools import lru_cache23@lru_cache(maxsize=None)4def fib_memo(n):5    if n < 2:6        return n7    return fib_memo(n - 1) + fib_memo(n - 2)89def fib_tabel(n):10    tabel = [0, 1] + [0] * (n - 1)11    for i in range(2, n + 1):12        tabel[i] = tabel[i - 1] + tabel[i - 2]13    return tabel[n]1415print(fib_memo(90), fib_tabel(90))

2880067194370816120 2880067194370816120

• Memoisasi (top-down): tulis rekursi biasa, lalu simpan hasilnya.
• Tabulasi (bottom-up): isi tabel dari submasalah terkecil.

Keduanya Θ(n), sedangkan rekursi tanpa penyimpanan butuh waktu eksponensial.

Merumuskan DP: empat langkah

1. 1Definisikan keadaan. Apa arti dp[i]?
2. 2Tulis transisi. Bagaimana dp[i] dihitung dari keadaan yang lebih kecil?
3. 3Tentukan kasus dasar.
4. 4Tentukan urutan pengisian dan di mana jawaban akhirnya.

Contoh: uang kembalian dengan koin sembarang

Berapa koin minimum untuk membentuk nilai V dengan koin {1, 3, 4}? Greedy gagal untuk V = 6, tetapi DP selalu benar.

• Keadaan: dp[v] = koin minimum untuk membentuk nilai v.
• Transisi: dp[v] = 1 + min(dp[v - c]) untuk setiap koin c ≤ v.
• Kasus dasar: dp[0] = 0.

1def koin_minimum(koin, nilai):2    tak_hingga = float("inf")3    dp = [0] + [tak_hingga] * nilai4    pilihan = [0] * (nilai + 1)5    for v in range(1, nilai + 1):6        for c in koin:7            if c <= v and dp[v - c] + 1 < dp[v]:8                dp[v] = dp[v - c] + 19                pilihan[v] = c10    if dp[nilai] == tak_hingga:11        return None12    hasil = []13    v = nilai14    while v > 0:15        hasil.append(pilihan[v])16        v -= pilihan[v]17    return hasil1819print(koin_minimum([1, 3, 4], 6))20print(koin_minimum([1, 3, 4], 13))21print(koin_minimum([5, 7], 3))

[3, 3]
[1, 4, 4, 4]
None

Kompleksitasnya Θ(V · k) untuk V nilai dan k jenis koin. Array pilihan menyimpan koin yang dipakai, sehingga susunan koinnya bisa direkonstruksi.

Contoh: jumlah subarray terbesar (Kadane)

Keadaan: terbaik_berakhir[i] = jumlah terbesar subarray yang berakhir di indeks i. Transisi: max(a[i], terbaik_berakhir[i - 1] + a[i]).

1def kadane(a):2    berakhir = terbaik = a[0]3    for x in a[1:]:4        berakhir = max(x, berakhir + x)5        terbaik = max(terbaik, berakhir)6    return terbaik78print(kadane([2, -4, 3, -1, 5, -9, 4, 2, -3]))

7

Hasilnya sama dengan versi divide and conquer, tetapi Θ(n) dan memori O(1).

1def cara_naik(n):2    cara = [0] * (n + 1)3    cara[0] = 14    for i in range(1, n + 1):5        cara[i] = sum(cara[i - k] for k in (1, 2, 3) if i - k >= 0)6    return cara[n]78print(cara_naik(10), cara_naik(30))

274 53798080