Canoeing on the cheap

Question

You are canoeing down a river and there are n renting 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. Prove that your algorithm yields an optimal solution and analyze the time complexity.

Please provide the Notation, optimality, recurrence, and algorithm.

Answer 1

I think if we begin with the notation, it might something like:

C(j) = Minimum cost of arriving at post # j, starting from # 1.

Now, we can try to write C(j) in terms of minimum C(i), where i < j.

Once that recurrence relation is there, that should do it.

Answer 2

I guess this is a example of All Pair Shartest Path Dynamic Programming algorithm where we have to return the Shortest Path from 1 to N

Comments

Using APSP will take O(n^3) time.  Using the simpler notation C(j), we can do this in O(n^2) time.