租用游艇问题

问题描述: 长江游艇俱乐部在长江上设置了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所需的最少租金.

数据输入: 第1行有一个正整数n, n<=200, 表示有n个游艇出租站. 接下来n-1行是r(i,j), 1<=i<j<=n.

结果输出: 游艇出租站1到n最少租金.

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int dp[205][205];

int main(){
	cin>>n;
	for(int i=1,j=2;;) 
	{
		scanf("%d",&dp[i][j]);
		if(i==n-1 && j==n) break;
		j++;
		if(j>n)
		{
			i++;
			j=i+1;
		}
	}
	for(int i=2;i<=n-1;i++) //步长 
	{
		for(int j=1,k=j+i; k<=n ; j++,k=j+i)
		{
			for(int w=j+1;w<k;w++)
			{
				dp[j][k] = min(dp[j][w]+dp[w][k],dp[j][k]);
				
			}
		}
	}
	cout<<dp[1][n]<<endl;
	return 0; 
}