考虑 $n$ 盘 $3$ 塔的汉诺塔问题，令 $d_i$ 表示 $i$ 盘 $3$ 塔问题的步数。我们考虑先将 $i - 1$ 个盘子从 $A$ 柱放到 $B$ 柱，再把剩下的一个盘子放到 $C$ 柱，最后再把 $B$ 柱上的 $i - 1$ 个盘子放到 $C$ 柱上。

通过以上步骤，可以写出递推式 $d_i = 2 \times d_{i - 1} + 1$

接着考虑 $4$ 塔问题。令 $f_i$ 表示 $i$ 盘 $4$ 塔问题的步数。

我们可以先将 $j$ 个盘子从 $A$ 移到 $B$，剩下的 $n - j$ 个盘子做 $3$ 塔问题，从 $A$ 移到 $D$，最后再把 $B$ 柱上的 $j$ 个盘子做 $4$ 塔问题，移到 $D$ 上。

类似的，我们可以写出递推式 $f_i = \underset{1 \leq j < i}\min(2 \times f_{j} + d_{n - j})$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int n, f[N], d[N];
int main() {
    scanf("%d", &n);

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

    for (int i = 1; i <= 12; i ++)
        cout << f[i] << endl;
    return 0;
}