Dynamic Programming via Static Incrementalization
Abstract:
Dynamic programming is an important algorithm design technique. It is
used for solving problems whose solutions involve recursively solving
subproblems that share subsubproblems. While a straightforward recursive
program solves common subsubproblems repeatedly and often takes
exponential time, a dynamic programming algorithm solves every
subsubproblem just once, saves the result, reuses it when the
subsubproblem is encountered again, and takes polynomial time. This paper
describes a systematic method for transforming programs written as
straightforward recursions into programs that use dynamic programming.
The method extends the original program to cache all possibly computed
values, incrementalizes the extended program with respect to an input
increment to use and maintain all cached results, prunes out cached
results that are not used in the incremental computation, and uses the
resulting incremental program to form an optimized new program.
Incrementalization statically exploits semantics of both control
structures and data structures and maintains as invariants equalities
characterizing cached results. The principle underlying
incrementalization is general for achieving drastic program speedups.
Compared with previous methods that perform memoization or tabulation, the
method based on incrementalization is more powerful and systematic. It
has been implemented and applied to numerous problems and succeeded on all
of them.
Scott Stoller's Home Page