LeetCode 509. Fibonacci Number
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).