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

长江游艇俱乐部在长江上设置了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"); }