本文主要是介绍游艇出租问题（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
长江游艇俱乐部在长江上设置了n个游艇出租站1,2,3…,n。游客可以在这些游艇出租站用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r（i，j），1<=i<j=n。试设计一个算法，计算从游艇出租站1到出租站n所需的最少租金。
输入描述：第一行表示有n个站点，接下来n-1行是r（ i , j）。
输出描述：输出从游艇出租站1到出租站3所需的最少租金
样例输入：
3 //站数
5 15 //从第1站到其他相应各站的租金
7 //从第2站到其他相应各站的租金
样例输出：
12
算法设计：
使用动态规划的思想，通过逐步计算每个出租站的最小租金，并利用已知的最小租金来计算后续出租站的最小租金。设dp[n]为出租站1到达出租站n-1所需最小租金，rent[i][j]为出租站i到出租站j的租金。先考虑边界条件：dp[0]=0，即从出租站1到达自身的租金为0；易知，当前出租站i所需最小租金应该等于前i个出租站中第x个出租站的dp[x]值+rent[x][i]（此时耗费的租金最少），所以遍历搜索前i个出租站dp值，得出最小耗费出租站x，即可得出dp[i]，dp[n]则为从游艇出租站1到出租站n所需的最少租金。状态转移方程如下：
代码实现：
#include <iostream>
using namespace std;
const int N=100;
int rent[N][N];
int MinRent(int n){int dp[n];// dp[n]表示从出租站1到达出租站n-1所需最小租金for (int i = 0; i < n; ++i) { //用于存储最小租金，先定义为极大值dp[i]=INT_MAX;}dp[0]=0;// 从出租站1到达自身的租金为0for (int i = 1; i < n; ++i) { //遍历所有出租站，得出dp[i]for (int x = 0; x < i; ++x) {if(dp[x]!=INT_MAX&&dp[x]+rent[x][i]<dp[i])dp[i]=dp[x]+rent[x][i]; //动态转移方程}}return dp[n-1];
}
int main(){int n;cout << "请输入游艇出租站数n: ";cin >> n;cout << "请输入每站到达其他各站的租金\n";for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {cin >> rent[i][j];}}int min= MinRent(n);cout << "从第一站到第" << n << "站所需花费最小租金为: " << min << endl;
}
运行结果：
这篇关于游艇出租问题（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
