Towards a discipline of dynamic programming

frobertcmeyerpsteffengtechfakunibielefeldde Abstract Dynamic programming is a classic programming technique applicable in a wide variety of domains like stochastic systems analysis operations research combinatorics of discrete structures ow problems parsing ambiguous languages or biosequence analysis Yet heretofore no methodology was available guiding the design of such algorithms The matrix recurrences that typically describe a dynamic programming algorithm are dicult to construct error prone to implement and almost impossible to debug This article introduces an algebraic style of dynamic programming over sequence data We de ne its formal framework including a formalization of Bellmans principle We suggest a language for algorithm design on a convenient level of abstraction We outline three ways of implementation including an embedding in a lazy functional language The workings of the new method are illustrated by a series of examples from diverse areas of computer science The power and scope of dynamic programming Dynamic programming a world without rules Dynamic programming DP is one of the classic programming paradigms in troduced even before the term Computer Science was rmly established When applicable DP often allows to solve combinatorial optimization problems over a search space of exponential size in polynomial space and time Bellmans Prin ciple of Optimality Bel belongs to the core knowledge we expect from ever