Assignment:
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?
Provide complete and step by step solution for the question and show calculations and use formulas.