What is the best solution?

#1

Is there a better solution than making all the pairs and counting the ones which follow the rule?

#2

@tusharnitharwal
hello Tushar,
yeah we do have O(n) dp approach for this problem.

#3

I want to know without dp, using recursion

#4

@tusharnitharwal

we have this recurrence relation for the given problem -> f(n)=f(n-1)+f(n-2) and its time complexity will be roughly O(2^n) . and we dont have any other solution using recusion.

also if u will notice the recurrence relation carefully then u will realise that it is nothing but nth fibonacci number,

#5

I thought since it was given in the recursion challenge section, there must be a solution using recursion as well

#6

@tusharnitharwal
I have mentioned about recursive solution as well .pls check my previous post

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.