Leetcode 509. Fibonacci Number (Python)

Related Topic

Dynamic-Programming.

Description

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).

Sample I/O

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.

Methodology

This question solved by Dynamic Programming. It is similar with question 70 70. Climbing Stairs!

1. Find the base case (Already given)

   1. When N = 0, F(0) = 0
   2. When N = 1, F(1) = 1 …. ```

2. Find the pattern (Already given):

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

   The traditional way is using recursion. If so, the BigO is O(2^N), appearently this is bad performance.

   We use dynamic programming to optimaze it to O(n). The basic idea is create a dp list and init all values with a number, apply the base case for the dp list and then update current value (start from index 2) by adding previous two values so the current value become to store the current result.

   The final result will be the last value of the dp list.

Code

def fib(self, N: int) -> int:
        dp = [0 for x in range(N+1)]
        dp[0] = 0
        if N>=1:
            dp[1] = 1
            for x in range(2,N+1):
                dp[x] = dp[x-1]+dp[x-2]
        return dp[-1]

BigO

We iterate all dp array, it will cost O(n), each value will add up last two value as result, it will cost (1+2), in total will be O(n+2n) and It is O(n)