366. Fibonacci【naive】

Find the Nth number in Fibonacci sequence.

A Fibonacci sequence is defined as follow:

The first two numbers are 0 and 1.
The i th number is the sum of i-1 th number and i-2 th number.

The first ten numbers in Fibonacci sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

Notice

The Nth fibonacci number won't exceed the max value of signed 32-bit integer in the test cases.

Example

Given 1, return 0

Given 2, return 1

Given 10, return 34

解法一：

 1 class Solution {
 2     /**
 3      * @param n: an integer
 4      * @return an integer f(n)
 5      */
 6     public int fibonacci(int n) {
 7         if (n == 1 || n == 2) {
 8             return (n-1);
 9         }
10  
11         return fibonacci(n-1) + fibonacci(n-2);
12  
13     }
14 }

will lead to time limit

解法二：

 1 class Solution {
 2     public int fibonacci(int n) {
 3          // declare an array to store the result
 4          // it has to be n+2 to avoid out_of_bound
 5          int[] f = new int[n+2];
 6          f[1] = 0; // when input is 1 => zero
 7          f[2] = 1; // when input is 2 => 1
 8  
 9          int i = 3;
10          while (i <= n) { // it has to be incremental instead of decremental
11              f[i] = f[i-1] + f[i-2];
12              i++;
13          }
14  
15          return f[n];
16      }
17 }

will need O(n) space, using DP

解法三：

 1 class Solution {
 2     public int fibonacci(int n) {
 3         if (n < 3) {
 4             return n - 1;
 5         } 
 6         
 7         int first = 0;
 8         int second = 1;
 9         int third = 1;
10         
11         int i = 3;
12         while (i <= n) {
13             third = first + second;
14             first = second;
15             second = third;
16             i++;
17         }
18         return third;
19     }
20 }

will only need O(1) space，We can optimize the space used in method 2 by storing the previous two numbers only because that is all we need to get the next Fibannaci number in series