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}= 0, F_{1}= 1F

_{n}= F_{n-1}+ F_{n-2}for n > 1Overlapping subproblems

Say you'd like to calculate F

_{3}which can be represented as belowF

_{3}= F_{2}+ F_{1}= (F_{1}+ F_{0}) + F_{1}F

_{1}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
```