Toward a Unified Implementation for Dynamic Programming

摘要

The paper presents a unified approach of algorithms derivation and programs generation for dynamic programming (DP) problems based on formal methods and generic types. Using partition-and-recur (PAR), we first derive two formal algorithms from DP problem specifications, and then transform them into generic programs in two steps. By binding generic types to constructed ones and passing anonymous methods to delegates, we can get concrete programs for a variety of DP problems directly. Three typical programs of the DP model are generated for illustration.