动态规划之游艇租用问题

     最近老师在将动态规划，好几节课了仍没讲完。上节课留了一道游艇租用的问题，准备下节课让同学们去黑板上写出来。本人稍愚钝，周末的时候自己啃掉了这部大块头，对动态规划的理解也稍稍有了点进步。好了，废话少说，咱进入正题。

      问题描述：

              长江游乐俱乐部在长江上设置了n个游艇出租站，游客可以在这些游艇出租站用游艇，并在下游任何一个游艇出租站归还游艇，游艇出租站i到j之间的租金是rent(i,j)，其中1<=i<j<=n。试设计一个算法使得游客租用的费用最低。

      问题分析：

       1、这道题用动态规划来做。将上述的从游艇出租站i到j的租金记为rent(i:j)，并假设该问题存在一个最优解决方案，即存在最小租金的方法，那么也就是说中间k我可以归回游艇并重新租用另一个游艇到达j，则原问题的子问题rent(i:k)和rent(k:j)也一定是最优的解决方案。

       2、证明

             若有一个rent（i:k）的租借方案planA比方案planB所包含的rent（i:k）的租借方案所用的费用更少则用planA代替planB,则得到的最小费用要比rent（i:j）的费用小，这与假设存在矛盾。故原问题的租借方案一定是最优的。由该问题的最优子结构性质可知，我们能通过确定问题的最优子结构性质来确定问题的最优解决方案。

      代码分析：

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

void rentOfBoat(){
	//i租店到j租店，rent为租金，number 为租店的个数
	int i,j,k,rent,number;
	//二维向量用来存储费用
	vector<vector<int>>list;
	vector<int>line;
	cout<<"请输入租店的个数";
	cin>>number;

	for(i=0;i<number-1;i++){
		list.push_back(line);
		for(j=0;j<=i;j++){
			//list[0][0]的租金为0
			list[i].push_back(0);
		}

		for(j=i+1;j<number;j++){
			cout<<"请输入第"<<i+1<<"到第"<<j+1<<"个租店之间的的费用：";
			cin>>rent;
			list[i].push_back(rent);
		}
	}

	//从2个租店开始，递增分析费用
	for(k=2;k<number;k++){
		for(i=0;i<number-k;i++){
			int mark=i+k;
			for(j=i+1;j<mark;j++){
				//取最小值
				if(list[i][j]+list[j][mark]<list[i][mark]){
					list[i][mark]=list[i][j]+list[j][mark];
				}
			}
		}
	}
	cout<<"最小的费用是";
	cout<<list[0][number-1]<<endl;
}

void main(){
	rentOfBoat();
}

由此可以看出选择的路线是1-4 然后4-5.

总结与反思：

     这道题的时间复杂是O(n^3)，应该还会有比这更为简单的算法。这道算法题最难理解的部分对于我来说就是mark的使用了，这东西犹如天外来物，相当的神奇，毫无道理却又把问题妥妥的给撂倒了。善哉也！