算法導論：鋼條切割問題動態規劃完整解析

問題描述

長度 n 鋼條，價格表 p_i (i=1..n)。切割方案使收益最大。切割位置在整數英寸處，共 2^{n-1} 種方案。

遞推關係

第一刀切在 k 位置：收益 = p_k + r_{n-k}。
r_n = max_{1≤k≤n} (p_k + r_{n-k})，r_0 = 0。

三種 DP 實現

1. 帶備忘錄自頂向下：遞歸 + 陣列記錄已解子問題。
2. 自底向上：按長度 1..n 遞推，無遞歸開銷。
3. 重構解：額外記錄 s[n] = 最優第一刀位置，回溯輸出切割方案。

代碼 (C++)

// 自底向上 + 重構解
int bottomUpCutRod(int p[], int n) {
    vector r(n+1, 0), s(n+1, 0);
    for (int j = 1; j <= n; j++) {
        int q = -1;
        for (int i = 1; i <= j; i++) {
            if (p[i] + r[j-i] > q) {
                q = p[i] + r[j-i];
                s[j] = i; // 記錄第一刀長度
            }
        }
        r[j] = q;
    }
    // 輸出切割方案
    while (n > 0) { cout << s[n] << ' '; n -= s[n]; }
    return r[n];
}

運行示例

價格表 p=[0,1,5,8,9,10,17,17,20,24,30] (長度 1..10)。
輸出每種長度最大收益及切割方案，如長度 10：收益 30，切割 10（不切）。