HDU 5092：DP 求矩陣縱向最小路徑和及路徑輸出

題目大意

給定 m × n 矩陣，從第一行走到最後一行，每步可向下、左下、右下三個方向移動（即第 i 行選列 j，第 i+1 行可選 j-1, j, j+1）。求路徑權值和最小，並輸出路徑（列索引）。若多解，輸出字典序最大（即盡量靠右）的路徑。

DP 狀態定義

• dp[i][j]：從第 i 行第 j 列出發，走到最後一行的最小權值和
• path[i][j]：在 (i,j) 處做出最優決策時，下一行選擇的列

遞推方程（自底向上）

// 初始化最後一行
for j = 1..n: dp[m][j] = a[m][j], path[m][j] = j;

// 從倒數第二行向上遞推
for i = m-1 down to 1:
    for j = 1..n:
        dp[i][j] = dp[i+1][j] + a[i][j];
        path[i][j] = j;
        // 左下
        if (j-1 >= 1 && dp[i+1][j-1] + a[i][j] < dp[i][j]) {
            dp[i][j] = dp[i+1][j-1] + a[i][j];
            path[i][j] = j-1;
        }
        // 右下：注意 <= 保證靠右優先
        if (j+1 <= n && dp[i+1][j+1] + a[i][j] <= dp[i][j]) {
            dp[i][j] = dp[i+1][j+1] + a[i][j];
            path[i][j] = j+1;
        }

答案提取與路徑回溯

// 找第一行最小值，靠右優先（<=）
int minVal = INF, startCol = 1;
for j = 1..n:
    if (dp[1][j] <= minVal) { minVal = dp[1][j]; startCol = j; }

// 輸出路徑
cout << startCol;
int cur = startCol;
for i = 1..m-1:
    cur = path[i][cur];
    cout << ' ' << cur;
cout << endl;

完整代碼

#include 
using namespace std;
const int INF = 0x3f3f3f3f;
int a[110][110], dp[110][110], path[110][110];

int main() {
    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        int m, n; cin >> m >> n;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                cin >> a[i][j];

        // 初始化
        for (int j = 1; j <= n; ++j) {
            dp[m][j] = a[m][j];
            path[m][j] = j;
        }

        // DP
        for (int i = m-1; i >= 1; --i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = dp[i+1][j] + a[i][j];
                path[i][j] = j;
                if (j-1 >= 1 && dp[i+1][j-1] + a[i][j] < dp[i][j]) {
                    dp[i][j] = dp[i+1][j-1] + a[i][j];
                    path[i][j] = j-1;
                }
                if (j+1 <= n && dp[i+1][j+1] + a[i][j] <= dp[i][j]) {
                    dp[i][j] = dp[i+1][j+1] + a[i][j];
                    path[i][j] = j+1;
                }
            }
        }

        // 答案
        int ans = INF, col = 1;
        for (int j = 1; j <= n; ++j)
            if (dp[1][j] <= ans) { ans = dp[1][j]; col = j; }

        cout << "Case " << tc << "\n";
        cout << col;
        for (int i = 1; i < m; ++i) {
            col = path[i][col];
            cout << ' ' << col;
        }
        cout << "\n";
    }
    return 0;
}

關鍵細節

1. 靠右優先：右下轉移用 <=，答案選擇用 <=，保證字典序最大
2. 邊界檢查：j-1 >= 1、j+1 <= n
3. 空間優化：可滾動數組將空間降為 O(n)，但需保存 path 故通常保留二維
4. 輸出格式：Case X 換行，路徑空格分隔

複雜度

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

總結

經典的矩陣最小路徑和 DP。核心在於：自底向上遞推、記錄決策路徑、<= 處理靠右優先。模板通用性強，可擴展到「最大路徑和」「可移動方向擴展」「帶權邊」等變體。