Dynamisc programming

Dynamic programming is not a programming technique but rather a strategy to find an optimal solution to a problem. In the same way as "linear programming" can be used to find optimal solutions given a set of linear equation we can use dynamic programming. The strategy can be used to solve a problem if we can define a solution to the problem in terms of one smal step and the solution to a smaller problem; we thus use recursion as the tool. To find a solution in exponential time is often easy but if do it right we will be able to find a solution in polynomial time.

In order understand what we are talking about you should repeat the chapters on graph theory in the previous courses and how you can find the shortest path between two vertices. 

• dynamic.pdf