Code Logo

Fibonacci Number

Published at24 Jul 2026
Created by
Easy 1 views
Like0

The Fibonacci sequence is defined as:F(0) = 0, F(1) = 1, and for n > 1, F(n) = F(n-1) + F(n-2). Given n, calculate F(n). This is the simplest example of a dynamic programming recurrence relation, where each value depends on the two previous values.

A recursive solution without memoization has exponential time O(2^n) because it recomputes the same subproblems repeatedly. Dynamic programming stores computed values to avoid redundant work. Using a bottom-up approach, we can compute F(0), F(1), F(2), and so on up to F(n) in O(n) time.

The space can be optimized to O(1) by noting that only the two most recent values are needed at each step. Use two variables to track F(n-1) and F(n-2), updating them iteratively. This eliminates the need for an array of size n.

Edge cases include n = 0 (return 0), n = 1 (return 1), and large n where the result may exceed 32-bit integers. In languages with fixed-width integers, use 64-bit or handle overflow.

The Fibonacci sequence appears throughout computer science and nature, from branching patterns in trees to the golden ratio. Solving it with DP demonstrates the core principles of memoization and tabulation — reusing computed subproblem results to avoid exponential blowup.

Example Input & Output

Example 1
Input
3
Output
2
Explanation

F(3) = F(2)+F(1) = 1+1 = 2.

Example 2
Input
4
Output
3
Explanation

F(4) = F(3)+F(2) = 2+1 = 3.

Example 3
Input
0
Output
0
Explanation

F(0) = 0.

Example 4
Input
2
Output
1
Explanation

F(2) = F(1)+F(0) = 1+0 = 1.

Example 5
Input
5
Output
5
Explanation

F(5) = F(4)+F(3) = 3+2 = 5.

Algorithm Flow

Recommendation Algorithm Flow for Fibonacci Number

Solution Approach

Use recursion with memoization to calculate the nth Fibonacci number. The Fibonacci sequence is defined as fib(0)=0, fib(1)=1, and fib(n)=fib(n-1)+fib(n-2) for n>1. A naive recursive approach recalculates the same values many times, so memoization stores previously computed results in an array to avoid redundant work.

function fib(n) {
  if (n <= 1) return n;
  var memo = [0, 1];
  for (var i = 2; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2];
  }
  return memo[n];
}

This iterative bottom-up approach builds the Fibonacci sequence from the base cases upward, storing each value exactly once. It avoids the exponential time complexity of naive recursion by solving each subproblem in order.

Time complexity is O(n), space complexity is O(n) for the memo array. A further optimization uses O(1) space by keeping only the last two values.

Best Answers

java
class Solution {
    public int solution(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}