Finding Nth Fibonacci Number using Dynamic Programming (Top Down DP)

Fibonacci is the problem almost everyone uses to learn dynamic programming, and for good reason. The plain recursive solution is short and obviously correct, and also hopelessly slow. Fixing it takes one array, and that fix is exactly what "top-down DP" means.

Problem

Given a number N, print the Nth Fibonacci number. The sequence starts 0, 1 and every later term is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21 ... We count from F(0) = 0, so F(5) = 5 and F(7) = 13.

Input: 5      Output: 5
Input: 7      Output: 13

Why plain recursion is slow

The direct translation of the definition is fib(n) = fib(n-1) + fib(n-2). Draw the calls for fib(5) and you will see fib(3) computed twice, fib(2) three times and fib(1) five times. The number of calls grows roughly like 1.6ⁿ. For n = 50 that is billions of calls, and the program seems to hang.

Top-down DP: remember what you have already worked out

Keep an array memo where memo[i] stores F(i) once we know it, and -1 means "not computed yet". Before doing any work, check the array. If the answer is there, return it. If not, compute it the normal recursive way and store it before returning. Now each value from 0 to n is computed only once, so the time drops from exponential to O(n).

This style, recursion plus a cache, is called memoisation or top-down dynamic programming. You keep the natural recursive structure and just stop it repeating itself.

Solution in Java

import java.util.Arrays;
import java.util.Scanner;

public class Fibonacci {
    // Top-down DP: plain recursion plus a memo array
    static long fib(int n, long[] memo) {
        if (n <= 1) return n;
        if (memo[n] != -1) return memo[n];
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
        return memo[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] memo = new long[n + 1];
        Arrays.fill(memo, -1);
        System.out.println(fib(n, memo));
    }
}

We fixed a few bugs from the earlier version of this code: it filled the array inside the recursive function (which wiped the memo on every call), used an array name that did not exist, and assigned an int[] to a long[]. The version above compiles and has been tested for N = 5, 7, 50 and 92.

Output

Input: 5
Output: 5

Input: 50
Output: 12586269025

Bottom-up version

You can also fill the values in order from the smallest up, with no recursion at all. Since each step only needs the last two numbers, you do not even need the array:

static long fib(int n) {
    if (n <= 1) return n;
    long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

This runs in O(n) time and O(1) extra space, and it cannot overflow the call stack for large n.

Complexity

• Top-down: O(n) time, O(n) space for the memo array plus the recursion stack.
• Bottom-up: O(n) time, O(1) space.

Limits to keep in mind

F(92) = 7,540,113,804,746,346,429 is the largest Fibonacci number that fits in a Java long. F(93) overflows and turns negative. For bigger N, use BigInteger, or, if the question asks for the answer modulo 10⁹+7, take the modulus at every addition.

Once this makes sense, try climbing stairs and coin change, which use the same idea. Our greedy and dynamic programming MCQs are a good check, and the algorithms study guide shows what to learn next.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More algorithms tutorials All coding problems MCQ practice