Fibonacci with Memoization
Fibonacci with Memoization
The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n ≥ 2. Given n, compute and print the nth Fibonacci number using memoization (top-down dynamic programming). Naive recursion is O(2^n) — far too slow. Memoization brings it down to O(n) by caching results of subproblems. Your solve(...) function receives these inputs directly as ready-made arguments — no input reading or parsing needed. Just compute and return the answer. Examples: n=0 → 0, n=1 → 1, n=5 → 5, n=10 → 55
Input format — only if your code reads from stdin
Input format (stdin): - A single integer n Output: a single integer — the nth Fibonacci number.
Approach
Create a memo array of size n+1 initialized to -1. If memo[n] != -1, return it. Otherwise compute F(n) = F(n-1) + F(n-2), store in memo[n], and return. Alternatively, use bottom-up iteration: just track the last two values.
Input
Output
- •
0 ≤ n ≤ 50
More Dynamic Programming problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards