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);
}

There are a total of N steps in a stair. You can either take one or two steps at a time. Write efficient code to print all possible ways of climbing.

There are a total of N steps in a stair. You can either take one or two steps at a time. Write efficient code to print all possible ways of climbing.

Use recursion, each time we have two choices, taking one step or taking two steps, so we have Fibonacci number ways to reach final

int foo(int n)
{
if(n<0) return 0;
if(n==0) return 1;
return f(n-1)+f(n-2);
}
//s(n)=s(n-1)+s(n-2)
//s(1)=1;s(2)=2