游艇出租问题（动态规划）

游艇出租问题（动态规划）

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

运行结果：