Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Is there any way to program *but* dynamic programming?
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
DtY




PostPosted: 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)?
Sponsor
Sponsor
Sponsor
sponsor
A.J




PostPosted: 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.
Brightguy




PostPosted: 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.
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 3 Posts ]
Jump to:   


Style:  
Search: