an introduction to Dynamic Programming
Tags: javascript, beginners
Published: 2020-07-02 16:22:25

---
title: an introduction to Dynamic Programming
published: true
description: 
tags: javascript, beginners
//cover_image: https://direct_url_to_image.jpg
---

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

1. Come up with a recursive solution to the problem
2. Store or memoize the intermediate results if there are a lot of repeated computations
3. 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:

```javascript
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.

![](https://ycpcs.github.io/cs201-fall2017/lectures/figures/fib5.png)

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:

1. Use an array with a length of `n + 1` , where the initial values are all set to null

2. Store 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]`)

3. 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:

```javascript
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.

```javascript
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.