题目来源：王晓东，《算法设计与分析》

长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n所需的最少租金。

输入格式:

第1 行中有1 个正整数n（n<=200），表示有n个游艇出租站。接下来的第1到第n-1 行，第i行表示第i站到第i+1站,第i+2站, … , 第n站的租金。

输出格式:

输出从游艇出租站1 到游艇出租站n所需的最少租金。

输入样例:

在这里给出一组输入。例如：

3
5 15
7

输出样例:

在这里给出相应的输出。例如：

12

#include<iostream>
#include<cstdlib>
using namespace std;

//用于保存站点之间的费用
int fee[201][201];

//动态规划填m表
int FeeChain(int n){
    //对角线，即始末相同。
    for(int i=1; i<=n; i++) fee[i][i] = 0;

    //循环填表
    for(int r=3; r<=n; r++) {
    //由于1-2,2-3,3-4...即表的第二层已经是最少费用了，可以直接从第三层开始
        for(int i=1; i<=n-r+1; i++) {
            int j=i+r-1;

            for(int k=i+1; k<j; k++) {
                int t = fee[i][k] + fee[k][j];
                //使用更短的费用代替原来的
                if(t<fee[i][j]) fee[i][j]=t;
            }
        }
    }
    return fee[1][n];
}

int main() {
    //游艇出租站的个数
    int n;
    
    cin>>n;
    for(int i=1; i<n; i++) {
        for(int j=i+1; j<n+1; j++) {
            cin >> fee[i][j];
        }
    }
    cout<<FeeChain(n);
    //system("pause");
}