inal grade. 1. (Basic) Recall that the The Fibonacci Sequence is 0, 1,1, 2, 3, 5, 8, 13, 21, 34, - 2) for all i > 2, where f(i) Formally, f(0)-0./(1)-1 and f(i)-f(i-1) + f(i denotes the ith Fibonacci number We saw the following naive pseudo-code/implementation of the function returns the n the Fibonacci number: int F(n) ifn-0 return 0 if n1 return 1 return F (n-2) F(n-1) However, the running time is exponential in n. We can improve the running time to O(n) using DP. There are typically two equivalent ways to implement a DP approach, i) bottom-up method and ii) top-doum with memoization. Give a pseudo-code of cach implementation. bottom up int F(n) Array AIO nl for i-2; i