HelloKoding

Practical coding guides

Dynamic Programming Examples in Java

In this article, you will learn about Dynamic programming algorithm and how to use it to resolve the Fibonacci numbers problem

Dynamic programming is an algorithm for solving a problem by breaking it down into subproblems of the same type with smaller input and storing the computed results of overlapping subproblems into a cache memory to reuse them and save 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
  • Use an array or hash table to cache solutions to overlapping subproblems. There are two ways to fill the cache: top-down and bottom-up

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

FibonacciRecursion.java

package com.hellokoding.algorithm;

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

FibonacciMemoization.java

package com.hellokoding.algorithm;

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

FibonacciTabular.java

package com.hellokoding.algorithm;

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
Follow HelloKoding