租用游艇问题---动态规划

问题描述 长江游艇俱乐部在长江上设置了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-1行是r(i,j),1<=i<j<=n。 (例如： 4 5 15 30 7 16 20

输出：21

分析

r(i,j)表示游艇出租站i到j之间的租金 m(i,j)表示从出租站i出发，到达第i+j站需要的最少租金 例如m(1,3)就表示从第1站出发，到达第4站所需的最少租金 而m(1,3)可以有多种租用方案，例如可以1-2，2-4 或者1-2,2-3,3-4，或者1-3,3-4 由此可以得出递归式： m(i,j) = min{ m(i,s)+m(i+s,j-s) , r(i,i+j) } 2 ≤j ≤n-i ,1 ≤s < j 且m(i,1) = r(i,i+1);m(n,1) = 0;

代码

#include<stdio.h> 
#define MaxSize 100
#define MAX_INT 9999
#define Min(a, b) (a < b ? a:b )
int r[MaxSize+1][MaxSize];

void solve(int n){
	int m[n+1][n+1];
	//初始化m数组 
	for(int i = 1; i <= n; i++){
		//m(i,1) = r(i,i+1);m(n,1) = 0; 
		if(i == n) m[i][1] = 0;
		else m[i][1] = r[i][i+1];
		
		for(int j = 2; j <= n; j++){
			m[i][j] = MAX_INT;
			m[n][j] = 0;
		}
	}
	//自顶向下递归计算 
	for(int i = n-1; i >= 1; i--){//从第n-1站开始计算  ，如果从i=n开始，则m[n][j] = 0,从终点站开始是没有意义的 
		for(int j = 2; j <= n-i ; j++){//j从2开始，因为如果j等于1，就是m[i][1]=r[i][i+1],已经是最小值了 
			for(int s = 1; s < j; s++){//s表示在i~i+j中间的i+s站归还游艇，并从i+s站开始下一阶段的旅行 
				int minf;
				minf = Min(m[i][s]+m[i+s][j-s],r[i][i+j]);
				if(minf < m[i][j])
					m[i][j] = minf;
			}
		}
	}
	printf("%d",m[1][n-1]);
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1; i < n; i++){
		for(int j = i+1; j <= n; j++)
			scanf("%d",&r[i][j]);
	}
	solve(n);
	return 0;
}