Fibonacci series: the complexity of the recursion function is O(2^n)

Fibonacci series: the complexity of the recursion function is O(2^n)

Use dp we can reduce complexity to O(n)

int f(int num,int* a)
{
 if(num<0) return 0; 
 if(num==1){a[num]=1; return 1;}
 
 a[num]=f(num-1,a)+a[num-2];
 return a[num];
}
int main()
{
 int num=5;
 int* a=(int*) malloc(sizeof(int)*(num+1));
 for(int i=0;i<=num;i++)
  a[i]=1;
 cout << f(num,a);
}