Learn Dynamic Programming using Fibonacci as an example
Tags: dp, fibonacci, algorithms
Published: 2018-07-20 00:52:17

---
title: Learn Dynamic Programming using Fibonacci as an example
published: true
description: Learn dynamic programming with Fibonacci sequence algorirthms
tags: dp, fibonacci, algorithms
---


To be honest, **Dynamic Programming** (DP) is a topic that is hard for me to wrap my head around. I think one of the reason is that I was not learning it the right way and understand its concept strong enough to build a mental model of how to solve it properly. Often time, either it takes me a very long time to solve a DP problem and forget about it in the next day, or I just can't.

Learning how to learn is important for me to retain as much as possible. And I think that a fibonacci sequence is a great example of learning DP. I will show you 4 different ways to solve it: Recursive, DP using recursive, DP Bottom Up Approach (optimized runtime), DP Bottom Up Approach (optimized space).

## Statement
Find the index value, given a number n in  the Fibonacci sequence
`1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ....`

A Fibonacci is a sequence of number where the current number is the result of the sum of the previous two numbers. For example, fib(5) should return 5.

# Solutions
## 1. using Recursion
```javascript
var fibRecursive = function(n) {
    if (n<=2) return 1;
    return fibRecursive(n-1) + fibRecursive(n-2);
}
```

This implementation is concise and easy to understand.
We just need have base case when `n <=2` and do recursive calls on `n-1` & `n-2`.
The drawback is 1 call becomes 2 calls. 2 calls becomes 4. etc. It is exponential.
Time complexity O(2^n) and space complexity is also O(2^n) for all stack calls.

## 2. DP = recursion + memoziation
In a nutshell, DP is a efficient way in which we can use memoziation to cache visited data to faster retrieval later on.

```javascript
var mem = [];
var fibRecursiveMem = function (n) {
    if (mem[n]) return mem[n];
    if (n<=2) mem[n] = 1;
    else {
        mem[n] = fibRecursiveMem(n-1) + fibRecursiveMem(n-2);
    }
    return mem[n];
}
```
This implementation makes use of `mem` as an array (or hash) to store value of an already computed num. This will greatly reduce the number of call stack and duplicated computation in the call stack.
For example

```
fib(4) = fib(3) + fib(2)
fib(2), fib(3) were already saved into mem, so will fib(4)
```
```
fib(5) = fib(4) + fib(3)
The previously saved fib(3) and fib(4) will be used to avoid duplicated calculation and call stacks
```
Time complexity O(N), Space O(N)

## 3. DP Bottom Up approach (Optimized runtime)
```javascript
var fibBottomUp = (n) => {
    var mem = [];
    for (var i=0; i <=n; i++) {
        if (i == 0) mem[i] = 0;
        else if (i <=2) mem[i] = 1;
        else {
            mem[i] = mem[i-1] + mem[i-2];
        }
    }
    return mem[n];
}
```
We can further optimize the runtime by using a bottom up solution with a `for` or `while` loop. We still use memoization but we no longer have recursive calls.
Time Complexity O(n), space O(n)

## 3. DP Bottom Up approach (Optimized space)
```javascript
var fibBottomUp2 = (n) => {
    var first, second = 0;
    for (var i=1; i <=n; i++) {
        if (i == 1) second = 1
        else {
            var temp = second;
            second = first + second;
            first = temp;    
        }
    }
    return second;
}
```
As you can see, we only need the last two number to calculate the next Fibonacci sequence. With this logic in mind, we can use two variable to store the last two Fibonacci sequence.
Time O(N), Space O(1)


Leave the comments below for more discussions and useful resources.

Further reading:
Source code:
https://github.com/rattanakchea/coding_interview/blob/master/src/fibonacii.js

This blog post include a test case and run time performance
https://medium.com/developers-writing/fibonacci-sequence-algorithm-in-javascript-b253dc7e320e