Fibonnaci

Question 1

Fibonacci with Dynamic Programming Memoization

Answer 1

Before ever calling Fib, initialize:
1: for i ← 0 to m do memo[i] ← −1
Function Fib(n, m) // Note: n ≤ m
1: if memo[n] ̸= −1 then return memo[n]
2: if n ≤ 1 then ret ← n mod m
3: else
4: ret ← (Fib(n−1, m) + Fib(n−2, m)) mod m
5: memo[n] ← ret
6: return ret

Time Complexity: O(n)
Space Complexity: O(n)