an introduction to Dynamic Programming

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:

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:

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:

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.