游艇租赁（区间DP）思路分析及代码实现（有注释）

游艇租赁（区间DP）思路分析及代码实现（有注释）

游艇租赁（区间DP）

题目：

每个游艇出租站到出租站需要不同的租金，求从出租站i到出租站j所需要的最少租金。

思路分析：

状态表示： 我们令f[i] [j]表示从出租站i到出租站j需要的最少租金

初始化：

对于状态表示f[i] [j]初始化：

当i == j : f[i] [j] = 0;

当i ！= j (只经过两个站点)： f[i] [j] = 出租站i 到 出租站j 所需要的租金。

//在输入两点距离时候就可以完成对f状态数组的初始化：
//r数组存放两个点之间需要的租金
//对i = j的情况，因为f是开在全局变量，默认值为0，所以就不用管了
for(int i = 1; i <= n; i ++){for(int j = i + 1; j <= n; j ++){cin >> r[i][j];f[i][j] = r[i][j];	//初始化}
}

讨论/划分：

因为从一个站点到另一个站点，可以通过中间某点，得到更少的租金，所以根据k位置（i < k < j）停靠进行划分：

对于从站点i到站点j，我们可能选择到中间某个站点k，得到更少的租金（当然也有可能不经过中间站点k，从站点i到站点j就是最少租金），可以分成两个子问题，即f[i] [k]和f[k + 1] [j], 因为根据状态数组的定义，f[i] [k] 和 f[k + 1] [j] 都是需要的最少租金，因此我们要进一步对站点i 到站点k + 1 和 站点k + 1 到站点j进行最少租金的选取（可能需要选某个中间点，可能直接到达），直到最后递归到一个站点为止。很容易看出，本题是具有最优子结构的，因此我们可以自底向上先把每个子问题的最优值计算出来，再求最优值即可。

伪代码：

for(int len = 3; len <= n; len ++)	//枚举子问题的区间长度
{for(int i = 1; i <= n - len + 1; i ++)	//枚举子问题的左端点{int j = i + len - 1;	//通过枚举的子问题的左端点和区间长度 求出右端点for(int k = i + 1; k <= j - 1; k ++)	//求当前i 到 j 能够经过的中间站点{int tmp = f[i][k] + f[k][j];	//i 到 j 通过中间站点k 需要的最少租金if(tmp < f[i][j])	//i 到 j 能够经过中间站点k获得最少租金{f[i][j] = tmp;	//更新最小租金s[i][j] = k;	//记录k}}}
}

复杂度：

**时间复杂度：**O（n^3）

**空间复杂度：**O（n^2）

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3 + 5;
/*
r：记录两点的租金
f：记录两点的最少租金
s：记录两点是否是要经过中间站点得的最少租金，如果s = 0 说明不需要经过中间站点即可达到最少租金
*/
int r[N][N], f[N][N], s[N][N];	
int n;
//输出最租费的路径
void print(int i, int j){if(s[i][j] == 0){cout << "--" << j;return;}print(i, s[i][j]);print(s[i][j], j);
}int main()
{int i, j;cout << "请输入站点的个数：";cin >> n;cout << "请依次输入各站点之间的租金："; for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++){cin >> r[i][j];f[i][j] = r[i][j]; //初始化}}for (int len = 3; len <= n; len++) //枚举子问题的区间长度{for (int i = 1; i <= n - len + 1; i++) //枚举子问题的左端点{int j = i + len - 1;                 //通过枚举的子问题的左端点和区间长度 求出右端点for (int k = i + 1; k <= j - 1; k++) //求当前i 到 j 能够经过的中间站点{int tmp = f[i][k] + f[k][j]; // i 到 j 通过中间站点k 需要的最少租金if (tmp < f[i][j])           // i 到 j 能够经过中间站点k获得最少租金{f[i][j] = tmp; //更新最小租金s[i][j] = k;   //记录k}}}}cout << "花费的最少租金为" << f[1][n] << 'n';cout << "最少租金经过的站点" << 1;print(1, n);return 0;
}