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.
Answers to the previous Daily Problem
Suppose you are given three strings of characters:
|X| = n,
|Y| = m, and
|Z| = n + m.
Zis said to be a shuffle of
Zcan be formed by interleaving the characters from
Yin a way that maintains the left-to-right ordering of the characters from each string. (a) Show that
cchocohilaptesis a shuffle of
chocochilatspeis not. (b) Give an efficient dynamic-programming algorithm that determines whether
Zis a shuffle of
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.