Exercise $3$

Dynamic Programming

Write a program that calculates the nth Fibonacci number using dynamic

programming. The Fibonacci sequence is defined as follows:

$(0)=0$

$(1)=1$

$2,()=(1)+(2)$

Your program should use a dynamic programming approach to store intermediate

results and avoid redundant computations. Specifically:

$1.$ Implement the solution using a bottom$-$up approach $($iterative$).$

$2.$ The input to the program should be an integer n $($where n $>=0).$

$3.$ Your solution should achieve a time complexity of $().$

Write the pseudocode for the algorithm and explain its time and space complexity.