R. Giegerich and C. Meyer:

Algebraic Dynamic Programming.

In Hélène Kirchner and Christophe Ringeissen, editors, Algebraic Methodology And Software Technology, 9th International Conference, AMAST 2002, pages 349--364, Saint-Gilles-les-Bains, Reunion Island, France, 2002. Springer LNCS 2422.
Dynamic programming is a classic programming technique, applicable in a wide variety of domains, like stochastic systems analysis, operations research, combinatorics of discrete structures, flow problems, parsing with ambiguous grammars, or biosequence analysis. Yet, no methodology is available for designing such algorithms. The matrix recurrences that typically describe a dynamic programming algorithm are difficult to construct, error-prone to implement, and almost impossible to debug.

This article introduces an algebraic style of dynamic programming over sequence data. We define the formal framework including a formalization of Bellman's principle, specify an executable specification language, and show how algorithm design decisions and tuning for efficiency can be described on a convenient level of abstraction.