There are n trading posts along a river numbered 1, 2, 3, ..., n. At any of the posts you can rent a canoe to be returned at any other post downstream. (It is impossible to paddle against the river, since it is too fast...) For each possible departure point i and each possible arrival point j (> i), the cost of a rental from i to j is known: it is C[i, j] > 0. However, it can happen that the cost of renting from i to j is higher than the total costs of a series of shorter rentals from i to j. In this case you can return the first canoe at some post k between i and j and continue your journey in a second (and, maybe, third, fourth ...) canoe. There is no extra charge for changing canoes in this way. Requried:
Give a dynamic programming algorithm to determine the minimum cost of a trip by canoe from each possible departure.