  Dynamic programming (DP) is an algorithmic design paradigm for the efficient,
exact solution of otherwise intractable, combinatorial problems. However, DP
algorithm design is often presented in an ad-hoc manner. It is sometimes
difficult to justify algorithm correctness. To address this issue, this paper
presents a rigorous algebraic formalism for systematically deriving DP
algorithms, based on semiring polymorphism. We start with a specification,
construct an algorithm to compute the required solution which is self-evidently
correct because it exhaustively generates and evaluates all possible solutions
meeting the specification. We then derive, through the use of shortcut fusion,
an implementation of this algorithm which is both efficient and correct. We
also demonstrate how, with the use of semiring lifting, the specification can
be augmented with combinatorial constraints, showing how these constraints can
be fused with the algorithm. We furthermore demonstrate how existing DP
algorithms for a given combinatorial problem can be abstracted from their
original context and re-purposed.
  This approach can be applied to the full scope of combinatorial problems
expressible in terms of semirings. This includes, for example: optimal
probability and Viterbi decoding, probabilistic marginalization, logical
inference, fuzzy sets, differentiable softmax, relational and provenance
queries. The approach, building on ideas from the existing literature on
constructive algorithmics, exploits generic properties of polymorphic
functions, tupling and formal sums and algebraic simplifications arising from
constraint algebras. We demonstrate the effectiveness of this formalism for
some example applications arising in signal processing, bioinformatics and
reliability engineering. Python software implementing these algorithms can be
downloaded from: http://www.maxlittle.net/software/dppolyalg.zip.
