Algorithm analysis

 

We  have n stations along a river, numbered 1 to n in the direction of the  current. You can rent a boat at any station i, go down the river to a  station k> i, return the boat and pay a fee c (i, k) for the tour. It  is possible that c (i, k) is greater than c (i, j) + c (j, k), with j  being an intermediate station between i and k. In this case, it is  cheaper to rent a boat from i to j and then another from j to k. Give an  efficient algorithm that calculates the minimum cost of a trip from 1  to n. Depending on n, how long does your algorithm consume?