奇怪的汉诺塔

汉诺塔问题，条件如下：

1、这里有 $A、B、C$ 和 $D$ 四座塔。

2、这里有 $n$ 个圆盘，$n$ 的数量是恒定的。

3、每个圆盘的尺寸都不相同。

4、所有的圆盘在开始时都堆叠在塔 $A$ 上，且圆盘尺寸从塔顶到塔底逐渐增大。

5、我们需要将所有的圆盘都从塔 $A$ 转移到塔 $D$ 上。

6、每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。

请你求出将所有圆盘从塔 $A$ 移动到塔 $D$，所需的最小移动次数是多少。

（三柱汉诺塔参考模型，注意 题中是四根柱子）

输入格式

没有输入

输出格式

对于每一个整数 nn，输出一个满足条件的最小移动次数，每个结果占一行。

数据范围

$1≤n≤12$

输入样例：

没有输入

输出样例：

参考输出样例

解析

汉诺塔经典问题，先推三塔公式 $d_i = d_{i - 1} \times 2 + 1$

假设只有三个盘子，最优的解法是先将最大的盘子放到第三根柱子上，然后剩下两个盘子再放到第三根柱子上，那么这样就变成了 两个盘子的问题，因为最大的盘子丝毫不影响剩下的盘子移动。即我们先将前两个盘子以两个盘子的最优步数放到第二根柱子上，然后将第三个盘子放到第三根柱子上，再将第二根柱子上的两个盘子以两个盘子的最优步数放到第三根柱子上，这样就达成了三根柱子三个盘子的最优步数，同理 $n$ 个盘子也是如此，所以得到公式 $d_i = d_{i - 1} \times 2 + 1$

推完三塔公式，就来推四塔公式，四塔唯一和三塔不同的是，假设有 $k$ 个盘子，第 $d$ （$0 ≤ d ＜ k)$ 个盘子（包括 $d$）以下的盘子是以三塔的方式移动，而第 $d$ 个盘子以上的盘子却是以四塔的方式移动，而四塔方式的最优步数却是由一共有 $d - 1$ 个盘子的最优步数推来的，那么代码就很好写了

a[1] = 1;
for (int i = 1; i <= 12; i++) {
    a[i] = a[i - 1] * 2 + 1;
}
    
memset(f, 0x3f, sizeof(f));
f[1] = 1;
for (int i = 1; i <= 12; i++) {
    for (int j = 1; j < i; j++) {
        f[i] = std::min(f[i], 2 * f[j] + a[i - j]);
    }
}

以下是总代码

#include <cstdio>
#include <cstring>
#include <iostream>

const int N = 15;
int a[N], f[N];

int main() {
    a[1] = 1;
    for (int i = 1; i <= 12; i++) {
        a[i] = a[i - 1] * 2 + 1;
    }
    
    memset(f, 0x3f, sizeof(f));
    f[1] = 1;
    for (int i = 1; i <= 12; i++) {
        for (int j = 1; j < i; j++) {
            f[i] = std::min(f[i], 2 * f[j] + a[i - j]);
        }
    }
    
    for (int i = 1; i <= 12; i++) {
        printf("%d\n", f[i]);
    } return 0;
}