From: Niklas Frykholm <r2d2@...>
Date: 2002-02-10T00:06:09+09:00
Subject: Re: Reg: tiny contest: who's faster? (add_a_gram)

[Tobias Reif]:
>> Note that the problems on the website you gave are all dynamic
>> programming problems and can be solved almost trivially once you are
>> aware of that fact.
> 
> Can you elaborate?
> Do you mean that with the add-a-gram problem, one can stop as soon as 
> the longest chain is found; or what do you mean by "dynamic" here?

"Dynamic programming" is the general technique of caching computation
results so that they don't have to be computed more than once.

For example, calculating the fibonnaci function.

Without dynamic programming:

	def f1(i)
	  case i
	  when 0 then 1
	  when 1 then 1
	  else f1(i-1) + f1(i-2)
	  end
	end

With dynamic programming

	$cache = []
	def f2(i)
	  $cache[i] ||= case i
		when 0 then 1
		when 1 then 1
		else f2(i-1) + f2(i-2)
		end
	end

Now compare the running times of f1(100) and f2(100) ;)

// Niklas