Introduction To Dynamic Programming in JavaScript

Learn how to use dynamic programming to solve complex recursive problems.

Dynamic Programming is a programming technique used to solve recursive problems more efficiently. Let’s take a look at a simple algorithm that can get computationally complex very quickly, and then let’s use dynamic programming to increase its efficiency.

Fibonacci

The Fibonacci series is a classic mathematical series in which the next number is calculated as the sum of the previous two numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, etc.

It can be calculated iteratively but summing the two previous numbers, or the nth Fibonacci number can be calculated recursively:

function fib(n)
  if n is 1 or 0:
    return n
  else
    return fib(n - 1) + fib(n - 2)

This technique breaks up calculating the nth number into many smaller problems, calculating each step as the sum of calculating the previous two numbers.

Although this technique will certainly work to find the correct number, as n grows, the number of recursive calls grows very quickly. Let’s visualize all the function calls if we were to calculate the fourth Fibonacci number:

fib(4) -> fib(3) + fib(2)
  fib(3) -> fib(2) + fib(1)
    fib(2) -> fib(1) + fib(0)
  fib(2) -> fib(1) + fib(0)

As you can seefib(2) is called twice, fib(1) is called three times. If n were larger than 4, you’d see these numbers of calls get high very quickly. For instance, to calculate the 10th number, we’d make 34 calls to fib(2) and 177 total function calls! Why do we need to call the same function multiple times with the same input?

We don’t! We can use a technique called memoization to cut down greatly on the number of function calls necessary to calculate the correct number.

Memoization

Memoization is a specialized form of caching used to store the result of a function call. The next time that function is called, instead of running the function itself, the result is used directly. Memoization can result in much faster overall execution times (although it can increase memory requirements as function results are stored in memory).

Memoization is a great technique to use alongside recursion. The memo can even be saved between function calls if it’s being used for common calculations in a program.

Memoizing Fibonacci

In the previous example, many function calls to fib() were redundant. Let’s memoize it in order to speed up execution.

To begin, we’ll use a plain JavaScript object to store the memoized values. We’ll set keys using n and values to store the result of that Fibonacci number. Then, whenever we need to calculate a number, if it’s already been calculated, we can retrieve the value from the object in O(1) time.

const memo = {};

In pseudocode, our approach to memoization will look something like this:

Create a memo object

function fibonacci(n)
  if n key exists in memo object
    return memo[n]
  else
    calculate current fibonacci number
    store value in memo
    return value

Let’s implement it in JavaScript!