Dynamic Programming in JavaScript Part 2 - Examples

Last time we covered the basics of Dynamic Programming. I highly recommend you check out that article first before you check this one out otherwise you might be a bit lost. Today we will be continuing this discussion by revealing a few more examples of Dynamic Programming problems and how to solve them.

This article is part of the Data Structures and Algorithms Series following the course The Analysis of Algorithms. If you missed the previous article, check that out first as well as a copy of The Algorithm Design Manual.

Answers to the previous Daily Problem

Suppose you are given three strings of characters: X, Y , and Z, where |X| = n, |Y| = m, and |Z| = n + m. Z is said to be a shuffle of X and Y iff Z can be formed by interleaving the characters from X and Y in a way that maintains the left-to-right ordering of the characters from each string. (a) Show that cchocohilaptes is a shuffle of chocolate and chips, but chocochilatspe is not. (b) Give an efficient dynamic-programming algorithm that determines whether Z is a shuffle of X and Y . Hint: the values of the dynamic programming matrix you construct should be Boolean, not numeric.

The way I’m approaching this is thinking about how my brain would solve it before finding the recurrence relation. So to answer A:

Two passes over the string array Z. First pass you are picking off letters from X until X is empty (i.e. so find c, now X is hocolate). If X is empty (meaning all letters were found in order), start over and run through Z again with the same heuristic but look for Y instead. If both X and Y are empty, you have found the shuffle. This will run in O(Z) time since you pass over Z twice. You won’t find this shuffle with chocochilatspe because when chips is down to ps it will find p and then s will be left and the two variables X and Y will not be empty.

Answering B is, of course, the real exercise Skiena is looking for us to undergo. Remember, determining a dynamic programming problem involves 3 steps:

1. Create a recurrence relation or recursive algorithm to describe the problem.
2. The parameters for your relation should be polynomial (i.e. recursion can take expontential time, if the number of solutions is less than exponential, that’s polynomial or less possible solutions and thus cheap enough to pursue)
3. Organize your alogrithm so that you can leverage your cached partial results when you need them to save time in exchange for space.

So answer A is not recursive…or is it? I now realize that the “picking off” of the variables can be done recursively by simply providing the function X, Y, and Z with the first letters chopped off. It might make more sense if I just write down the recursive algorithm now:

const weave = (str, z, newIdx = 0) => {
  if (!str.length) return z;
  for (let i = newIdx; i < z.length; i++) {
    if (str[0] === z[i]) {
      // storing the partial results into the arguments of the recursive function = DP!
      return weave(str.slice(1), z.slice(undefined,i).concat(z.slice(i+1)), newIdx);
    } else {
      newIdx++;
    }
  }
  return false;
};

const isShuffle = (x, y, z) => {
  return y === weave(x, z);
};

Before I explain the algorithm, the fact that I created a recursive solution with a defined number of arguments proves parts 1 and 2 of the dynamic programming requirements, so the real trick is to explain part 3.

The first trick I realized in writing this is that when you pick off all of the letters in X, if you have a shuffle, all that is left is Y, so we only ever need to “weave” in letters from X into Z! That means if the first word is picked off of the joint word, you can just compare the two strings for equality.

Now for the recursion. To recurse, we store the smaller versions of X and Z in the arguments of the function. To maintain order, we have to always check the first letter of X or else we don’t maintain the rules of the shuffle. The annoying part comes with the larger word.

To store the partial results, this came down to removing the matched letter from the larger Z string and ensuring when we start our for loop again within our recursed weave that we move along where we left off. This ensures that we only actually have to run this algorithm in O(Z) in one pass rather than 2 in answer A. In fact, if your X is solved before Z is empty, you already have Y so in the best case scenario Z is just X.concat(Y) in order. Therefore, you can actually solve this in the best-case sublinear time of Ω(Z-Y).

Having fun yet? Let’s keep exploring with more examples!

Example 1: binomial coefficients

Everyone uses Fibonacci to talk about Dynamic Programming. The problem is if you only ever hear Fibonacci, your brain will train itself to remember the answer to calculating Fibonacci, and not necessarily how to apply Dynamic Programming.

Let’s take another example from the book: binomial coefficients. This is just another way of saying:

How many different ways can I count something?

So if I have the numbers 1,2,3,4 and I want to pick 2 numbers from them, how many pairs will that generate? The answer is 6, because I can grab (1,2), (1,3), (1,4), (2,3), (2,4), and (3,4).

A technique for quickly generating these coefficients is Pascal’s triangle which you can read on your own for fun. Suffice it to say, it looks an awful lot like how you would generate a Fibonacci sequence. In this case, it’s the sum of two numbers directly above it in the triangle.

We can map this idea out as a function for our binomial coefficient pretty quickly in code. Remember that for Fibonacci we iterated on our code three times: once with recursion, once with recursion and memoization, and finally a third with in-place memoization over a loop. To illustrate that we don’t need recursion to make Dynamic Programming work, let’s see binomial coefficients mapped out as a loop:

const binomialCoefficient = (n, k) => {
  const bc = [[]];
  // fill along the edges of the triangle
  for (let i = 0; i < n; i++) bc[i][0] = 1;
  for (let j = 0; j < n; j++) bc[j][j] = 1;
  // fill in the middle
  for (let i = 1; i < n; i++)
    for (let j = 1; j < i; j++)
      bc[i][j] = bc[i - 1][j - 1] + bc[i - 1][j];

  return bc[n][k];
}

You’ll see that the bigger for loop is just the definition of the recurrence relation for binomial coefficients.

You can see there’s a pretty similar pattern here to the last Fibonacci algorithm we drew up. First, we fill in the default values and edge cases. Next, we iterate through our numbers to precompute values in an array. Finally, we draw values from that array to grab our coefficient value.

The only real difference is that we have to supply two values now instead of one and the math of computation is slightly varied given that the recurrence relation isn’t exactly the same as that of Fibonacci.

So these two examples are pretty similar. For my last trick, let’s go in a completely different direction to really cement this idea.

Example 2: Checking for spelling errors

Did you know that you can create a spellchecker with Dynamic Programming? Yeah, you can! It’s the same formula: try recursion, then memoize, then optimize. So what happens when you spell something? You’re dealing with 4 scenarios for the spellchecker to validate:

1. It matched. Each letter of soil is evaluated and compared to be correct.
2. It swapped. For soel, you have to swap the e for an i when you get there.
3. It added. For sol, you have to add in the i when you get to l too early.
4. It removed. For soile, you have to remove the e when you expected the string to end.

And all but the first scenario carries a cost since the correct string requires no changes but each of the other three requires a change.

To map this out, we have a function that takes our correct word (from something like a dictionary) and compares it to the word we typed out. To do this we’re going to create a matrix of all possibilities from how to get from a letter in our target word to a letter in our compared word. I’ll write it all out now then we can explain it a bit more afterwards:

const compareWords = (targetWord, comparedWord) => {
  const costs = [0,0,0]; // each slot is associated with a MATCH, INSERT, or DELETE cost
  const INSERT_COST = 0;
  const DELETE_COST = 0;
  const matrix;
  let i, j, k; // counters

  // initialize the matrix 2D array
  // our first row
  for (i = 0; i < targetWord.length; i++) {
    matrix[0][i].cost = 0;
    if (i > 0) {
      matrix[0][i].parent = 'I'; // for insert cost
    } else {
      matrix[i][0].parent =  -1; // no parent since we're in the top corner
    }
  }
  // our first column
  for (j = 0; j < compareWord.length; j++) {
    matrix[j][0].cost = 0;
    if (j > 0) {
      matrix[j][0].parent = 'D'; // for deletion cost
    } else {
      matrix[j][0].parent = -1;
    }
  }

  // determine costs
  for (i = 1; i < targetWord.length; i++) {
    for (j = 1; j < compareWord.length; j++) {
      // match cost
      costs[0] = matrix[i-1][j-1].cost + (compareWord[i] === targetWord[j] ? 0 : 1);
      // insert cost
      costs[1] = matrix[i][j-1].cost + 1; // always costs 1 to insert a letter into our target word
      // delete cost
      costs[2] = matrix[i-1][j].cost + 1; // always costs 1 to delete a letter from our target word

      // assume match cost is cheapest at first
      matrix[i][j].cost = costs[0];
      matrix[i][j].parent = 'M'; // for an exact match being made
      for (k = 0; k < 3; k++) {
        if (costs[k] < matrix[i][j].cost) {
          matrix[i][j].cost = costs[k];
          matrix[i][j].parent = k === 0 ? 'M' : k === 1 ? 'I' : 'D';
        }
      }
    }
  }

  // find the final cost at the end of both words
  return matrix[targetWord.length-1][compareWord.length-1].cost;
}

So what is this really doing? There’s really 4 parts to this solution:

1. Matrix initialization

We know that the edges along the rows and columns have a fixed cost at the extremes. When you compare a word to nothing, the cost scales linearly by letter as you add one more. And we know that a blank word carries no cost.

2. Cost calculation

Next, we compare the current position in the matrix to some previous adjacent cell. That leaves us with 3 calculations to compute:

1. Moving up and to the left. We assume we matched the previous cell (i.e. if we matched, both characters can advance) so all that is left to calculate is if the cell matches or not. It costs 0 for an exact match and 1 if we have to substitute one letter for the other.
2. Moving up. Our target character had to advance once without advancing our comparison word. In other words, we had to insert a character which carries a cost of 1 no matter what.
3. Moving left. Converseley, if our target character cannot advance but our comparison word did, we would need to delete a character to reduce matching costs which, again, has a price of 1 no matter what.

3. Optimize our path forward

Now that our costs are calculated in comparison to previous adjacent cells, we can find the minimum cost thus far. We just iterate through all of the cost enumerations and pick the cheapest one of the three. From here we can begin moving onto the next cell in the matrix.

4. Determine the total cost

Once we’ve enumerated through every cell in the cost matrix, we simply find the final cost at the very bottom of our matrix, which has compared every letter in our targetWord with every letter in our compareWord. That final cost is the cheapest cost to navigate from the target word to our comparison word.

String comparisons solve a few problems

The beauty of this solution is that it can really work in a variety of other problems:

Substring matching

Need to spellcheck just a word within a whole text? Initializing the first row removes the conditional to assign an insertion cost since we’re not trying to build one string into the other. Then in step 4, rather than count the cost of the letter in the big text, we just find the cost at the last point in our substring rather than the whole text.

Longest Common Subsequence (LCS)

This is one of those classic problems in Dynamic Programming: you want to find all of the shared characters between two words if you only advance character-by-character. The example in the book uses democrat and republican with a LCS of eca (i.e. e is followed by a c is followed by an a in each of the two words, and it’s of length 3 which is longer than any single letter in both words and is longer than, say, ra which is also a subsequence in the two words).

Leveraging our existing code, if we just make the cost of a substitution in our match calculation 2 instead of 1, the cost is disproprotionately greater than any other cost and we’d never want to swap out letters.

Why is this the solution? Think about it this way: all we ever want are matches. We want all of the other letters out of our way, which either means insertion or deletion just to get the exact sequence of something like LETTER-e-LETTER-LETTER-c-LETTER-LETTER-a. The least number of insertions/deletions to form an equal patter between our target and comparison words gets us our common subsequence.

Example 3: Partitions

Imagine you have a bunch of books in a library. The head librarian has already given you all of the books organized by number of pages in the book. He then gives you a few book dividers to segment the books into sections, ideally as uniformly as possible. How would you do it?

A naive approach

Let’s say the example is super basic: 2 dividers (3 sections) with 9 books: 100 pages, 200 pages…all the way up to 900 pages. The naive way to handle this is to divide the sum of all pages of all books by the number of sections and add in your divider when your ideal division is exceeded by the next book.

So with our example we have 4,500 total pages over 9 books to divide in 3 sections, which makes each section ideally 1,500 pages. The first section creeps over 1,500 pages after book 5, so we put a divider there and it helps that we hit exactly 1,500 pages in this section. The next section creeps over after book 7, so we put the next divider there but we only have 1,300 pages in this section. We’ve used up all dividers, so we’re left with our last section having books 8 and 9, which has a division of 1,700 pages.

This works because while 1,500 is the ideal, the last two sections have a delta of only 200 pages in either direction, so no section is worse than the other and there’s no other possible configuration that would further minimize the cost from the maximum distance of the ideal.

Of course, this is a pretty ideal example and we haven’t applied any dynamic programming principles to achieve this result, which means we know there is more on how to approach this. Can we leverage any of this previous knowledge to improve our algorithm?

Using dynamic programming

The truth is we need an exhaustive search involving recursion to solve this problem. Describing this problem with recusion and storing partial results along the way gives us our dynamic programming solution. How will we manage this?

Remember that to solve the full problem, we should be able to describe a subset of the problem. In other words, if we solved the above example with only 8 books, that should give us information to help solve the total solution with 9 books. And in the other direction, that should should be based on a solution when we only have the first 7 books. What is the cost of adding this last divider?

Maximum sectional cost

That cost is the sum of the remaining elements. The cost we would choose is the maximum of either this current section or the largest section thus far. Why? Either we are breaking new ground and we’ve forced an increase in our total worst cost per section, or we have remained within the cost cap we have defined in all previous sections. This is like if our last book in our example is 1,000 pages instead of 900 - the cost is 1,800 pages which is 300 pages from our ideal instead of the previous delta which is 200 pages (i.e. 600 + 700 = 1,300 which is 200 pages off of the first section at the ideal 1,500 pages).

Minimum sectional distance

Now we mentioned in the previous example that while we’re totalling some maximum, we want to minimize that delta from the ideal, so how do we minimize the total cost per section? Since we have k sections (and k-1 dividers), we need to minimize the cost with the remainder of books if we have k-1 sections (or k-2 dividers). Which is to say, we need to know if the previous remainder was trending in the right direction to set us up for a reasonable maximum with our current last divider available. And because we are trying to solve this as a subset of the previous problem, this is our recurrence relation.

We’ve got enough words here and not enough code, so let’s try and write out what we have above:

const printBooks = (books, start, end) => {
  books.forEach(book => console.log(book));
  console.log('\n');
};

const reconstructPartition = (books, dividers, length, divisions) => {
  if (divisions === 1) return printBooks(books, 1, length);
  reconstructPartition(books, dividers, dividers[length][divisions], divisions-1);
  return printBooks(books, dividers[length][divisions]+1, length);
};

const partitionize = (books, divisions) => {
  let length = books.length;
  let allSums = [0];
  let cachedValues, dividers, cost;

  // collect the cumulative sums
  for (let i = 1; i <= length; i++) allSums[i] = allSums[i-1] + books[i];

  // boundary condition - one division is just the total sum
  for (let i = 1; i <= length; i++) cachedValues[i][1] = allSums[i];

  // boundary condition - one value across all sums is just one section
  for (let j = 1; j <= divisions; j++) cachedValues[1][j] = books[j];

  // store partial values as we walk the recurrence relation
  for (let i = 2; i <= length; i++) {
    for (let j = 2; j <= divisions; j++) {
      cachedValues[i][j] = Number.POSITIVE_INFINITY; // can't get worse than the max cost
      for (let x = 1; x <= i-1; x++) {
        cost = Math.max(cachedValues[x][j-1], allSums[i]-allSums[x]);

        if (cachedValues[i][j] > cost) {
          cachedValues[i][j] = cost;
          dividers[i][j] = x;
        }
      }
    }
  }

  return reconstructPartition(books, dividers, length, divisions);
};

The code here should be self-explanatory: it is meant to work out the algorithm above. The real key is iterating through all of the books and all of the divisions to get the minimum cost after finding the maximum between the previously cached value and the current sum into the partition. If we hit that, increment our dividing line and store the next cached value.

Study it a few times and if you have any questions feel free to hit me up on Twitter. We’ve covered a few examples here and there’s a bunch to unpack so if you need to read over these a few times that’s okay!

Onto the next Daily Problem

A certain string processing language allows the programmer to break a string into two pieces. It costs n units of time to break a string of n characters into two pieces, since this involves copying the old string. A programmer wants to break a string into many pieces, and the order in which the breaks are made can affect the total amount of time used. For example, suppose we wish to break a 20-character string after characters 3, 8, and 10. If the breaks are made in left-right order, then the first break costs 20 units of time, the second break costs 17 units of time, and the third break costs 12 units of time, for a total of 49 steps. If the breaks are made in right-left order, the first break costs 20 units of time, the second break costs 10 units of time, and the third break costs 8 units of time, for a total of only 38 steps. Give a dynamic programming algorithm that takes a list of character positions after which to break and determines the cheapest break cost in O(n^3) time.

More problems to practice on

For even more dynamic programming practice problems, check out Problem 8-14 in the book.