POJ 1088 滑雪：記憶化 DFS 求最長下降路徑

題目描述

給定 R x C 網格高度圖，從任意格子出發，只能向上下左右移動到嚴格更低的格子。求最長滑雪路徑長度（格子數）。

解題思路：記憶化深度優先搜索

定義 dp[x][y] 為從 (x,y) 出發的最長下降路徑長度。遞歸公式：

dp[x][y] = 1 + max{ dp[nx][ny] }  // (nx,ny) 為四鄰域且 height[nx][ny] < height[x][y]

若 dp[x][y] 已計算直接返回，否則遞歸計算四鄰域。時間 O(R×C)，每個狀態只算一次。

C++ 代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 105;
int h[MAXN][MAXN], dp[MAXN][MAXN];
int R, C;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int dfs(int x, int y) {
    if (dp[x][y]) return dp[x][y];
    dp[x][y] = 1; // 至少自身
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= R && ny >= 1 && ny <= C && h[nx][ny] < h[x][y]) {
            dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);
        }
    }
    return dp[x][y];
}

int main() {
    while (scanf("%d%d", &R, &C) == 2) {
        for (int i = 1; i <= R; ++i)
            for (int j = 1; j <= C; ++j)
                scanf("%d", &h[i][j]);
        memset(dp, 0, sizeof(dp));
        int ans = 0;
        for (int i = 1; i <= R; ++i)
            for (int j = 1; j <= C; ++j)
                ans = max(ans, dfs(i, j));
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點

1. 邊界處理：數組開大一圈或判斷索引範圍。
2. 遞歸深度最大 10000，C++ 默認棧足夠，無需手動增棧。
3. 記憶化避免重複計算，將指數級遞歸降為 O(RC)。