Problem 2: Minimizing Expenditure
This problem is called the stagecoach problem, and is a classic problem in dynamic programming. The background for the problem is said to lie in the frontier of the old west where a salesman is travelling from town S to town T and didn't wish to pay more for transportation than necessary.
Because the only means of transportation at the time were stagecoaches, the cost of travel would have to be found by adding the cost of the individual distances between the towns through which he would pass.
Problem 2: Minimizing Expenditure
Enter your answers in the left as two-point numbers. For example, to go from S to C, type in "SC". Type in 0 if you only use a four-stage path.
Try as many times as you wish until you arrive at the cheapest course!
Stage 5:
Stage 4:
Stage 3:
Stage 2:
Stage 1:
Your traverse distance is:
