Canoe Rental Problem:

There are n trading posts numbered 1 to n as you travel downstream. At any trading post i you can rent a canoe to be returned at any of the downstream trading posts j, where j i. You are given an array R[i, j] defining the costs of a canoe which is picked up at post i and dropped off at post j, for 1 i j n. Assume that R[i,i] = 0 and that you cant take a canoe upriver.

Your problem is to determine a sequence of rentals which start at post 1 and end at post n, and that has the minimum total cost.

a) Describe verbally and give pseudo code for a DP algorithm called CanoeCost to compute the cost of the cheapest sequence of canoe rentals from trading post 1 to n. Give the recursive formula you used to fill in the table or array.

b) Using your results from part a) how can you determine the sequence of trading posts from which canoes were rented? Give a verbal description and pseudo code for an algorithm called PrintSequence to retrieve the sequence.

c) What is the running time of your algorithms?