There are n trading posts numbered 1 to n, as you travel downstream. At any trading post i, you can rent a canoe to be returned at any of the downstream trading posts j > i . You are given a cost array R (i , j ) giving the cost of these rentals for 1 i j n . We will have to assume that R (i , i ) = 0 and R (i , j ) = if i > j . For example, with n = 4, the cost array may look as follows: Therowsarethesources(i-s)andthecolumnsarethedestinations(js).

1234 10237 2 024 302 40

The problem is to find a solution that computes the cheapest sequence of rentals taking you from post 1 all the way down to post n. In this example, the cheapest sequence is to rent from post 1 to post 3 (cost 3), then from post 3 to post 4 (cost 2), with a total cost of 5 (less than the direct rental from post 1 to post 7, which would cost 7).

1) Design a brute force

2) DIVIDE AND CONQUER

3) DYNAMIC PROGRAMMING

please use in this three ways to solve this problem. You need to print the cheapest solution, as well as the sequence.

What is the asymptotic complexity of this algorithm?