LeetCode 509. Fibonacci Number

LeetCode Notes [17]

Problem

Fibonacci Number - LeetCode

Intuition

Optimal Substructure: F(n) = F(n-1) + F(n-2), for n > 1

Solution 1: Dynamic Programming

Complexity Analysis

• Time complexity : O(n).
  The recursive function is run once for each of the n nodes, and the body of the recursive function is O(1). Therefore, this gives a total of O(n).
• Space complexity : O(n).

Solution 2: Three variables

Complexity Analysis

• Time complexity : O(n).
• Space complexity : O(1).