Dynamic Programming with an example of all-pairs shortest paths

Share this post!

Vote this!

Dynamic programming is a powerful technique for solving problems that might otherwise appear to be extremely difficult to solve in polynomial time. Algorithms built on the dynamic programming paradigm are used in many areas of CS, including many examples in AI (from solving planning problems to voice recognition).
 Dynamic programming works by solving subproblems and using the results of those subproblems to more quickly calculate the solution to a larger problem. Unlike the divide-and-conquer paradigm (which also uses the idea of solving subproblems), dynamic programming typically involves solving all possible subproblems rather than a small portion.  more...