Menu
Whenever I look at solutions to computer contests, I always see the term "dynamic programming". I Googled the term and read a few articles, but none of them provide a simple example of programming VS "dynamic" programming. So how is "dynamic" programming different than "normal" programming? (simple terms please!)
964
In D&C subproblems, they are substantially smaller then the original problem. In contrast, DP involves solving problems that are only slightly smaller than the original problem.
Dynamic Programming is a technique for solving problems with overlapping subproblems. Each sub-problem is solved only once and the result of each sub-problem is stored in a table ( generally implemented as an array or a hash table) for future references.
In software development projects, dynamic programming uses an algorithm that breaks down complex coding problems into subproblems. Programmers can then apply the optimized solution to the entire problem, depending on the type of solution they derive from each subproblem in the code.
Recursion takes time but no space while dynamic programming uses space to store solutions to subproblems for future reference thus saving time.
Dynamic Programming uses programming more in the sense used with Linear Programming -- a mechanism of solving a problem.
One description I recently read (but can no longer recall the source -- [citation needed]) suggested that the usual approach of divide and conquer used in recursion is a top-down approach to solving problems, while dynamic programming is a bottom-up approach to solving problems.
The Wikipedia article suggests computing the Fibonocci sequence is an excellent use of dynamic programming -- you memoize results as you compute them for further use in the algorithm, to avoid re-computing similar results.
Knuth's algorithm for line-breaking paragraphs is another good example of dynamic programming: if you consider the possibility of inserting line breaks between every word (and even breaking lines inside words, at hyphenation points), it feels like the only algorithms will be exponential -- or worse. However, by keeping track of the "badness" associated with previous line breaks, Knuth's algorithm actually runs in linear time with the size of the input. (I must admit that I don't fully understand Knuth's algorithm -- only that it is supremely clever.)
58
By "normal" programming, I think you mean C++/Java/C# programming, right?
Dynamic programming is not "programming" in that sense. It is not about writing code, but the word "programming" there is used in the context of solving complex problems by breaking them down into simpler problems.
3
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
