32
x[0] = x[1] = 1
Function fib(n)
If x[n] belum diinisialisasikan
Then x[n] = fib(n-1) + fib(n-2)
Return x[n]
Teknik
menyimpan nilai-nilai
fib()
yang
sudah
dihitung
ini
disebut
juga
dengan
memoization,
ini
adalah pendekatan top-down
karena problem
yang
ada
dipecah-pecah menjadi
beberapa subproblem, yang kemudian dihitung dan hasilnya disimpan ke dalam array.
Sedangkan dalam
pendekatan
bottom-up,
nilai
dari
fungsi
fib()
yang
lebih
kecil
akan
dihitung
terlebih
dahulu,
kemudian nilai
fib(n)
untuk
n
yang
lebih
besar
akan
dihitung
berdasarkan
nilai-nilai
tersebut,
seperti
pada
pseudocode
di
bawah
ini:
(implementasi
jenis
ini
lebih menghemat tempat, karena tidak memerlukan array khusus untuk menyimpan hasil fib(n))
Function fib(n)
Var fib0 = 1, fib1 = 1, fib2
For i = 1 to n – 1 do
fib2 = fib0 + fib1
fib0 = fib1
fib1 = fib2
End For
Return fib1
Dalam
kedua
contoh
implementasi dynamic
programming
di
atas,
fib(2)
dan
fib(3)
masing-masing
hanya
dihitung
sekali,
dan
kemudian
digunakan
untuk
menghitung fib(4)
tanpa
harus menghitungnya kembali.
 |