P4891 租用游艇（基础）

解题思路

第一步，读懂题目。 长江上有 n 个游艇出租站，从 1 号站到 n 号站排成一排。从 i 站到 j 站（i<j）租一次游艇要花 r(i,j) 元。游客可以从 1 号站出发，中途可以换船（比如先从 1 到 3，再从 3 到 5），问从 1 号站到 n 号站最少要花多少钱。

第二步，把问题拆小。 到 j 站的最少钱数，一定是从某个更前面的站 i 先到 i 站，再从 i 站一次性租到 j 站。也就是：最少钱数 dp[j] = min（dp[i] + r(i,j)），其中 i 从 1 到 j-1。就像坐公交车可以直达，也可以先坐一段再换乘，换乘方案里选最省钱的。

第三步，按顺序算。 先算 dp[1]=0（在 1 号站还没花钱），然后从小到大算 dp[2]、dp[3]……算 dp[j] 的时候，dp[1] 到 dp[j-1] 都已经算好了，直接套公式。这叫做动态规划，用"已经算好的小问题的答案"推出"更大问题的答案"。

具体例子： 样例 n=3，租金 r(1,2)=5，r(1,3)=15，r(2,3)=7。dp[2]=dp[1]+5=5；dp[3]=min(dp[1]+15, dp[2]+7)=min(15,12)=12。所以答案是 12，正好对应"先到 2 站再换到 3 站"最省钱。

边界情况： 如果 n=2，只有一个租法 dp[2]=r(1,2)。租金有可能比较大，所以 dp 数组初值要设成很大的数（比如 1e9），表示"还没算出来"。

参考代码

// 租用游艇：从1站到n站最少租金，dp[j]=min(dp[i]+r(i,j))，i<j
#include <iostream>
using namespace std;

int n, r[205][205], dp[205]; // r[i][j]为i到j的租金

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++)
            cin >> r[i][j];
        dp[i] = 1000000000; // 先设为无穷大
    }
    dp[1] = 0; // 从1站出发不用钱
    for (int j = 2; j <= n; j++)
        for (int i = 1; i < j; i++)
            if (dp[i] + r[i][j] < dp[j])
                dp[j] = dp[i] + r[i][j];
    cout << dp[n] << endl;
    return 0;
}

复杂度分析

需要计算 n 个 dp 值，每个 dp[j] 都要枚举 j-1 个 i，所以时间复杂度是 O(n²)。n 最大约 200，也就是 4 万次计算，很快。空间上只用了两个一维数组，是 O(n)。