OJ 1066 青蛙過河：動態規劃求最少踩石子數完整解析

OJ 1066 青蛙過河：動態規劃求最少踩石子數完整解析

經典動態規劃題目：青蛙從獨木橋起點 (0) 跳到終點 (L)，每跳距離在 [S, T] 之間，橋上有 M 顆石子。求青蛙過河最少踩到的石子數。

題目形式化建模

• 狀態定義：dp[i] 表示到達位置 i 的最少踩石子數
• 狀態轉移：dp[i] = min(dp[i-j]) + stone[i]，其中 j ∈ [S, T]，i-j ≥ 0
• 石子標記：stone[i] = 1 若位置 i 有石子，否則 0
• 邊界條件：dp[0] = 0，其餘初始化為大值 (INF)
• 答案：min(dp[L], dp[L+1], ..., dp[L+T-1])（跳過終點亦視為過河）

優化觀察：狀態壓縮與滑動窗口

由於 T ≤ 10，轉移只依賴前 T 個狀態，可用大小 T 的循環陣列滾動更新，空間從 O(L) 降為 O(T)。但鑑於 L ≤ 20000，直接 O(L) 空間完全足夠，代碼更清晰。

完整 AC 程式碼（C 語言）

#include <stdio.h>
#include <string.h>

#define MAXL 20010
#define INF  0x3f3f3f3f

int stone[MAXL];
int dp[MAXL];

int main() {
    int L;
    while (scanf("%d", &L) == 1 && L) {
        int S, T, M;
        scanf("%d %d %d", &S, &T, &M);
        
        memset(stone, 0, sizeof(stone));
        for (int i = 0; i < M; ++i) {
            int pos; scanf("%d", &pos);
            stone[pos] = 1;
        }
        
        for (int i = 0; i <= L + T; ++i) dp[i] = INF;
        dp[0] = 0;
        
        for (int i = S; i <= L + T; ++i) {
            for (int j = S; j <= T; ++j) {
                if (i - j >= 0) {
                    if (dp[i-j] + stone[i] < dp[i])
                        dp[i] = dp[i-j] + stone[i];
                }
            }
        }
        
        int ans = INF;
        for (int i = L; i <= L + T; ++i)
            if (dp[i] < ans) ans = dp[i];
        
        printf("%d\n", ans);
    }
    return 0;
}

關鍵細節解析

1. 陣列長度 L+T：青蛙可能從 L-S 直接跳過終點，最遠落在 L+T-1，故 DP 陣列需覆蓋至 L+T
2. 初始化 INF：使用 0x3f3f3f3f 避免加法溢位，且 memset 可快速填充
3. 多測試用例：輸入以 0 結束，while(scanf("%d",&L)&&L) 同時處理讀取與終止判斷
4. 石子位置不重複：題目保證，無需去重

複雜度分析

• 時間：O(L × (T-S+1)) ≤ O(20000 × 10) = 2×10⁵ 操作，極快
• 空間：O(L+T) ≈ 20KB，遠小於限制

擴展思考

• 若 T 較大（如 1000），可用單調隊列優化轉移至 O(L)
• 若需輸出具體跳躍路徑，增加 pre[i] 記錄前驅位置即可回溯
• 本質是有向無環圖 (DAG) 上的單源最短路徑，拓撲序即為位置遞增序

此題是「狀態轉移只依賴固定寬度歷史窗口」型 DP 的典型範例，掌握其建模範式，可舉一反三解決類似跳躍、爬樓梯、最小代價路徑等問題。