Code Logo

Fibonacci Number

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Fibonacci Number

Solution Approach

Bottom-up DP with two variables: start with a=F(0), b=F(1). For each step, compute c=a+b, shift a=b, b=c.

function solution(n) {
  if (n <= 1) return n;
  var a = 0, b = 1;
  for (var i = 2; i <= n; i++) {
    var c = a + b;
    a = b;
    b = c;
  }
  return b;
}

Time O(n), Space O(1).

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;
    }
}