Recursion is most famous solution for the Fibonacci number. But it's complexity is higher. It is 2^n. Is what can be better optimal solution. And Answer is Dynamic Programming. We can solve the problem in o(n). But for this we need to use space complexity. We will be saving our previous record to the memory. Let's see..
========================================
=========================================
=========================================
Initialize our array with certain length
========================================
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
========================================
We will manually assign 1 and 1 to the position 0 and 1 of array. Because we know in Fibonacci Series 1st and 2nd index is 1.
========================================
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
========================================
now we will iterate through 2 to n and add (n-1) + (n-2) and save it to memory. Which we do is our recursive solution as well. So our array looks like this.
=========================================
| 1 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
=========================================
we continue iterating it.
=========================================
| 1 | 1 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
=========================================
:
\/
finally it looks like this
==========================================================
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | 610 | 987 | 1597 |
==========================================================
Below is Java code:
public static void main(String[] args) {
Scanner in = new Scanner(System.in); // Taking input from console
int q = in.nextInt();
int[] arr = new int[q]; // Initializing array
arr[0]= arr[1] = 1; // Setting 0 and 1st pos to 1
System.out.print(arr[0]+" "+arr[1]+" "); printing 0th and 1st pos
for(int i = 2; i<q;i++){ //iterating from 2nd to size
arr[i] = arr[i-1]+arr[i-2]; // adding last two values
System.out.print(arr[i]+" "); //Printing value
}
}
