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

    F0 = 0, F1 = 1

    Fn = Fn-1 + Fn-2 for n > 1

  • Overlapping subproblems

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

    F3 = F2 + F1 = (F1 + F0) + F1

    F1 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
55

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
55

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
55

Other dynamic progamming problems