Introduction
Dynamic Programming is a technique for solving problems that are repetitive (recursive) in nature and have the following characteristics:
- The best solution to the problem would be the sum of the best solutions for the smaller problems it is made of.
- There are a small number of subproblems.
- A recursive (repetitive) structure where some stages are referred to repeatedly.
A simple example would be working backward in a maze from the end to the start. Of course in a maze there is only one correct path because all others are "dead ends" along the way. In the problems we will be solving, the paths that aren't correct don't stop (they're just longer than the correct one) and so you have to compare the paths to each other to find the best path possible. Try it with the maze on page 1 because this simple procedure is what dynamic programming is all about!
Example: Shortest Path
Let's begin with an example. Suppose we wish to get from Albuquerque in New Mexico (A) to Juneau (J) in Alaska in the road network displayed below. In order to calculate the 'shortest path' (shortest path problems are a group of problems that use dynamic programming to find the shortest--most efficient--path between two points) we will need to use dynamic programming. Try to find the best solution now, and then go to the next page for the answer!
Example 1: Shortest Path
Dynamic Programming: Why is it so important?
Dynamic Programming is important because it provides a computational method by which we can essentially 'work backward' from the solution in order to calculate the most efficient method by which to arrive at a given value. In other words, we can start at the end and then calculate our options by moving backward. This allows us to find the most optimal paths to take, or decisions to make, at each successive step and the most optimal of these options must be part of the optimal solution for the entire problem.
