Dynamic Programming Example in Java with Fibonacci Numbers

In this article, we will learn about dynamic programming algorithms, and use them to resolve the Fibonacci numbers problem

Dynamic programming algorithms resolve a problem by breaking it into subproblems and caching the solutions of overlapping subproblems to reuse them for saving time later

Steps to solve a dynamic programming problem

Break the problem into subproblems and find the optimal substructure. A problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems
Find overlapping subproblems, and use an array or hash table to cache solutions to overlapping subproblems
Use the cached solutions to save the time complexity of the algorithm

Fibonacci numbers problem

Given a number n
Write an algorithm to return the Fibonacci number at n
Fibonacci numbers form a sequence such that each number is the sum of two preceding ones, starting from 0 and 1

Example

Input n=2, expected output 1
Input n=6, expected output 8
Input n=10. Expected output 55

Analysis

Optimal substructure

F₀ = 0, F₁ = 1

F_n = F_n-1 + F_n-2 for n > 1
Overlapping subproblems

Say you'd like to calculate F₃ which can be represented as below

F₃ = F₂ + F₁ = (F₁ + F₀) + F₁

F₁ is calculated more than 1 time so the computed result can be cached to save time

Approach 1: Recursion

Use a recursive algorithm to resolve the problem with no-cache

public class FibonacciRecursion {  
    int fibonacci(int i) {
        if (i < 2) return i;
        return fibonacci(i-1) + fibonacci(i-2);
    }

    public static void main(String[] args) {
        System.out.println(new FibonacciRecursion().fibonacci(10));
    }
}

Output

Approach 2: Memoization/Top-down Dynamic Programming

Using a cache array to store computed results starting from N to 0, so-called top-down

public class FibonacciMemoization {  
    int[] cache;

    FibonacciMemoization(int[] cache){
        this.cache = cache;
    }

    int fibonacci(int n) {
        if (cache[n] == 0) {
            if (n < 2) cache[n] = n;
            else cache[n] = fibonacci(n-1) + fibonacci( n-2);
        }

        return cache[n];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(new FibonacciMemoization(new int[n+1]).fibonacci(n));
    }
}

Output

Approach 3: Tabulation/Bottom-up Dynamic Programming

Using a cache array to store computed results starting from 0 to N, so-called bottom-up

public class FibonacciTabular {  
    int fibonacci(int n) {
        int[] cache = new int[n+1];
        cache[0] = 0;
        cache[1] = 1;

        for (int i = 2; i <= n; i++) {
            cache[i] = cache[i-1] + cache[i-2];
        }

        return cache[n];
    }

    public static void main(String[] args) {
        System.out.println(new FibonacciTabular().fibonacci(10));
    }
}

Output