Boost logo

Boost :

From: Jim Apple (japple_at_[hidden])
Date: 2003-12-12 21:30:50

Let me try again.

Memoizing a function involves stoing all calls and results in a table.
Dynamic programming involves building a table of results along the way.

A dynamic programming approach to computing fibonacci numbers would look

int fib(int n) {
   vector<int> ans;
   for(unsigned i = 2; i <=n; ++i)
     ans.push_back(ans[i-1] + ans[i-2]);
   return ans[n];

A memoized approach would be

int fib(int n) {
   static std::map<int,int> memo;
   if (memo.find(n) == memo.end()) {
     int result = fib(n-1) + fib(n-2);
     memo[n] = result;
     return result;
   } else {
     return (memo.find(n)->second);

1. As you pointed out, neither one of these is the smart way to do it.
Some of the examples in the last message were more approprite candidates
for memoization or dynamic programming; I can write one or two up in
code, if desired.
2. This is not smart use of std::map. I chose this use for
demonstration purposes only.

David Abrahams wrote:
> Example? I always think of dynamic programming as creating the cache
> implicitly, too.

I think the literature disagrees with you, but I'm not really attached
to any name for the concept. We could call it as-need dynamic
programming to be more clear.

A danger of this library is that it encourages lazy solutions, like
memoizing fibonacci, when merely implementing it with zero static
storage and zero recursive calls is possible.


Boost list run by bdawes at, gregod at, cpdaniel at, john at