洛谷 P1359 租用游艇 C语言 记忆化搜索

题目:

https://www.luogu.com.cn/problem/P1359

题目描述

长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,⋯ ,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j)（1≤i<j≤n）。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。

输入格式

第一行中有一个正整数 n，表示有 n 个游艇出租站。接下来的 n−1 行是一个半矩阵 r(i,j)（1≤i<j≤n）。

输出格式

输出计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金。

思路：

1.将站点i到达站点j的费用存入二维数组。

2.状态转移方程，从站点1开始出发，会发现每次都会有n-i个站点可以走，所以需要一个循环，和一个参数来限制走的站点的范围。

代码如下：

#include<iostream> 
#include<string>
#include<climits>
int n;  
using namespace std;
typedef long long ll;
ll mem[201];//记录到达第x层花费最小花费
ll money[201][201]; //从行到列就是从当站点i到站点j花费的钱 
ll dfs(ll x,ll end)//x为当前站点，end为最多可以上的楼层 
{
	ll sum = INT_MAX;
	if(mem[x])
	return mem[x];
	if(x == n)
	return 0;
	 
	for(int i = 1; i <= end ; i++)
	{
		sum = min(sum,dfs(x + i,end - i) + money[x][x + i]); 
	}
	
	mem[x] = sum;
	return sum;
 } 
int main(void) 
{
	cin >> n;
	for(ll i = 1 ; i <= n ; i++)
	{
		for(ll j = i + 1 ; j <= n ; j++)
		{
			cin >> money[i][j];	
		}
	}
	 cout << dfs(1,n-1);
    return 0; 
}