Summary

In this chapter, we have analyzed and implemented two archetypal examples of dynamic programming and learned several methods by which different DP problems may be approached. We have also learned how to identify the characteristics of problems that can be solved with DP, how DP algorithms should be considered conceptually, and how the concepts of states, base cases, and recurrence relations can be used to break a complex problem down into much simpler components.

We have just barely scratched the surface of the dynamic programming technique. Indeed, the two problems we explored in depth are actually quite similar, both conceptually and in terms of how their solutions are implemented. However, many of these similarities serve to demonstrate several commonalities that are encountered in nearly every DP problem, and, as such, they serve as an excellent introduction to a topic that is admittedly quite complex and difficult to master.

Using dynamic programming is a skill that you are unlikely...