本文主要是介绍洛谷 1359.租用游艇，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：线性dp。
这道题有点像区间dp，又不全像。管他的，反正是dp的题目，主要是思路为好，什么类型的只要自己能分析出来，其实都是一样的核心思路，都是递推嘛，只不过换了个递推的对象。
这里用的二维dp,令dp[i][j]是从i到j的最小租金数。
我们想，题目中需要我们求到1-n的最小租金，那么我们能否从头遍历呢？这里教大家一个技巧，那就是递推的时候，要求大数，必定从小数开始递推；反过来，要求小数，必定从大数开始递推。
这道题的第一维是比较小的数，也就是1，我们就要考虑从后面开始推，而j这个数其实和i有关，它在题目中也说过了，i<j，所以j的最小值肯定是i+1,然后最大值一定是n，因为我们在第二维需要从小的数推到大的数。
解决下标的问题了，我们根据dp的含义来初始化，要我们求最小值，那么每一个dp的值初始时都应该是一个比较大的数，我们直接让它是无穷大。特殊的：dp[i][i]这种矩阵的对角线，我们需要特别注意，因为只有两个不同的站点之间才会有租金，那么从当前站点到站点本身就没有租金，怎么递推它都是0，所以这里需要额外注意。
好了，我们再想一下转移方程的事情。既然是从一个站点到终点，那么我们中途就可以分为好多路径，比如，我们从1--n，那么我们可能是从1--n-1再从n-1--n走过来的，也可能是1--n-2再从n-2--n走过来的，以此类推。可以说这里就是一个断点了。很像区间dp吧？
那么状态方程就能够写出来了:dp[i][j]=min(dp[i][j],dp[i][j-k]+arr[j-k][j])。其中k就是断点。
注意：k这里你可以从0开始遍历，也可以从1开始遍历，从0开始遍历其实就是相当于和dp[i][j]本身比较了，没什么意思；但是，k需要满足j-k>=i这个条件。其实大于好理解，因为租金站之间肯定是不能一样的，但是为什么要j-k==i呢？因为啊，我们可能是直接从起点走到终点，而不经过其他的站点，就相当于一步到位，不经过任何站点，我们需要考虑这种可能。
上代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_map>
#include<set>
#define int long long
#define MAX 1000
#define inf 0x3f3f3f3f
#define _for(i,a,b) for(int i=a;i<(b);i++)
using namespace std;
typedef pair<int, int> PII;
int n,m;
int counts,u=1;
int dx[] = { 0,1,0,-1};
int dy[] = { 1,0,-1,0 };
int dp[MAX][MAX];
int arr[MAX][MAX];
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n;memset(dp, inf, sizeof dp);for (int i = 1; i <= n; i++)dp[i][i] = 0;for (int i = 1; i <= n - 1; i++) {for (int j = i + 1; j <= n; j++) {cin >> arr[i][j];}}for (int i = n - 1; i >= 1; i--) {for (int j = i+1; j <=n; j++) {for (int k = 1; j-k>=i; k++) {dp[i][j] = min(dp[i][j], dp[i][j - k] + arr[j-k][j]);}}}cout << dp[1][n];return 0;
}这篇关于洛谷 1359.租用游艇的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
