In this article, you will learn to resolve the Fibonacci numbers problem by using recursive vs dynamic programming algorithms

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

Let walkthrough below to explore in more details

### 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

```
```

- 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

```
```

- 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

```
```

- Output

```
55
```