HDU 5092 DP 另解：自頂向下遞推與路徑記錄

題目回顧

同 HDU 5092：m × n 矩陣，從第一行走到最後一行，每步可移動到下一行的同列、左列、右列。求最小路徑和，輸出路徑（多解取靠右）。

自頂向下 DP 另解

狀態：dp[i][j] = 走到第 i 行第 j 列的最小權值和。
初始化：dp[1][j] = a[1][j]。
遞推（i = 2..m）：

for i = 2..m:
    for j = 1..n:
        dp[i][j] = dp[i-1][j] + a[i][j];
        pre[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];
            pre[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];
            pre[i][j] = j+1;
        }

答案提取

// 最後一行找最小值，靠右優先
int minVal = INF, col = 1;
for (int j = 1; j <= n; ++j)
    if (dp[m][j] <= minVal) { minVal = dp[m][j]; col = j; }

// 回溯路徑（從下往上）
vector path;
for (int i = m; i >= 1; --i) {
    path.push_back(col);
    col = pre[i][col];
}
reverse(path.begin(), path.end());
// 輸出

兩種 DP 方向對比

代碼精簡版

#include 
using namespace std;
const int INF = 0x3f3f3f3f;
int a[110][110], dp[110][110], pre[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[1][j] = a[1][j], pre[1][j] = j;

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

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

        cout << "Case " << tc << "\n";
        vector path;
        for (int i = m; i >= 1; --i) {
            path.push_back(col);
            col = pre[i][col];
        }
        reverse(path.begin(), path.end());
        for (int i = 0; i < path.size(); ++i) {
            if (i) cout << ' ';
            cout << path[i];
        }
        cout << "\n";
    }
    return 0;
}

總結

自頂向下與自底向上本質等價，選擇取決於個人習慣。關鍵點：初始化行、遞推方向、轉移來源、答案行、回溯邏輯 五者必須配套。靠右優先始終通過 <= 體現。兩種寫法熟練掌握，應對變體題更靈活。