A Comprehensive Model of Dynamic Programming
Paul Helman, Arnon S. Rosenthal · SIAM Journal on Algebraic and Discrete Methods · 1985
We present a new model of problems solvable by discrete dynamic programming. The formalism of the model is based on “nonassociative regular expressions” and a generalized notion of comparability. We formally define dynamic programming in this setting, and study its efficiency. We obtain theorems showing dynamic programming to be optimally efficient for a general class of problems. Our model generalizes previous work in that it naturally includes problems of a nonassociative and nonsequential nature (e.g., “parenthesization problems” and nonserial dynamic programming.). A key aspect of the model is that it separates a problem’s structure from the required computation. This serves to make similarities between problems more apparent.