Algorithm Puzzles: Fibonacci Number

Posted on Edited on In Views: Word count in article: 81 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Fibonacci Number

Puzzle

Puzzle from leetcode:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
 public:
  int fib(int n) {
    if (n <= 1) {
      return n;
    }
    if (fn[n] == 0) {
      fn[n] = fib(n - 1) + fib(n - 2);
    }
    return fn[n];
  }

 private:
  int fn[30] = {0};
};

T.C.: O(N)