Is there any way to program *but* dynamic programming?
Author |
Message |
DtY
![](http://compsci.ca/v3/uploads/user_avatars/8576159234be48b7a8b0e8.png)
|
Posted: Sat Oct 16, 2010 4:21 pm Post subject: Is there any way to program *but* dynamic programming? |
|
|
[quote=Wikipedia]In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler steps. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller[1] and optimal substructure (described below). When applicable, the method takes far less time than naive methods.[/quote]
This seems like a pretty vague idea, but every one seems to be talking about it as though it were something amazing, not that I'm saying it isn't, just that?as far as I can see?there's no other way to program.
The idea (one of, at least) of functional programming is to break down the problem into smaller bits by creating functions. The idea of object oriented programming is to break down the problem into smaller bits by creating objects or classes. The idea of concurrent programming is to break the problem down into smaller pieces that can be run at the same time. The idea of event based programming is to break the problem down into smaller bits by adding event responders.
I did a problem (can't remember which one it was now), and I did it using recursion. The solution described how to do it with dynamic programming. Had I memoized the function, my solution would have been exactly the same. Is there really anything special about dynamic programming (that's not present in other paradigms)? |
|
|
|
|
![](images/spacer.gif) |
Sponsor Sponsor
![Sponsor Sponsor](templates/subSilver/images/ranks/stars_rank5.gif)
|
|
![](images/spacer.gif) |
A.J
![](http://compsci.ca/v3/uploads/user_avatars/119833057151651227b0d87.gif)
|
Posted: Sat Oct 16, 2010 6:17 pm Post subject: RE:Is there any way to program *but* dynamic programming? |
|
|
Well, if the subproblems were to be solved only once, then a bottom-up dynamic programming algorithm outperforms a top-down memoized algorithm. However, if some subproblems need not be computed at all, a memoized solution has the advantage of solving only those that are required for the whole problem. |
|
|
|
|
![](images/spacer.gif) |
Brightguy
![](http://compsci.ca/v3/uploads/user_avatars/527435178485ad4c287538.gif)
|
Posted: Sat Oct 16, 2010 6:25 pm Post subject: Re: Is there any way to program *but* dynamic programming? |
|
|
The name is a bit ambiguous. An algorithms teacher I had once remarked we should just call it "write stuff down and remember it rather than recomputing it" or something to that effect.
But it can definitely be useful. The naive method of computing the Fibonacci numbers can be decreased from doubly exponential time to exponential time simply by using memoization. |
|
|
|
|
![](images/spacer.gif) |
|
|