Fibonacci Numbers (Compute the Nth Fibonacci with Dynamic Programming) | Coding Problems: DSA

Definition

Each state depends on the previous two; keep two rolling values for linear time and constant space.

Fibonacci Numbers pattern – a DP family where each state depends on a fixed number of previous states.
Definition – fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2) for n >= 2.
Naive recursion – O(2^n) time due to exponential recomputation of identical subproblems.
Memoization – O(n) time and O(n) space by caching each result.
Bottom-up rolling – O(n) time and O(1) space by keeping only the last two values.
Overflow – Fibonacci numbers exceed long at n = 93; use BigInteger for exact results.

The National Bank of India models a simple compounding sequence where each month's projected figure is the sum of the two previous months. Instead of recomputing the whole history from scratch for every query, the system remembers just the last two months and rolls forward, computing the answer in one pass.

Understanding the Concepts

What is the Fibonacci Numbers DP pattern?

The Fibonacci Numbers pattern is a family of dynamic programming problems where each state depends on a small, fixed number of previous states. The classic Fibonacci sequence is the simplest example: each number is the sum of the two preceding numbers. But the pattern extends to any problem with a fixed-window recurrence: climbing stairs, house robber, decode ways, and tribonacci.

The defining characteristic is that once you identify the window size (how many previous states are needed), you can compute the answer in linear time with constant space.

JAVA

package com.bank.dsa;

public class FibonacciPattern {

    public static long fib(int n) {
        if (n <= 1) return n;
        long prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; i++) {
            long current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.println("fib(" + i + ") = " + fib(i));
        }
    }
}

TEXT

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55

Why is naive recursion exponentially slow?

The naive recursive implementation calls itself twice at each level, creating a binary call tree. The total number of nodes in this tree is approximately 2^n. Many subproblems are computed multiple times: fib(3) is computed twice when computing fib(5), and fib(2) is computed three times.

JAVA

package com.bank.dsa;

public class FibonacciNaive {

    private static long calls = 0;

    public static long fib(int n) {
        calls++;
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        calls = 0;
        System.out.println("fib(30) = " + fib(30));
        System.out.println("Calls:    " + calls);
    }
}

TEXT

fib(30) = 832040
Calls:    2692537

How does memoization fix the problem?

Memoization stores each computed result in a cache. Before computing fib(n), check the cache. If the value exists, return it immediately. Otherwise compute, store, and return. This ensures each value is computed exactly once.

JAVA

package com.bank.dsa;

import java.util.HashMap;
import java.util.Map;

public class FibonacciMemo {

    private static final Map<Integer, Long> memo = new HashMap<>();

    public static long fib(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        long result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println("fib(50) = " + fib(50));
    }
}

TEXT

fib(50) = 12586269025

How does bottom-up with rolling variables work?

Since each Fibonacci number depends only on the two preceding values, we do not need to store the entire sequence. Two variables are enough. We iterate from 2 to n, computing each value as the sum of the previous two, then slide the window forward.

JAVA

package com.bank.dsa;

public class FibonacciRolling {

    public static long fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        long twoBack = 0;
        long oneBack = 1;
        for (int i = 2; i <= n; i++) {
            long current = oneBack + twoBack;
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }

    public static void main(String[] args) {
        System.out.println("fib(10) = " + fib(10));
        System.out.println("fib(50) = " + fib(50));
        System.out.println("fib(92) = " + fib(92));
    }
}

TEXT

fib(10) = 55
fib(50) = 12586269025
fib(92) = 7540113804746346429

How is this different from memoization?

| Aspect | Bottom-up rolling | Memoization |
|---|---|---|
| Direction | Base cases to target | Target recurses to base cases |
| Space | O(1) with two variables | O(n) for cache + stack |
| Stack risk | None | StackOverflowError for large n |
| Code style | Simple loop | Recursive with cache check |
| Best for | When only final value needed | When state space is sparse |

What about overflow for large n?

Fibonacci numbers grow exponentially. The 92nd Fibonacci number is the last that fits in a Java long. The 93rd overflows silently. For exact results with large n, use BigInteger.

JAVA

package com.bank.dsa;

import java.math.BigInteger;

public class FibonacciBig {

    public static BigInteger fib(int n) {
        if (n == 0) return BigInteger.ZERO;
        if (n == 1) return BigInteger.ONE;
        BigInteger twoBack = BigInteger.ZERO;
        BigInteger oneBack = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            BigInteger current = oneBack.add(twoBack);
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }

    public static void main(String[] args) {
        System.out.println("fib(93)  = " + fib(93));
        System.out.println("fib(200) = " + fib(200));
    }
}

TEXT

fib(93)  = 12200160415121876738
fib(200) = 280571172992510140037611932413038677189525

What problems belong to the Fibonacci Numbers pattern?

The pattern applies whenever the recurrence has a fixed window of previous states:

Climbing Stairs (1 or 2 steps): dp[n] = dp[n-1] + dp[n-2], which is exactly Fibonacci.
Climbing Stairs (1, 2, or 3 steps): dp[n] = dp[n-1] + dp[n-2] + dp[n-3], a three-term window.
House Robber: dp[n] = max(dp[n-1], dp[n-2] + value[n]), a two-term window with a choice.
Decode Ways: dp[n] depends on dp[n-1] and dp[n-2] based on digit validity.

JAVA

package com.bank.dsa;

public class HouseRobber {

    public static int maxLoot(int[] houses) {
        if (houses.length == 0) return 0;
        if (houses.length == 1) return houses[0];
        int twoBack = 0, oneBack = houses[0];
        for (int i = 1; i < houses.length; i++) {
            int current = Math.max(oneBack, twoBack + houses[i]);
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }

    public static void main(String[] args) {
        System.out.println(maxLoot(new int[]{2, 7, 9, 3, 1}));
    }
}

TEXT

What are common mistakes?

The most common mistake is getting the base cases wrong. For Fibonacci, forgetting to handle n = 0 separately (returning 0) or n = 1 (returning 1) leads to incorrect results or infinite recursion.

JAVA

// WRONG: no base case for n = 0
public static long fibWrong(int n) {
    if (n == 1) return 1;
    return fibWrong(n - 1) + fibWrong(n - 2);  // fib(0) recurses to fib(-1) + fib(-2)
}

// CORRECT: both base cases
public static long fibCorrect(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibCorrect(n - 1) + fibCorrect(n - 2);
}

When should you use this pattern in banking?

At the National Bank of India, the analytics team models a reward-points scheme where each month's points equal the sum of the previous two months. Customers query their projected points for future months. The system uses the rolling bottom-up approach to compute the answer in O(n) time with O(1) space, and caches popular results in Redis.

JAVA

package com.bank.service;

import java.math.BigInteger;

public class RewardPointsProjector {

    public static BigInteger projectPoints(int month) {
        if (month < 0) throw new IllegalArgumentException("Month must be non-negative");
        if (month == 0) return BigInteger.ZERO;
        if (month == 1) return BigInteger.ONE;

        BigInteger twoBack = BigInteger.ZERO;
        BigInteger oneBack = BigInteger.ONE;
        for (int i = 2; i <= month; i++) {
            BigInteger current = oneBack.add(twoBack);
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }

    public static void main(String[] args) {
        System.out.println("Month 12 points: " + projectPoints(12));
        System.out.println("Month 50 points: " + projectPoints(50));
    }
}

TEXT

Month 12 points: 144
Month 50 points: 12586269025

What should a senior engineer know?

A senior engineer should know that matrix exponentiation can compute fib(n) in O(log n) time by raising the 2x2 Fibonacci matrix {{1,1},{1,0}} to the nth power using fast exponentiation. This is useful for extremely large n but rarely needed in interviews.

The Fibonacci pattern generalises: any linear recurrence with constant coefficients can be solved in O(k^3 * log n) time using matrix exponentiation, where k is the number of terms in the recurrence.

In production, the practical concern is overflow. Java's long holds up to 9.2 * 10^18, which accommodates fib(92) = 7,540,113,804,746,346,429 but not fib(93). Always use BigInteger when the index can exceed 92.

Visual Overview

DIAGRAM

  Fibonacci Numbers Pattern: Rolling Variables
  ─────────────────────────────────────────────

  Naive Recursion (exponential):
                 fib(5)
                /      \
           fib(4)      fib(3)     ← same subproblems
          /    \       /    \
      fib(3) fib(2) fib(2) fib(1)
       ...    ...    ...

  Bottom-Up Rolling (linear, constant space):
  ┌──────┬──────┬──────────────────┐
  │ Step │ prev │ curr             │
  ├──────┼──────┼──────────────────┤
  │  0   │ 0, 1 │ -                │
  │  2   │ 1, 1 │ 0 + 1 = 1       │
  │  3   │ 1, 2 │ 1 + 1 = 2       │
  │  4   │ 2, 3 │ 1 + 2 = 3       │
  │  5   │ 3, 5 │ 2 + 3 = 5       │
  └──────┴──────┴──────────────────┘
  Only 2 variables at any point → O(1) space

Key Takeaway

The Fibonacci Numbers dynamic programming pattern covers problems where each state depends on a fixed window of previous states. The classic Fibonacci sequence is the simplest example, but the pattern extends to climbing stairs, house robber, decode ways, and any fixed-window recurrence.

Naive recursion creates an exponential call tree because it recomputes the same subproblems. Memoization fixes this by caching each result, reducing the work to O(n) time with O(n) space. The bottom-up rolling approach goes further: since each value depends only on the previous two, keep just two variables and iterate forward for O(n) time and O(1) space.

At the National Bank of India, the analytics team used this pattern for a reward-points projection where each month's target equalled the sum of the previous two months. The rolling computation returned results instantly even for distant future months, and popular results were cached in Redis for repeated queries.

The senior-level addition is that Fibonacci numbers overflow a long at n = 93, so BigInteger is necessary for large indices. Matrix exponentiation computes fib(n) in O(log n) time for extreme cases, but the rolling approach is what you use in practice.

Remember one sentence: each state depends on the previous two, so keep two rolling values for linear time and constant space.

---