Dynamic Programming : Write an Algorithm to Minimize Cost

There are n trading posts along a river.  At any of the posts you can rent a canoe to be returned at any other post downstream.  (It is next to impossible to paddle against the current.)  For each possible departure point i and each possible arrival point j the cost of a rental from i to j is known.  However, it can happen that the cost of renting for i to j is higher that the total cost of a series of shorter rentals.  In this case you can return the first canoe at some post k between i and j and continue your journey in a second canoe.  There is no extra charge for changing canoes in this way.

Give an efficient algorithm to determine the minimum cost of a trip by canoe for each possible departure point i to each possible arrival point j.  In terms of n, how much time is needed by your algorithm?