Understanding Dynamic Programming using Javascript

The dynamic-programming method is a great approach to optimize an algorithm. In this tutorial we’ll review how to think through it and try some examples using Javascript.

What are the benefits?

If you have a (tentative) solution that has overlapping subproblems and exhibits optimal substructure, it may be possible to reduce the time complexity of the algorithm using Dynamic Programming!

Let’s break down those terms:

1. A solution that has overlapping subproblems means that as it’s running, it is actually solving the same problem again and again.
2. A solution that has optimal substructure means that an optimal solution to the problem incorporates optimal solutions to related subproblems.

The Rod Cutting Problem

To better understand points one and two, let’s take the rod cutting problem:

Rod Corp. sells metal rods. We are given a price table that states how much Rod Corp. charges for a rod of length i inches. Management wants to know the most profitable way to cut up the rods. Each cut is free.

length i: 1 2 3

price pᵢ : 2 5 6

Solve the problem by hand

If you have a rod of length 3, you’re best of converting it into two rods: one of length 1 and the other of length 2 as that would yield 7 dollars rather than keeping it uncut and yielding 6 dollars. So how could we create an algorithm to solve this for us?

A first pass could look like the following:

/**
 *
 * @param {number[]} prices
 * @param {number} length
 * @returns {number
 *
 function cutRod(prices, length) {
  if (length <= 0) return 0;
  let max = -Infinity;
  for (let i = 0; i < length; i ++) {
    max = Math.max(max, prices[i] + cutRod(prices, length - i - 1));
  }
  return max;
}

The time complexity of this algorithm is exponential, so don’t feed it anything too big. Looking back at the characteristics of an algorithm that can be optimized with dynamic programming, we soon see it has both attributes.

1. Overlapping subproblems: Even with an array of length 3, we can already see that cutRod() is getting called repeatedly with the same inputs (length 0 gets called four times). There is room to remember, or memoize, the function such that if it sees the same input a second time, it knows the final answer without using computational time needlessly.
2. Optimal substructure: Notice how in our for loop we are always seeking the biggest number possible and then returning that value in the end. Our final result is the product of optimal solutions to related subproblems.

Top-Down and Bottom-Up

There are two approaches to optimizing an algorithm with Dynamic Programming.

1. Top-Down: Start from the largest subproblem just like in our first algorithm, but memoize, or cache in a key-value dictionary, your answers so when you come across a subproblem a second time you can use the memoized answer.
2. Bottom-Up: Start from the smallest subproblem and iteratively increase the size as you tabulate, or cache in a fixed-length array, your answers. As the size increases and you start to need solutions for smaller subproblems, you can find the answers in your generated table.

Top-Down in action

/**
 *
 * @param {number[]} prices
 * @param {number} length
 * @param {object} memo
*/
const cutRodMemoized = (prices, length, memo) => {
  if (typeof memo[length] === "number") return memo[length];
  if (length <= 0) return memo[length] = 0;
  let max = -Infinity;
  for (let i = 0; i < length; i ++) {
    max = Math.max(max, prices[i] + cutRodMemoized(prices, length - i - 1, memo));
  }
  return memo[length] = max;
}
/**
 *
 * @param {number[]} prices
 * @returns {number}
*/
function cutRod(prices) {
  const memo = {};
  const length = prices.length;
  return cutRodMemoized(prices, length, memo);
}

To understand what’s going on here, start with the cutRod function. We have created a memo object that will remember our answers and then we return the result of our new function cutRodMemoized which uses the memo object.

cutRodMemoized is identical to our first attempt at the problem except now the first thing it does is check if memo has a value for a given length value; length being our key for storing answers. When returning a solution, rather than just returning a value, the answer is also stored in the memo.

Bottom-Up in action

/**
 *
 * @param {number[]} prices
 * @returns {number}
*/
function cutRod(prices) {
  const table = Array(prices.length + 1);
  table[0] = 0;
  for (let i = 1; i <= prices.length; i ++) {
    let max = -Infinity;
    for (let j = 0; j < i; j ++) {
      max = Math.max(max, prices[j] + table[i - j - 1]);
    }
    table[i] = max;
  }
  return table[prices.length];
}

The only portion of this solution that carried over from our initial unoptimized solution is the optimal substructure portion:

max = Math.max(max, prices[j] + table[i - j - 1]);

We are otherwise going through all the possible ways we can cut up the rods iteratively and using the table to keep track of past computations starting with the smallest length (0) and increasing in size from there.

Further work

Hope this info was useful! That’s all I have for today. If you’re looking for other problems to practice applying top-down and bottom-up Dynamic Programming to, some known problems include:
1. Solving for the nth fibonacci number

2. Matrix-chain multiplication

Good luck!

Unrelated PSA: Looking for a new high paying software development job? Send me your resume to alexleondeveloper@gmail.com and I’ll get back to you!