一：题目

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

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

二：思路

思路：本题的思路和矩阵链相乘思路一样，但递推方程不一样
1：首先判断是否用动态规划：从1到最后的站N,那么这个求解的过程是跳跃性的
可以从1到2 然后从2到 N,或则从1到3，从3到N,其是跳跃性的,判断其是动态规划

2：回归本题我们在考虑的时候，其中涉及到划分问题，比如从2到N,可以从2到3，然后从
3到N,那么的我们可以找类似的思路，那就是矩阵连相乘

3: 总结出递归方程：m[i][j] = m[i][k]+m[k][j] 这里和矩阵链相乘有区别
注意递推方程的区别：游艇：比如：从1到3，然后从3到N
矩阵链：比如从1到3，那么接下来就是4到N(A1A2A3A4A5)

三：来干了这杯代码

/*思路：本题的思路和矩阵链相乘思路一样，但递推方程不一样1：首先判断是否用动态规划：从1到最后的站N,那么这个求解的过程是跳跃性的可以从1到2 然后从2到 N,或则从1到3，从3到N,其是跳跃性的,判断其是动态规划2：回归本题我们在考虑的时候，其中涉及到划分问题，比如从2到N,可以从2到3，然后从3到N,那么的我们可以找类似的思路，那就是矩阵连相乘3: 总结出递归方程：m[i][j] = m[i][k]+m[k][j] 这里和矩阵链相乘有区别注意递推方程的区别：游艇：比如：从1到3，然后从3到N矩阵链：比如从1到3，那么接下来就是4到N(A1*A2*A3*A4*A5) */ #include<bits/stdc++.h> using namespace std;int main(){int m[300][300];//注意定义二维数组不可定义的范围过大 int N; cin >> N;// int m[N+1][N+1];//二维数组初始化 自己到自己为0for(int i = 0; i <= N; i++){m[i][i] = 0;} for(int i = 1; i <= N; i++){for(int j = i + 1; j <= N; j++){//这里的i+1 是 从 一个站到另一个站 cin >> m[i][j];}}//直接开始更新二维数组当中的值for(int i = N; i >= 1; i--){//for(int j = i + 1; j <= N; j++){//开始划分for(int k = i + 1; k < j; k++){int temp = m[i][k] + m[k][j];if(temp < m[i][j]){ //求取最小值 m[i][j] = temp;} } } } cout << m[1][N]; } //3 //5 15 //7

加油 陌生的赶路人！成功本就不易，我们怎能轻言放弃！！！！！！！！！！！！！！！！！！！

总结

以上是生活随笔为你收集整理的7-11 租用游艇问题 (15 分)(思路+详解+一步步分析+网格解决动态规划问题)Come boy!!!!的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。