Fibonacci Number
ID: 509; easy
Solution 1
This the bottom-up tabulation approach. We start from the very "bottom" and add up the numbers until n
.
Time complexity: O(n)
Space complexity: O(n)
Solution 2
This is the top-down memoization approach. We use a hash table to achieve memoization.
Time complexity: O(n)
Space complexity: O(n)
Solution 3
This is the bottom-up approach without using an array to keep the results. Instead, we only use three variables to keep the progress.
Time complexity: O(n)
Space complexity: O(1)
Last updated