GuoXin Li's Blog

LeetCode509. Fibonacci Number

字数统计: 440阅读时长: 2 min
2020/12/05 Share

LeetCode 509. Fibonacci Number

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. That is,

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).

Example 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Note: 0 ≤ N ≤ 30.

According to the description of example, it easy to code the straight code following:

1
2
3
4
5
6
7
8
class Solution {
public:
    int fib(int N) {
        if(N == 0) return 0;
      	if(N == 1) return 1;
      	return (fib(N - 1) + fib(N - 2));
    }
};

time complexity: $O(2^n)$ the number of subproblem is $2^n$, and the time subproblem spent is 1

space complexity: $O(1)$

Having a note to memory the value of the node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int fib(int N) {
        if(N < 1) return 0;
        vector<int> mem (N+1, 0);
        return notes(mem, N);
    }
    int notes(vector<int> &mem, int N){
        if(N == 1 || N == 2) return 1;
        if(mem[N] != 0) return mem[N];
        mem[N] = notes(mem, N-1) + notes(mem, N-2);
        return mem[N];
    }
};

time complexity: $O(n)$

space complexity: $O(n)$

If we have a DP table to record the value of different node.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int fib(int N) {
        if(N < 1) return 0;
      	if(N == 1 || N == 2) return 1;
      	vector<int> table(N+1, 0);
      	table[1] = table[2] = 1;
      	for(int i = 3; i < N+1; i++){
          table[N] = table[N-1] + table[N-2];
        }
        return table[N];
    }
};

time complexity: $O(n)$

space complexity: $O(n)$

if we use point to record the previous and current value of the table, just like control a table using point in data structure. Then we can deprecate the table.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int fib(int N) {
        if(N < 1) return 0;
      	if(N == 1 || N == 2) return 1;
      	pre = cur = 1;
      	for(int i = 3; i < N+1; i++){
          int sum = pre + cur;
          pre = cur;
          cur = sum;
        }
        return sum;      
    }
};

then space complexity is $O(1)$

reference: https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/dong-tai-gui-hua-xiang-jie-jin-jie

CATALOG
  1. 1. LeetCode 509. Fibonacci Number
    1. 1.0.1. Example 1:
    2. 1.0.2. Example 2:
    3. 1.0.3. Example 3:
Total : 89
2022
2021
2020
2019
2018
essay Deep Learning Paper-reading learning-note C++ CUDA cmake LeetCode DataStructure Numpy OS-Linux PAT slidingwindow git golang BuaaAssignments CG
Machine-Learning Data-Structure