Quy hoạch động: vì sao fib(45) mất 2,74 giây với đệ quy nhưng 625 nano giây với memoization
Đệ quy ngây thơ tính Fibonacci gọi hàm 3,67 tỉ lần cho fib(45) và mất gần 3 giây — vì nó tính đi tính lại cùng một giá trị. Bài này đo thật trong go-lab: thêm một mảng nhớ (memoization) biến O(2^n) thành O(n), nhanh hơn ~4 triệu lần, và giải được fib(90) trong 667 ns. Kèm so sánh memoization với tabulation và đánh đổi bộ nhớ.