杭電 1207 漢諾塔 II：四柱最優移動 DP 遞推解法

含義：將 n 個盤子分為兩組——
① 先用四柱最優法將最小的 n-k 個盤子移到輔助柱（dp[n-k] 步）；
② 剩餘 k 個大盤子用三柱經典法移到目標柱（2^k - 1 步）；
③ 再用四柱最優法將 n-k 個小盤子疊上去（dp[n-k] 步）。
總步數 = 2·dp[n-k] + 2^k - 1。枚舉 k 取最小值。

DP 邊界與計算順序

• dp[1]=1, dp[2]=3, dp[3]=5, dp[4]=9（可手動驗證）。
• 遞推從 5 到 64 順推，內層枚舉 k=2..i/2（對稱性，k 超過一半等價）。
• 用 unsigned long long (__int64) 存儲，dp[64] < 2^64。

完整 C++ 代碼

#include 
using namespace std;
using u64 = unsigned long long;

u64 dp[65];
u64 pow2[65];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    pow2[0] = 1;
    for(int i=1;i<=64;++i) pow2[i] = pow2[i-1] << 1;

    dp[1]=1; dp[2]=3; dp[3]=5; dp[4]=9;
    for(int i=5;i<=64;++i) {
        u64 best = 2*dp[i-1] + 1;  // k=1
        for(int k=2;k<=i/2;++k) {
            u64 cur = 2*dp[i-k] + pow2[k] - 1;
            if(cur < best) best = cur;
        }
        dp[i] = best;
    }

    int n;
    while(cin >> n) {
        cout << dp[n] << '\n';
    }
    return 0;
}

樣例驗證

複雜度

• 預計算：O(64²) ≈ 4000 次運算，瞬間完成。
• 查詢：O(1)。

數學背景

此即著名的 Reve's Puzzle（四柱漢諾塔），最優解於 2014 年由 Thierry Bousch 證明 Frame-Stewart 算法確為最優。本題 n≤64 直接 DP 表查詢即可。

常見錯誤

• 內層枚舉 k 範圍寫錯（應 2..i/2 或 1..i-1 配合對稱剪枝）。
• 用 int/long 導致溢位（dp[64] ≈ 1.8e12 需 64 位）。
• 未預計算 2^k 反覆 pow() 產生浮點誤差。