长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。用c++实现该问题，含算法思路及代码注释

这是一个典型的最短路径问题，可以使用Dijkstra算法或者Floyd算法来解决。这里我们使用Dijkstra算法来求解。

Dijkstra算法的基本思路是从起点开始，每次选择当前最短路径的节点进行拓展，直到到达终点或者所有节点已经拓展完毕。具体实现时，可以使用一个优先队列来保存当前可以拓展的节点，并按照节点到起点的距离从小到大进行排序。

以下是C++代码实现：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1005;

int n; // 游艇出租站数量
int r[MAXN][MAXN]; // 租金
int dis[MAXN]; // 起点到各点的最短距离
bool vis[MAXN]; // 是否已经确定最短路径

struct Node {
    int id, d; // id是节点编号，d是当前路径长度
    bool operator < (const Node& rhs) const {
        return d > rhs.d; // 按距离从小到大排序
    }
};

void dijkstra() {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[1] = 0;

    priority_queue<Node> q;
    q.push({1, 0});

    while (!q.empty()) {
        Node cur = q.top();
        q.pop();

        int u = cur.id;
        if (vis[u]) continue;
        vis[u] = true;

        for (int v = u + 1; v <= n; ++v) {
            if (dis[v] > dis[u] + r[u][v]) {
                dis[v] = dis[u] + r[u][v];
                q.push({v, dis[v]});
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            cin >> r[i][j];
            r[j][i] = r[i][j]; // 因为是无向图，所以需要对称存储
        }
    }

    dijkstra();

    cout << dis[n] << endl;

    return 0;
}

时间复杂度为O(n^2logn)。其中n^2是因为需要枚举每一条边，logn是因为每次需要从优先队列中取出距离最小的节点。