NYC 712 探尋寶藏：雙路徑 DP (四維/三維優化) 完整解析

題目模型

M×N 迷宮，左上角 (1,1) 走到右下角 (M,N) 再原路不回頭返回。去程只能↓/→，回程只能↑/←，每個格子寶物只能撿一次。最大化總價值。

關鍵轉化：兩人同步前進

「去程 + 回程不重疊」等價於「兩人同時從 (1,1) 走到 (M,N)，路徑不相交 (除端點)」。因為步數相同，可用步數 k = i + j - 2 關聯兩人坐標。

狀態定義

• 四維 DP：dp[i1][j1][i2][j2] — 兩人位置，冗余度高
• 三維優化：dp[k][i1][i2] — k 步後，人1在第 i1 行，人2在第 i2 行，列推導 j1 = k - i1 + 2, j2 = k - i2 + 2

轉移方程

每人有↓/→兩種選擇，共 4 種組合：

// 三維版本
for (int k = 1; k <= M+N-2; ++k) {
    for (int i1 = 1; i1 <= M; ++i1) {
        int j1 = k - i1 + 2;
        if (j1 < 1 || j1 > N) continue;
        for (int i2 = i1+1; i2 <= M; ++i2) {  // 強制 i1 < i2 避免重疊
            int j2 = k - i2 + 2;
            if (j2 < 1 || j2 > N) continue;
            
            int val = map[i1][j1] + map[i2][j2];
            dp[k][i1][i2] = max({
                dp[k-1][i1-1][i2-1],  // 都向下
                dp[k-1][i1-1][i2],    // 人1下，人2右
                dp[k-1][i1][i2-1],    // 人1右，人2下
                dp[k-1][i1][i2]       // 都向右
            }) + val;
        }
    }
}

初始化與答案

• dp[0][1][1] = map[1][1] (起點重合只算一次)
• 終點 (M,N) 同理只算一次
• 答案：max(dp[K-1][M][M-1], dp[K-1][M-1][M]) + map[M][N]，K = M+N-2

完整 AC 代碼 (三維優化版)

#include 
using namespace std;

int map[55][55];
int dp[110][55][55];  // k up to 100, M,N up to 50

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int M, N; scanf("%d%d", &M, &N);
        memset(map, 0, sizeof(map));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= M; ++i)
            for (int j = 1; j <= N; ++j)
                scanf("%d", &map[i][j]);
        
        int K = M + N - 2;
        dp[0][1][1] = map[1][1];
        
        for (int k = 1; k <= K; ++k) {
            for (int i1 = 1; i1 <= M; ++i1) {
                int j1 = k - i1 + 2;
                if (j1 < 1 || j1 > N) continue;
                for (int i2 = i1+1; i2 <= M; ++i2) {
                    int j2 = k - i2 + 2;
                    if (j2 < 1 || j2 > N) continue;
                    
                    int val = map[i1][j1] + map[i2][j2];
                    dp[k][i1][i2] = max({
                        dp[k-1][i1-1][i2-1],
                        dp[k-1][i1-1][i2],
                        dp[k-1][i1][i2-1],
                        dp[k-1][i1][i2]
                    }) + val;
                }
            }
        }
        
        int ans = max(dp[K-1][M][M-1], dp[K-1][M-1][M]) + map[M][N];
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 狀態數：O(K × M²) ≈ O((M+N) × M²)，M,N ≤ 50 → 約 25 萬狀態
• 轉移：O(1) 四個來源取最大
• 總時間：O(M²N + MN²)，空間 O((M+N) × M²) 可滾動數組優化至 O(M²)

四維到三維優化原理

利用 i1 + j1 = i2 + j2 = k + 2 這一不變量，消除一維。同理可推廣到三維網格雙路徑問題。