百度之星 1004 Labyrinth — 迷宮最大金幣 DP 解法

問題描述

在 m × n 矩陣迷宮中，從左上角 (1,1) 出發，只能向上、下、右移動，不可重複經過同一格，終點為右上角 (1,m)。每格有金幣（可為負），初始金幣為 0，求走出迷宮時的最大金幣數。m, n ≤ 100，T < 200 組數據。

核心觀察

由於不能向左走，路徑按列推進。每一列內可上下移動，但不可回頭。這啟發我們按列進行 DP，並利用「單調隊列」或「雙向掃描」優化列內轉移。

狀態定義

dp[i][j]：到達第 j 列第 i 行的最大金幣數。

列內轉移優化

對於固定列 c，從上一列 c-1 轉移過來後，在本列內可向上或向下走。採用雙向掃描：

1. 向下掃描：temp = dp[i][c-1] + ma[i][c]，累加向下路徑值，更新 dp[j][c]。
2. 向上掃描：同理從下往上累加，取最大值。

這相當於在列內做「前綴最大值」與「後綴最大值」的結合，時間 O(n) 處理一列。

參考代碼 (C++)

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

const int INF = 0x3f3f3f3f;
const int MAXN = 110;
int dp[MAXN][MAXN];
int ma[MAXN][MAXN];
int n, m;

void DP(int c) {
    // 向下掃描
    for (int i = 1; i <= n; ++i) {
        int temp = dp[i][c-1] + ma[i][c];
        dp[i][c] = max(dp[i][c], temp);
        for (int j = i+1; j <= n; ++j) {
            temp += ma[j][c];
            dp[j][c] = max(dp[j][c], temp);
        }
    }
    // 向上掃描
    for (int i = n; i >= 1; --i) {
        int temp = dp[i][c-1] + ma[i][c];
        dp[i][c] = max(dp[i][c], temp);
        for (int j = i-1; j >= 1; --j) {
            temp += ma[j][c];
            dp[j][c] = max(dp[j][c], temp);
        }
    }
}

int main() {
    int t; cin >> t;
    int cas = 1;
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                scanf("%d", &ma[i][j]);
                dp[i][j] = -INF;
            }
        dp[1][1] = ma[1][1];
        for (int i = 2; i <= n; ++i) dp[i][1] = dp[i-1][1] + ma[i][1]; // 第一列只能向下
        for (int j = 2; j <= m; ++j) DP(j);
        printf("Case #%d:\n%d\n", cas++, dp[1][m]);
    }
    return 0;
}

複雜度分析

• 時間：O(T × n × m)，n,m ≤ 100，T < 200，極快。
• 空間：O(n × m)。

總結

本題關鍵在於發現「不可向左」限制導致的列 DP 結構，並用雙向掃描優化列內轉移，避免了 O(n²) 的枚舉。這是網格 DP 中常見的「列優化」技巧。