You are reading another tutorial in the Algorithm Techniques multi-part series. As the title suggests, today we are going to briefly present the dynamic programming algorithm technique. The truth is, dynamic programming is one of the most discussed techniques in the algorithmic literature, especially since it refers to a large number of algorithms. Theoretically thousands of problems can be solved with its implementation.
Now that you have grasped the basic concepts and the theory that lies behind dynamic programming, it'd be worthwhile to also find out which traits should be present before approaching a problem via the dynamic programming technique. First off, the optimality principlemust apply; a recursive formula should exist.
Secondly, the problem should notbe solvable by the greedy strategy. Why not? Well, if a so-called greedy algorithm solves the problem and returns the global optimal solution, which can be mathematically proven, then it is unnecessary to try dynamic programming. Implementing and coding a greedy algorithm is always faster and easier.
A third criterion requires the assumption that lots of sub-problems are identical. You see, one of the most outstanding differences between dynamic programming and divide and conquer is that the former does not do unnecessary work by repeatedly solving identical problems that were already solved once. If it isn't likely at all that identical sub-problems could exist, then opting for the divide and conquer approach might be better.
Summing these all up, dynamic programming is truly a unique algorithm technique. However, in the real world there are lots of common algorithms based on it, including string algorithms such as the longest common sub-sequence and longest common sub-string. Typical prime example problems can be also solved with it, such as the knapsack and the traveling salesman exercises. Google for these and you will see what I mean.
Furthermore, I'd like to invite you to join our experienced community of technology professionals with knowledge of all areas of IT&C starting from software and hardware up to consumer electronics at Dev Hardware Forums. As well, be sure to check out the community of our sister site at Dev Shed Forums. We are friendly and we'll do our best to help you.
DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.