# what is Dynamic Programming?

Dynamic programming is a way of making your algorithm more efficient by storing some of the intermediate results. It works well when your algorithms has a lot of repetitive computations.

In Dynamic Programming there are typically three steps you can take:

- Come up with a recursive solution to the problem
- Store or memoize the intermediate results if there are a lot of repeated computations
- Come up with a bottom-up approach

## Recursive solution for fibonacci sequence

If we want to write a function `fib(n)`

to find the nth number of a Fibonacci sequence.

Given the following Fibbonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, ... `fib(3)`

should return 2 and `fib(6)`

should return 8.

A recursive solution to the problem without memoization:

```
function fib(n) {
if (n === 1 || n === 2) return 1;
return fib(n - 1) + fib(n - 2);
}
```

The above solution works, but it is very inefficient.

From the diagram above, it can be seen that in order to calculate the 5th fibonacci number, `fib(5)`

, we need to first compute `fib(4)`

and `fib(3)`

and add them up. In order to compute `fib(4)`

, we then need to compute `fib(3)`

again and `fib(2)`

.

Hence it can be seen that there are a number of repeated computations, where we need to compute the return value for `fib(2)`

three times, and `fib(3)`

two times.

This becomes an issue when the value of `n`

increases (eg. `fib(1000)`

) and the time to calculate the `nth`

Fibonacci grows exponentially, with a time complexity of O(2^n).

With Dynamic programming, we can store (ie. memoize) the return value of say, `fib(3)`

after it is computed, and then use that value when it is needed again.

We can tweak the solution as follows:

Use an array with a length of

`n + 1`

, where the initial values are all set to nullStore the return value for

`fib(n)`

at index`n`

of the array. (ie. 1, which is the return value of`fib(1)`

, will be stored at`array[1]`

)At the beginning of the function, check whether the

`array[n]`

is`null`

or not. If it is not`null`

, it means that we have already stored the return value at index n, so we can just return`array[n]`

. If it is not null, then we need to find the sum of the previous two Fibonacci numbers. and then store that result in`array[n]`

Rewriting the solution using memoization:

```
function fibWithMemoization(n) {
const memo = new Array(n + 1).fill(null);
function fib(n) {
if (memo[n] !== null) {
return memo[n];
}
if (n <= 2) {
return 1;
} else {
result = fib(n - 1) + fib(n - 2);
memo[n] = result;
return result;
}
}
return fib(n);
}
```

This reduces the time complexity to O(n), however there is also a space complexity of O(n)

Also, as `n`

increases, there is a possibility of a recursion error, which happens when there are too many calls on a call stack. To fix that, a bottom-up approach can be used.

## Bottom-up approach

In the bottom-up approach, we start from the smallest sub-problem and work our way up. In this case, we iterate up to `n`

and store the earlier results in a table/ array.

```
function fib(n) {
if (n === 1 || n === 2) return 1;
arr[1] = 1;
arr[2] = 1;
for (let i = 3; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
```

With the bottom-up approach, the time complexity is O(n) and space complexity is constant.

## Discussion