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 all 1ij). For example, one cost array with n=4 might be the following.

The problem is to find a dynamic programming algorithm that computes the cheapest sequence of rental taking you from post 1 all the way down to post n. In this example, the cheapest way is to rent canoes from post 1 to post 3, and then from post 3 to post 4 for a total cost of 5. The second problem is to find the least cost associated with this sequence. You are to design a dynamic programming algorithm for both the problems.

Describe the table and what does each entry in the table mean?

How will the table be initialized?

In which order the table will be filled?

What is the recurrence?

How will you use the table to find what is cheapest sequence of canoe rental (for the first problem) and the least cost of the canoe rentals (for the second problem)?

Give the asymptotic complexity of the algorithms. Implement the your algorithm by using C

Input: The input consists of n+1 lines: the first line will be a single integer that indicates the number of trade posts. The next n lines will give the rental costs that taking post i to j (where ij). For example, the input of the above given example would be:

4 0 2 3 7 0 2 4 0 2 0 

Output: Output the minimum cost to travel from post 1 to post n. Output the sequence of canoe renting that achieves the goal. For example, the sample output of the above given example would be:

The minimum cost is 5 The renting sequence is 1->3->4 

Requirements:

Your program is required to support up to 100 posts.

Your program can either take keyboard input or input redirection from a file. For example,

$ myexec  
In the readme file, please describe your algorithm design by answering all the questions above. In addition, please provide the commands that compile and run the program. Meanwhile, provide at least one sample run to show your program works.
 
List the existing bugs in your program.
 
 
  Cost from i T3