0509._Fibonacci_Number.md

509. Fibonacci Number

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/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.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

top-down(memorize)

class Solution:
    cache = {
        0: 0,
        1: 1
    }
    def fib(self, N):
        """
        :type N: int
        :rtype: int
        """
        def helper(n):
            if n in self.cache:
                return self.cache[n]
            else:
                self.cache[n] = self.fib(n-1) + self.fib(n-2)
                return self.cache[n]
            
        return helper(N)

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

bottom up(tabulation)

class Solution:
    def fib(self, N):
        """
        :type N: int
        :rtype: int
        """
        fibs = [0, 1, 1]
        if N < 3:
            return fibs[N]
        for k in range(2, N+1):
            fibs[2] = fibs[0] + fibs[1]
            fibs[0], fibs[1] = fibs[1], fibs[2]
        return fibs[2]

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(N)******

import functools
class Solution:
    @functools.lru_cache(maxsize=None)
    def fib(self, N):
        """
        :type N: int
        :rtype: int
        """
        if N <= 1:
            return N
        else:
            return self.fib(N - 1) + self.fib(N - 2)