Formal Derivation of Dynamic Programming Algorithms
Leila Mofarah-Fathi, Theodore S. Norvell · 2007
Abstract—Dynamic programming is a recursive approach to solving optimization problems. It works by finding solutions to subproblems and combining those solutions. By storing solutions to solved problems, dynamic programming can be particularly efficient. In this paper we will discuss an approach to solving optimization problems based on specialization of an abstract dynamic programming algorithm. This provides not only reuse of the algorithm, but also reuse of its proof. Application of dynamic programming includes Matrix chain multiplication and Largest black square. Index Terms—formal methods, dynamic programming, divide and conquer, predicative style I.