设d[n]表示求解n盘3塔问题的最小步数

递推式：d[n] = 2 * d[n-1] + 1

 即把前n-1个盘子从A柱移到B柱，然后把A柱上剩的那一个盘子移动到C柱，最后把B柱上的那n-1个盘子移动到C柱上

设f[n]表示求解n盘4塔问题的最小步数

递推式：f[n] = min{2 * f[i] + d[n - i]}

初始化：f[1] = 1(一个盘子在4塔模式下移动到D柱需要1步)
先把i个盘子在4塔模式下移动到B柱，
然后把n-i个盘子在3塔模式下移动到D柱（因为不能覆盖到B柱上，就等于只剩下A、C、D柱可以用）
最后把i个盘子在4塔模式下移动到D柱
考虑所有可能的i取最小值，即得到上述递推公式

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int d[20], f[20];

int main() {
    d[1] = 1;
    for (int i = 2; i <= 12; i++)
        d[i] = 2 * d[i - 1] + 1;
    memset(f, 0x3f, sizeof(f));
    f[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]);
    for (int i = 1; i <= 12; i++)
        cout << f[i] << endl;
    return 0;
}