题目链接

http://poj.org/problem?id=1958

解题思路

三个的汉诺塔就不细说了，太基础了（还是细说了……）：
将n个盘子从A通过B移到C的方案数表示为tir[n]，完成这件事就得先把前n-1个盘子从A通过C移到B，方案数为tir[n-1]；再把第n个盘子从A直接移动到C，方案数为1；最后把B上的n-1个盘子通过A移到C，方案数为tir[n-1]。所以转移方程为tir[i]=tir[i-1]*2+1;
至于四塔，我们还是分析这个过程：
A，B，C，D四个塔，开始的i个盘子都在A塔上，我们先把前k个盘子在四塔模下移动到B，方案数为dp[k]；然后把i-k个盘子在三塔模式下移动到D，方案数为tir[i-k]；最后把k个盘子在四塔模式下移动到D，方案数为dp[k]。所以转移方程为dp[i]=min( 2 * dp[k]+tir[i-k] ) ，k从1到i。
说实话我有点疑惑，为什么三塔就可以n个盘子就能直接从n-1转移来，但是四塔就要从小于n的情况中和最小的转移来？百度不到，好像没人有和我一样的疑惑
我只能暂时理解到四塔问题中的第二步（将i-k个移动到D上）是与tir三塔问题有关的，而不同的k会产生不同的tir，四塔问题中的每种盘子数不同的情况都受tir的影响，所以要由最佳转移而来。

AC代码

#include<iostream>
#include<cstring>
#define ll long long

using namespace std;
const int N=20;

int dp[N],tir[N];

int main()
{
    memset(dp,0x3f,sizeof dp);cout<<(dp[1]=1)<<endl;//初始化并输出
    for(int i=1;i<=12;i++) tir[i]=2*tir[i-1]+1;//求三塔
    for(int i=2;i<=12;cout<<dp[i]<<endl,i++)//求完接着输出
    for(int k=1;k<=i;k++)
    dp[i]=min(dp[i],dp[k]+dp[k]+tir[i-k]);//转移方程
}