My first Magazine pemrograman-kompetitif-dasar | Page 88

7 Dynamic Programming
Algoritma 38 Solusi Memotong Kayu menggunakan top-down .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
function SOLVE (`, r)
if (` > r) then
return 0
end if
if computed[`][r] then
return memo[`][r]
end if
best ← ∞
cost ← L[r + 1] − L[` − 1]
for m ← `, r do
best ← min(best, SOLVE (`, m − 1) + SOLVE (m + 1, r) + cost)
end for
computed[`][r] ← true
memo[`][r] ← best
return best
end function
Jawaban akhirnya ada pada SOLVE (1, N).
Solusi Bottom-Up
Algoritma 39 Solusi Memotong Kayu menggunakan bottom-up .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
function SOLVE ()
. Base case
for ` ← 0, N + 1 do
for r ← 0, ` − 1 do
d p[`][r] ← 0
end for
end for
. Isi "tabel" mulai dari kasus yang kecil
for gap ← 0, N − 1 do
for ` ← 1, N − gap do
r ← ` + gap
best ← ∞
cost ← L[r + 1] − L[` − 1]
for m ← `, r do
best ← min(best, d p[`][m − 1] + d p[m + 1][r] + cost)
end for
d p[`][r] ← best
end for
end for
return d p[1][N]
end function
Perhatikan bahwa implementasi metode bottom-up lebih rumit dibandingkan dengan imple-
mentasi top-down . Hal ini dikarenakan pengisian "tabel" dilakukan secara "tidak biasa". Pada
78