Dynamic Programming in JavaScript Part 2 - Examples

p 291-300

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. If you missed the previous article, check that out first.

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.


Get the FREE UI crash course

Sign up for our newsletter and receive a free UI crash course to help you build beautiful applications without needing a design background. Just enter your email below and you'll get a download link instantly.

A new version of this app is available. Click here to update.