[boost] Re: memoization and dynamic programming

From: Dave Gomboc (dave_at_[hidden])
Date: 2003-12-15 07:04:01

>        dynamic programming (algorithmic technique)
> 
>        Definition: An algorithmic technique in which an optimization
>        problem is solved by caching subproblem solutions (memoization)
>        rather than recomputing them.
> 
> seems to contradict Mr. Apple's definition.

Yes, hmmm.  Well, I'll try to do better:

When an optimisation problem exhibits both "overlapping subproblems" and
"optimal substructure", it is amenable to solution via Dynamic
Programming (DP) techniques.  Subproblems are solved at most once, and
their solutions are stored for later lookup (this would be pointless
without overlapping subproblems).  Solutions to subproblems are combined
to solve larger subproblems (which is not possible without optimal
substructure).

The distinction between conventional DP and memoization is that with the
former, subproblems are solved in advance of any attempted use of their
solution to solve a larger subproblem.  In contrast, memoization
attempts to compute the final problem solution directly, computing
subproblems on demand as their solutions are required.

Generally, conventional DP is preferred when all subproblems must be
solved to solve the original problem, while memoization is for choice
when it is possible to avoid solving some subproblems.  Whether
avoidance is possible or not depends upon the optimal substructure
inherent in the problem.

(I think this is in agreement with what Mr. Apple wrote earlier.)

Dave