Dynamic Programming Practice Problems : Canoes and Posts

Dynamic Programming Practice Problems : Canoes and Posts

You are traveling by a canoe down a river and there are n trading posts along the way. Before starting your journey, you are given for each 1 <= i < j <= n, the fee f(i,j) for renting a canoe from post i to post j. These fees are arbitrary. For example it is possible that f(1,3) = 10 and f(1,4) = 5. You begin at trading post 1 and must end at trading post n (using rented canoes). Your goal is to minimize the rental cost. Give the most efficient algorithm you can for this problem. Be sure to prove that your algorithm yields an optimal solution and analyze the time complexity.

Solution :

Let m[i] be the rental cost for the best solution to go from post i to post n for 1 <= i < n.

The final answer is in m[1].

We can recursively, define m[i] as follows:

m[i] = 0                                                                 if i = n

          OR

          min {for all i<j <=n }(f(i,j) + m[j])                otherwise

Proof of correctness :

The canoe must be rented starting at post i (the starting location) and then returned next at a station among i + 1, . . . , n. In the recurrence we try all possibilities (with j being the station where the canoe is next returned).

Furthermore, since f(i,j) is independent from how the subproblem of going from post

j, . . . , n is solved, we have the optimal substructure property.

For the time complexity there are n subproblems to be solved each of which takes

O(n) time. These subproblems can be computed in the order m[n],m[n−1], . . . ,m[1].

Hence the overall time complexity is O(square(n)).

NOTE: One (of several) alternate general subproblem form that also leads to an O(square(n)) algorithm is to find the best solution to get from post i to post n where the canoe cannot be exchanged until post j is reached (for 1< i < j n).