POJ 1958 Strange Towers of Hanoi：四柱漢諾塔線性 DP

遞推關係：Frame-Stewart 算法

最優策略（猜想已證）：將 n 個盤子分為上 k 個和下 n-k 個：

1. 用四柱將上 k 個從 A 移到 B（借用 C、D）：f(k) 步。
2. 用三柱將下 n-k 個從 A 移到 D（借用 C）：2^{n-k} - 1 步。
3. 用四柱將上 k 個從 B 移到 D（借用 A、C）：f(k) 步。

總步數：f(n) = min_{1≤k≤n} [ 2·f(k) + 2^{n-k} - 1 ]。
邊界：f(0)=0, f(1)=1。

動態規劃實現

遞歸 + 備忘錄 (Top-down)

int dp[20];
int Move(int n) {
    if (dp[n] != -1) return dp[n];
    int best = 1<<30;
    for (int k = 1; k <= n; k++) {
        best = min(best, 2*Move(n-k) + (1<

線性 DP (Bottom-up) —— 推薦
int dp[20];
int main() {
    for (int i = 0; i <= 13; i++) dp[i] = 1<<30;
    dp[0] = 0; dp[1] = 1;
    for (int i = 1; i <= 12; i++) {
        for (int k = 1; k <= i; k++) {
            dp[i] = min(dp[i], 2*dp[i-k] + (1<

結果表 (n=1..12)
1
3
5
9
13
17
25
33
41
49
65
81


關鍵點解析

1. 分割點 k 的含義
代碼中 k 為下層盤子數（用三柱移動的部分），上層為 n-k。

轉移：dp[n] = min( 2*dp[n-k] + 2^k - 1 )。

2. 三柱移動步數
g(k) = 2^k - 1，直接用位運算 (1< 計算。


3. 最優 k 的規律
經驗規律：k 取使 n-k 接近三角數的值。但 n≤12 直接枚舉即可。

4. 遞歸 vs 迭代

遞歸 + 備忘錄：代碼簡短，但有函數調用開銷。
迭代 DP：無遞歸深度限制，效率略高，更適合競程。


擴展：輸出具體移動序列
若需輸出移動步驟，需記錄每個 n 的最優 k，然後遞歸構造：
int best_k[20];

void solve(int n, char from, char aux1, char aux2, char to) {
    if (n == 0) return;
    int k = best_k[n];
    // 1. 上層 n-k 從 from 移到 aux1 (四柱)
    solve(n-k, from, to, aux2, aux1);
    // 2. 下層 k 從 from 移到 to (三柱)
    hanoi3(k, from, aux2, to);
    // 3. 上層 n-k 從 aux1 移到 to (四柱)
    solve(n-k, aux1, from, aux2, to);
}


總結
POJ 1958 是四柱漢諾塔 DP的入門經典。核心在於：

Frame-Stewart 遞推公式：f(n) = min_k [ 2f(n-k) + 2^k - 1 ]。
線性 DP 自底向上計算，O(n²) 極快。
三柱部分直接用 2^k - 1 公式。
n≤12 可直接預計算輸出。

此題展示了「分治 + DP」優化遞歸問題的典型思想，也是漢諾塔變體問題的基礎模型。