動態規劃經典題：游艇租賃最小費用問題解析

游艇租賃最小費用：動態規劃與 Floyd 演算法應用

長江游艇俱樂部在 n 個站點提供租賃服務，游客可在任意上游站點租艇、下游站點還艇。給定站點間租金 r(i,j)，求從站點 1 到站點 n 的最小租金。這是典型的動態規劃問題，可轉化為有向無環圖最短路徑求解。

問題輸入輸出格式

• 輸入：第一行 n (≤200)，接著 n-1 行租金矩陣上三角資料
• 輸出：最小租金總額
• 範例：n=3，租金矩陣 [[0,5,15],[0,0,7],[0,0,0]]，最小費用 12 (1→2→3)

動態規劃狀態轉移

定義 f[i][j] 為從站點 i 到 j 的最小費用。狀態轉移方程：

f[i][j] = min(f[i][j], f[i][k] + f[k][j])  對所有 i < k < j

按區間長度遞增順序計算，最終答案為 f[0][n-1]（0-based 索引）。

Floyd 演算法實作

#include <stdio.h>
int f[201][201], n, i, j, k, p, tmp;

void solve() {
    for (k = 2; k < n; k++)           // 中間站點
        for (i = 0; i < n - k; i++) { // 起點
            j = i + k;                // 終點
            for (p = i + 1; p < j; p++) { // 嘗試所有中轉點
                tmp = f[i][p] + f[p][j];
                if (f[i][j] > tmp) f[i][j] = tmp;
            }
        }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i++)
            for (j = i + 1; j < n; j++)
                scanf("%d", &f[i][j]);
        solve();
        printf("%d\n", f[0][n-1]);
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n³) - 三層巢狀迴圈
• 空間複雜度：O(n²) - 費用矩陣儲存
• n ≤ 200 時約 800 萬次運算，完全在時限內

優化方向

因為圖為有向無環圖（DAG），可用拓撲排序 + 動態規劃將複雜度降至 O(n²) 或 O(E)，但 n=200 時 Floyd 寫法更簡潔易懂，工程實務上足夠使用。