Programming Algorithms in Lisp: Writing Efficient Programs with Examples in ANSI Common Lisp

© Vsevolod Domkin 2021

V. DomkinProgramming Algorithms in Lisphttps://doi.org/10.1007/978-1-4842-6428-7_12

12. Dynamic Programming

Vsevolod Domkin¹  

(1)

Kyiv, Ukraine

 

This chapter opens the final part of the book. In it, we’re going to apply the knowledge from the previous chapters in analyzing a selection of important problems that are mostly application-independent and find usages in many applied domains: optimization, synchronization, compression, and similar.

We will start with a single approach that is arguably the most powerful algorithmic technique in use. If we managed to reduce the problem to dynamic programming (DP), in most of the cases, ...