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

算法设计
对于给定的游艇出租站 i 到游艇出租站 j 之间的租金为 r(i, j)（1 ≤ i ≤ j ≤ n），计算从游艇出租站 1 到游艇出租站 n 所需的最少租金。

数据输入

输入文件 input.txt 提供输入数据。文件的第 1 行有 1 个正整数 n（n ≤ 200），表示有 n 个游艇出租站。接下来的 n 行是 r(i, j)（1 ≤ i ≤ j ≤ n）。

结果输出
将计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金输出到文件 output.txt。

input.txt
3
5 15
7

output.txt
12

#include <iostream>
using namespace std;

/*
3
5 15
7
和加括号也差不多，dp[i][j]=min(dp[i][k]+dp[k][j])
*/

int n;//出租站
int dp[210][210];

void init(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){ cin>>dp[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        dp[i][i]=0;//初始化，自己到自己不用花费
    }
}

void solve(){
    for(int len=2;len<=n;len++){//枚举区间长度
        for(int i=1;i<n&&i+len-1<=n;i++){//枚举起点
            int j=i+len-1;//终点
            for(int k=i;k<=j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
    cout<<dp[1][n]<<endl;
}

int main(){
    init();
    solve();
    return 0;
}