My first Magazine pemrograman-kompetitif-dasar | Page 85

7.2 Contoh-contoh DP Sederhana
Solusi Top-Down
Kita implementasikan d p(i, j) sebagai fungsi SOLVE (i, j).
Algoritma 36 LCS secara top-down .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
function SOLVE (i, j)
if (i = 0 ∨ j = 0) then
return 0
end if
if computed[i][ j] then
return memo[i][ j]
end if
if (A[i] = B[ j]) then
best ← SOLVE (i − 1, j − 1) + 1
else
best ← max( SOLVE (i − 1, j), SOLVE (i, j − 1))
end if
computed[i][ j] ← true
memo[i][ j] ← best
return best
end function
Jawaban akhirnya ada pada SOLVE (M, N).
Solusi Bottom-Up
Algoritma 37 LCS secara bottom-up .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
function SOLVE ()
for i ← 0, M do
. Base case
d p[i][0] ← 0
end for
for j ← 0, N do
d p[0][ j] ← 0
end for
for i ← 1, M do
. Isi "tabel" dari kasus yang kecil ke besar
for j ← 1, N do
if (A[i] = B[ j]) then
d p[i][c] ← d p[i − 1][ j − 1] + 1
else
d p[i][c] ← max(d p[i − 1][ j], d p[i][ j − 1])
end if
end for
end for
return d p[M][N]
end function
75