Jabarkan function fib(n) dari Pemrograman dinamis

if n <= 1 return n

return fib(n − 1) + fib(n − 2)

Perhatikan bahwa jika kita sebut, katakanlah, fib(5), kita menghasilkan pohon panggilan yang memanggil fungsi pada nilai yang sama berkali-kali:

(fib(3) + fib(2)) + (fib(2) + fib(1))

((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Khususnya, fib(2) dihitung tiga kali dari awal. Dalam contoh yang lebih besar, lebih banyak nilai fib, atau subproblem, dihitung ulang, yang mengarah ke algoritme waktu eksponensial.

Sekarang, misalkan kita memiliki objek peta sederhana, m, yang memetakan setiap nilai fib yang telah dihitung ke hasilnya, dan kita memodifikasi fungsi kita untuk menggunakannya dan memperbaruinya. Fungsi yang dihasilkan hanya membutuhkan O(n) waktu, bukan waktu eksponensial (tetapi membutuhkan O(n) ruang):

var m := map(0 → 0, 1 → 1)