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;
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
``````