算法竞赛进阶指南之Strange Towers of Hanoi及其扩展内容

一、三个塔的问题。

基础内容参考博客：点我点我点我
（一个初始 一个目标 一个中转的问题！！）

首先：我们应该先从小汉诺塔入手。
一开始就考虑n个圆盘的话头脑会混乱，所以我们先缩小问题的规模，从3个圆盘开始思考。
即：暂时不考虑n个圆盘的问题，而是先找出3个圆盘的“3层汉诺塔”的解法。


通过递推
我们用x,y,z来分别代表起点柱，目标柱，中转柱。注意：x,y,z并不具体代表A,B,C柱子，在不同情况下会不固定的对应A,B,C中的某一个。

当n=0时：

• 不做任何操作
  当n>0时：
• 首先，将n-1个圆盘从A柱移到C柱（解出n-1层）
• 然后，将（n个中）最大的圆盘从A柱移到B柱
• 最后，将n-1个圆盘从C柱移到B柱（解出n-1层）
  由以上步骤可知：为了解出n层汉诺塔，要使用n-1层汉诺塔的解法。
  那么，我们可以用H(n)表示解出n层汉诺塔所需的最少移动次数。
  当n=0时，H(0)=0;
  当n=1时，H(1)=1;
  当n=2时，H(2)=H(1) + 1 + H(1) = 3;
  当n=3时，H(3)=H(2) + 1 + H(2) = 7;
  得到递推关系式：
  

二、四个塔 Strange Towers of Hanoi【DP】【递推】【枚举】 甚至n盘m个塔问题

题目大意：：

将汉诺塔中的3跟柱子改为4根，求盘子数为1到12时将全部盘子从第一根移动到最后一根需要移动的次数。

传统的3给汉诺塔的方程是：
f[i]=f[i?1]×2+1
那么我们要怎么利用它得到四个的呢？

思考：
传统的汉诺塔告诉我们，汉诺塔最重要的就是大问题化小问题，小问题直接解决，那么将四个塔转为三个塔。

题目链接：点我点我点我

其实很简单，如果我们从第一个汉诺塔中取出 i 个盘子到第二个汉诺塔中，并将这 i 个盘子固定不看，就只看第一个塔剩下的 n-i 个盘子和第三\第四个塔，这样就把四个汉诺塔问题转换成了三个。
这个步骤的状态表达 公式就是：
f[3][n-i]=2*f[3][n-i-1]+1 这里表示：三个塔状态下移动 n-i 个盘子到 第四个塔。
在代码里的表达为： d[i] = 2*d[i-1] +1 ;
我们将这第二个塔的i个盘子移到第四个塔中，问题，就解决问题了。

枚举不同的 i （0 <= i <=n ）所得的 f【n】 取min为 问题的解，即n个盘子从A塔移动到D塔的最小步骤。
状态表达方程为：
f[4] [n] = min(2*f [4] [i] + d[4] [n-i] , f[n])
在代码中的表达式为：f[n] = min(2*f[i] + d[n-i] , f[n]) ;

#include<bits/stdc++.h>
using namespace std;
long long f[15],d[15];   //f 数组是四个塔的解法 d 数组是3个塔的解法。 
//const int t=1e8;
int main(){
    for(int i = 1;i<=12;i++) {
    d[i] = 2*d[i-1]+1;	cout<<"d: "<<d[i]<<endl;}memset(f,0x3f,sizeof(f));//for(int i = 0;i <12;i++) cout<<f[i]<<endl;f[0] = 0;for(int n= 1; n<=12; n++){
    for(int i = 0; i<=n; i++){
    //cout<<n<<" "<<i<<" "<<f[n]<<" "<<f[i]<<" "<<d[n-i]<<endl;f[n] = min(2*f[i] + d[n-i],f[n]);  }}for(int i = 1;i <=12;i++) cout<<f[i]<<'\n'; return 0;
}

那么按照这个逻辑，如果是五个塔，那就先移j个盘到B塔，剩下的就又是四个塔的情况了。
避雷！！！：
memset函数 赋值最大值 一定要用 0x3f 来赋值！！！
最开始我定义的1e9去给内存赋值，结果赋值出来全是0； 我哭了。debug半天都没找到问题。

三、只能相邻移动的汉洛塔问题

相邻移动的 汉洛塔问题 就是每次会把除最大盘 来回移动三趟 最大盘相邻移动两步 即是移动一趟。
注意一趟： 即n=1时，f【1】 = 2;
所以递推式为：
f[n] = 3*f[n-1] + 2;

题目链接：点我点我点我