
Boost : 
From: Jim Apple (japple_at_[hidden])
Date: 20031212 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
like:
int fib(int n) {
vector<int> ans;
ans.push_back(1);
ans.push_back(1);
for(unsigned i = 2; i <=n; ++i)
ans.push_back(ans[i1] + ans[i2]);
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(n1) + fib(n2);
memo[n] = result;
return result;
} else {
return (memo.find(n)>second);
}
}
Notes:
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 asneed 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.
Jim
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk