Path: csiph.com!au2pb.net!feeder.erje.net!1.eu.feeder.erje.net!newsfeed.fsmpi.rwth-aachen.de!newsfeed.straub-nv.de!eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail From: Kaz Kylheku Newsgroups: comp.programming Subject: Re: Programming techniques Date: Tue, 4 Aug 2015 23:52:56 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 25 Message-ID: <20150804163519.69@kylheku.com> References: NNTP-Posting-Host: OGJi3KNpFOhM58UHZwXj0w.user.speranza.aioe.org X-Complaints-To: abuse@aioe.org User-Agent: slrn/pre1.0.0-18 (Linux) X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:5579 On 2015-08-04, Charles Richmond wrote: > "Chad" 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.