首先回顾一下经典汉诺塔，我们设f[i]表示放好i个盘的最少步数。 先思考有两个盘子，我们把1盘放到B柱，然后把2盘放到C柱，最后把1盘放到C柱。 那么三个盘子就是先执行一遍同样的操作，发现B柱空了。干脆把B柱当作C柱，那么直接把3盘移到B柱上。 发现了什么？又变成了两个盘子的情况？！ 以此类推，i个盘子其实是把执行一次i-1时的步骤，把i盘放到空柱上，最后把剩下i-1个盘子放到i盘所在的柱上。 那么递推式显而易见f[i]=f[i-1]+1+f[i-1]=2f[i-1]+1。 思考有4根柱子，我们设ff[i]表示放好i个盘的最少步数。 一样思考，我们假设已经放了j（j<i）个盘子到k柱，这时，剩下的是啥？ So easy！i-j个盘子和3个柱子。。。？！ 然后呢？j个盘子和4个柱子 那么递推式又双显而易见ff[i]=min{ff[j]+f[i-j]+ff[j]}=min{2ff[j]+f[i-j]}(1<=j<i) 初始化（可以不写）：f[1]=1;ff[1]=1; 结束了，我用的f[0][i]代替f[i]，用f[1][i]代替ff[i]。

原文链接：https://blog.csdn.net/YIERsRP/article/details/81318428

#include<bits/stdc++.h>
 
using namespace std;
 
int f[5][25],n=12;
 
int main()
{
	for(int i=1;i<=n;i++)
	  f[0][i]=0,f[1][i]=2147364847;
	f[0][1]=1;f[1][1]=1;
	for(int i=1;i<=n;i++)
	  f[0][i]=2*f[0][i-1]+1;
	for(int i=2;i<=n;i++)
	  for(int j=1;j<i;j++)
	    f[1][i]=min(f[1][i],2*f[1][j]+f[0][i-j]);
	for(int i=1;i<=n;i++)
	  printf("%d\n",f[1][i]);
	return 0;
}