My first Magazine pemrograman-kompetitif-dasar | Page 83

7.2 Contoh-contoh DP Sederhana
Analisis Kompleksitas
Terdapat O(N) nilai berbeda untuk nilai i dan O(G) nilai berbeda untuk nilai c pada d p(i, c).
Dibutuhkan O(1) untuk menghitung d p(i, c). Sehingga untuk menghitung seluruh nilai d p(i, c)
untuk seluruh i dan c dibutuhkan waktu O(NG).
Solusi Top-Down
Kita implementasikan d p(i, c) sebagai fungsi SOLVE (i, c). Implementasi dapat dilihat pada
Algoritma 34.
Algoritma 34 Coin Change secara top-down .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
function SOLVE (i, c)
if (c = 0) then
return 0
end if
if (i = 0) then
return ∞
end if
if computed[i][c] then
return memo[i][c]
end if
best ← SOLVE (i − 1, c)
if (c ≥ a[i]) then
best ← min(best, SOLVE (i − 1, c − a[i]) + 1)
end if
computed[i][c] ← true
memo[i][c] ← best
return best
end function
Jawaban akhirnya ada pada SOLVE (N, G).
Solusi Bottom-Up
Algoritma 35 Coin Change secara bottom-up .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
function SOLVE ()
for c ← 1, G do
d p[0][c] ← ∞
end for
for i ← 0, N do
d p[i][0] ← 0
end for
for i ← 1, N do
for c ← 0, G do
best ← d p[i − 1][c]
if (c ≥ a[i]) then
. Base case 1
. Base case 2
. Isi "tabel" dari kasus yang kecil ke besar
73