Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Fibonacci Number

Dynamic Programmingeasy

Implement `fib(n)` returning the n-th Fibonacci number where `fib(0) = 0` and `fib(1) = 1`.

Sample tests

Input: fib(10)
Output: 55
Input: fib(0)
Output: 0

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Naive recursion recomputes subproblems exponentially.

Learning resources

  • Wikipedia: Dynamic programming
Approach & explanation (try first)

Bottom-up iteration with two rolling values is O(n) time, O(1) space.

Loading...
⌘/Ctrl + Enter

Run your code to see results.