https://www.acwing.com/problem/content/98/
先考虑三个柱子的汉诺塔问题，设d[i]表示在三个柱子都可以选时，把i个塔从一个柱子移动到另一个柱子的最小移动步数。首先把n-1个塔从A移动到B，然后把n从A移动到C，再把n-1个塔从B移动到C。
d[i]=2*d[i-1]+1
当有四个柱子时，情况稍微改变，设f[i]表示在四个柱子都可以选时，把i个塔从一个柱子移动到另一个柱子的最小移动步数，但是观察到实际上最底层的n-j个塔都是要从A到D的，而其中B和C之一必然要把顶层的塔全部放上才空出另一个塔给n-j中转（当然如果只有n一个的话是不需要中转的）。
所以先把j个塔在四个柱子的情况从A移动到B，然后ACD三个塔把n-j从A移动到D，再把j个塔在四个柱子的情况从B移动到D。
f[i]=min(f[i],2*f[j]+d[n-j])
貌似可以推广到更多柱子。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int d[13], f[13];
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
d[1] = 1;
for(int i = 2; i <= 12; ++i)
d[i] = 2 * d[i - 1] + 1;
f[1] = 1;
for(int i = 2; i <= 12; ++i) {
f[i] = 1e9;
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)
printf("%d\n", f[i]);
}