# 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;
cache = 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``