算法题：多柱汉诺塔最优算法

三柱汉诺塔

n 个盘子，3 根柱子，在一根柱子上从下往上按照大小顺序摞着。问从下面开始按大小顺序重新摆放在另一根柱子上的最小次数。规定：在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘

算法：

设 f(n) 为移动 n 个盘子的最小次数
要移动 n 个盘子，必将先移动上面 n - 1 个盘子，然后把最底下的盘子挪到目标柱子上，最后把上面 n - 1 个盘子挪上去
得出递推式 f(n) = 2 * f(n - 1) + 1;

四柱汉诺塔

设 f(n) 为四柱汉诺塔移动 n 个盘子的最小次数，g(n) 为三柱汉诺塔移动 n 个盘子的最小次数
要移动 n 个盘子，必将用先移动上面 k 个盘子，然后用三柱汉诺塔的算法移动下面 n - k 个盘子，最后再用四柱汉诺塔的算法移动上面 k 个盘子到上面
得出递推式 f(n) = f(k) + g(n - k) + f(k) = min{2 * f(k) + 2^(n - k) - 1}，其中 1 <= k <= n

n 柱汉诺塔

设 f(n) 为 M 柱汉诺塔移动 n 个盘子的最小次数，g(n) 为 M - 1 柱汉诺塔移动 n 个盘子的最小次数
同理，n 柱汉诺塔递推式为 f(n) = min{ 2 * f(k) + g(n - k)}，其中 1 <= k <= n