LeetCode 509. Fibonacci Number

LeetCode Notes [17]

John Lu
Nov 21, 2022

Problem

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

--

--

John Lu

AI Engineer. Deeply motivated by challenges and tends to be excited by breaking conventional ways of thinking and doing. He builds fun and creative apps.