Dynamic programming is an algorithm technique which is usually based on:
- recurrent formula
- one or more starting states
A sub-solution of the problem is constructed from previously found ones, which starts from the starting states. DP solutions have a polynomial complexity where the brute-force or backtracking solutions usually have exponantial solutions. DP computes the recurrence efficiently because it stores (memoized) the sub-probelms and use the results instead of recalculating them everytime.
These are the examples implemented in this project: The resources used are the following TopCoder and [The Algorithm Design Manual](http://www. algorist.com/)
- Fibonacci number
- Longest Increasing Sub Sequence
- Min total coins to add to a sum
- Floyd–Warshall: Single source shortest path for in a graph with positive and negative weighed edges (not started)
- Bellman–Ford: Single source shortest path for a graph with positive and negative weighted edges, but no negative cycles. (not started yet)
- Dijkstra Algorithm: Single source shortest path for a grpah with only positive edges.(hasn't started)
- String Matching
- Partitioning Problem (working on it)