Kaz Kylheku
8/4/2015 11:53:00 PM
On 2015-08-04, Charles Richmond <numerist@aquaporin4.com> wrote:
> "Chad" <cdalten@gmail.com> wrote in message
> news:ad9aaa3d-2daa-41e0-a619-66e9ad07def7@googlegroups.com...
>>Recently on Project Euler I got introduced to the idea of Dynamic
>>Programming to solve some of the difficult >problems. This is the first
>>time I heard of the programming technique. This is primary because I'm a
>>self >taught programmer. The only other programming techniques I'm aware of
>>are backtracking and the brute force >approach. With that, what are some
>>other programming techniques?
>
> Backtracking uses dynamic programming in a way... because in backtracking,
> one must keep data indicating what paths have already been tried so one will
> *not* take those paths again.
Paths have already been tried only if the tree being searched has
common subtrees (i.e. is a DAG). If there are no common subtrees,
then the problem has no overlapping subcases, and so isn't a candidate
for dynamic programming (memoization).
Even in the absence of overlapping subcases, backtracking must avoid going
down the prior paths, to keep trying new avenues and eventually terminate. That
requires mainintaing state, for instance in the stack being used for recursion,
which holds activation frames that maintain suspended procedures.
Each suspended procedure knows what statement to execute next
when its child procedure returns.