HDU 2391 Filthy Rich：網格最大路徑和 DP

問題描述

給定 b×c 的網格，每個格子有值 s[i][j]。從 (0,0) 走到 (b-1, c-1)，每步只能向右、向下或向右下（即從左上三個方向轉移）。求路徑上數值之和的最大值。

DP 狀態與轉移

• w[i][j]：到達 (i,j) 的最大和。
• 初始化：w[0][0] = s[0][0]；第一行只能從左來 w[0][j] = w[0][j-1] + s[0][j]；第一列只能從上來 w[i][0] = w[i-1][0] + s[i][0]。
• 一般情況：w[i][j] = max(w[i-1][j-1], w[i-1][j], w[i][j-1]) + s[i][j]。

複雜度

• 時間：O(b·c)，b,c ≤ 1000，極快。
• 空間：O(b·c) 或滾動數組優化至 O(min(b,c))。

參考代碼（C++）

int show(int a, int b, int c) {
    int t = a > b ? a : b;
    return t > c ? t : c;
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int b, c; scanf("%d%d", &b, &c);
        for (int i = 0; i < b; i++)
            for (int j = 0; j < c; j++)
                scanf("%d", &s[i][j]);

        memset(w, 0, sizeof(w));
        for (int i = 0; i < b; i++) {
            for (int j = 0; j < c; j++) {
                if (i == 0) {
                    w[i][j] = (j == 0) ? s[i][j] : w[i][j-1] + s[i][j];
                } else if (j == 0) {
                    w[i][j] = w[i-1][j] + s[i][j];
                } else {
                    w[i][j] = show(w[i-1][j-1], w[i-1][j], w[i][j-1]) + s[i][j];
                }
            }
        }
        printf("Scenario #%d:\n%d\n\n", cas, w[b-1][c-1]);
    }
    return 0;
}

總結

經典二維 DP 入門題。狀態定義直觀，轉移只需取三個鄰居最大值。注意邊界初始化，輸出格式需符合題目要求（Scenario #k: 及空行）。