世界真的很大 这不是一道题 汉诺塔问题的基本思想应该还是了然于心了 花了1个小时来思考汉诺塔问题的精髓，就是子结构的问题，用递归就很好解决了 但是在柱子很多的情况下，有可能子结构多样化，再指定最大的分散是否还是最优呢 来探讨一下这个神奇的印度玩意儿
给定n，m求n个盘子m个柱子的汉诺塔问题答案
两个整数n，m
答案
先来谈谈汉诺塔问题的普通版 中心思想是，先把n个盘子的上面n-1个挪到另一个盘子上，然后把最下面的一个盘子拿到最后一个柱子上，然后把另一个柱子的n-1个盘子挪到最后一个柱子上 由于第n个盘子比上面的所有盘子都大，上面的盘子在移动的过程中最后一个盘子对他们没有影响 于是乎可以看出第一步和第三步的本质相同，都是n-1个盘子的问题，这就是一个子问题了 于是可以递归求解 有一点要理解，这三个柱子其实是没有先后顺序的，如果m步能从1号柱子挪到3号柱子，那么同样也可以挪到2号柱子 当然我们也可以发现其实答案就是2^n-1，这个在递推的过程中也很好得到
来谈一下这个拓展版的汉诺伊问题 通过之前的例子可以看出，汉诺伊塔的本质大概就是分解同结构的子问题 对于每一个n和m，我们的思路都是一样的，类比之前的原版汉诺伊问题 我们先从n个盘子里面选i个利用m个柱子移动到一个柱子上，对于剩下的n-i个，没有一个可以放到这个柱子上面，那么就只剩下m-1个柱子了，问题就是用m-1个柱子把n-i个盘子挪到另一个柱子上。 然后把之前的i个柱子挪到那一根柱子上 第一步和第三部等价 由于在原版汉诺塔问题里面只有三个柱子，于是每次这个i的选择必须是n-1，因为两个柱子是无法移动1个以上的盘子的，所以子结构就被确定了 但是在多柱汉诺塔问题中，我们的选择就多样化了，不一定必须挪走n-1个，也可以是n-2个。。等等 对于这样的子结构的多样性，究竟哪一种选择最优呢？凭借推理，我们不得而知 但是使用类DP的方法，我们可以去枚举究竟采用哪一种子结构最优 令f（ij）表示i个盘子，j个柱子 那么f（ij）=min（2*f（kj）+f（i-K，j-1）） 于是乎可以用递推得到答案 复杂度n^3
