LightOJ 1004 Monkey Banana Problem：菱形 DP 從底向上求最大香蕉數

問題描述

猴子從菱形數組頂部進入，每步只能向下移動到相鄰格子，吃掉該格香蕉。菱形由上半部（1 到 N 行，第 i 行 i 個數）和下半部（N-1 到 1 行）組成。求猴子能吃到的最大香蕉總數。

DP 狀態定義

將菱形展開為 \( 2N-1 \) 行陣列 a[row][col]。
定義 dp[j] 為從底部走到當前行第 j 個位置的最大香蕉數。
從底向上 分兩階段轉移：

階段 1：下半部（行號 N 到 2N-2）

行長度遞增，每個位置可從左下或右下轉移：

for i = 2N-2 down to N-1:
    d = 2N-1 - i  // 當前行長度
    dp[d-1] = dp[d-2] + a[i][d-1]        // 最右只能從左下來
    for j = d-2 down to 1:
        dp[j] = max(dp[j], dp[j-1]) + a[i][j]
    dp[0] = dp[0] + a[i][0]                // 最左只能從右下來

階段 2：上半部（行號 N-2 到 0）

行長度遞減，每個位置可從左下或右下轉移（注意索引對應）：

for i = N-2 down to 0:
    d = i + 1
    for j = 0 to d-1:
        dp[j] = max(dp[j], dp[j+1]) + a[i][j]

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
long long a[2*MAXN][MAXN], dp[MAXN];

long long solve(int n) {
    int len = 2*n - 1;
    memset(dp, 0, sizeof(dp));
    dp[0] = a[len-1][0];                    // 底部唯一點

    // 下半部
    for (int i = len-2, d = 2; i >= n-1; i--, d++) {
        dp[d-1] = dp[d-2] + a[i][d-1];
        for (int j = d-2; j > 0; j--)
            dp[j] = max(dp[j], dp[j-1]) + a[i][j];
        dp[0] += a[i][0];
    }
    // 上半部
    for (int i = n-2, d = n-1; i >= 0; i--, d--) {
        for (int j = 0; j < d; j++)
            dp[j] = max(dp[j], dp[j+1]) + a[i][j];
    }
    return dp[0];
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int n; scanf("%d", &n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= i; j++)
                scanf("%lld", &a[i][j]);
        for (int i = n-1, d = n; i >= 1; i--, d++)
            for (int j = 0; j < i; j++)
                scanf("%lld", &a[d][j]);
        printf("Case %d: %lld\n", cas, solve(n));
    }
    return 0;
}

關鍵點總結

• 菱形展開為一維 DP 數組，空間 \( O(N) \)。
• 下半部行長增、上半部行長減，轉移方向相反，下標極易出錯，需仔細對應。
• 樣例驗證：輸入 4 行菱形，輸出 63；輸入 2 行，輸出 5。

總結

本題是經典「三角形 DP」的變體——菱形疊加。核心技巧是 從底向上、壓縮狀態、分段處理行長變化。調試時務必打印中間 dp 數組，確保下標對應正確。