More 1D DP Problems

(Easy) 509. Fibonacci Number, NeetCode Basic

https://leetcode.com/problems/fibonacci-number/

The Fibonacci sequence is a set of numbers that starts with 0 and 1, each subsequent number is the sum of the two preceding numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …).

Fib(n) = Fib(n-1) + Fib(n-2)

Base Case

• Fib(0) = 0
• Fib(1) = 1

Fibonacci Decision Tree

Top down approaches see it as a conceptual Binary Tree.

• Fibonacci breaks down subproblems unevenly, the tree is unbalanced, because F(n-1) has more recursive calls than F(n-2).
• Because the recursion of F(n-1), F(n) has n levels.
• The number of nodes doubles at each level, growing exponentially, resulting 2^n nodes. It is a Geometric Series (1 + 2 + 4 + 8 + ... + 2^n).
• F(n) means the number of F(1) in its tree, because F(1) is the base cause allowing us adding the result.

                  F(5)
               /        \\
          F(4)             F(3)
         /    \\           /    \\
      F(3)   F(2)       F(2)   F(1)
      / \\     / \\       / \\
  F(2) F(1) F(1) F(0) F(1) F(0)
   / \\
F(1) F(0)

DFS (Return-Value)

Recursion

• Time Complexity O(2^n)
• Space Complexity O(n)