游艇---动态规划实验2

问题描述
在长江水域内，游艇租赁服务设有n个站点，编号依次为1，2，…，n。游客可在任一站点租借游艇，并在位于其下游的任意站点归还。从站点i至站点j的租金为r(i,j)，其中满足1£i<j£n。现需设计一种计算方案，以确定从站点1前往站点n所需的最低租金总额。

编程任务
针对给定的各站点间租金数据r(i,j)，其中满足1£i<j£n，编写程序以求解从站点1到站点n所需的最少租金金额。

数据输入
输入数据来源于文件input.txt。文件第一行包含一个正整数n（n<=200），用于表示总共有多少个游艇出租站。随后的n-1行中依次记录了各个r(i,j)值。

（例如：3
5 15
7 表示存在3个出租站，其中第1站到第2站的费用为5元；第1站到第3站的费用为15元；第2站到第3站的费用为7元）

结果输出
当程序执行完毕后，需将计算得到的从站点1至站点n所需最低租金写入文件output.txt中。输入文件示例输出文件示例

该问题与课堂上讲解过的矩阵链乘法问题存在相似之处
此题与矩阵链乘法的问题较为类似，整体难度较低
其中dp[i][j]用于表示从i到j之间租用游艇所需要的最小花费
动态规划递推公式如下：
dp[i][j] =
{
0 i=j;
min(dp[i][k]+dp[k