Home arrow Development Cycles arrow Page 4 - Dynamic Programming Algorithm Technique

Dynamic Programming Algorithm Technique

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.

Author Info:
By: Barzan "Tony" Antal
Rating: 5 stars5 stars5 stars5 stars5 stars / 15
October 14, 2008
  1. · Dynamic Programming Algorithm Technique
  2. · The Theory
  3. · The Theory, Continued
  4. · Concluding Thoughts

print this article

Dynamic Programming Algorithm Technique - Concluding Thoughts
(Page 4 of 4 )

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 principle must apply; a recursive formula should exist.

Secondly, the problem should not be 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.

blog comments powered by Disqus

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


© 2003-2019 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials