..
AcWing 96. 奇怪的汉诺塔
首先考虑 $n$ 个盘子 $3$ 座塔的经典 $Hanoi$ 问题。
设 $d[n]$ 表示求解该 $n$ 盘 $3$ 塔问题的最少步数，显然有 $d[n] = 2 * d[n - 1] + 1$。
- 即把前 $n - 1$ 个盘子从 $A$ 柱移动到 $B$ 柱。
- 然后把第 $n$ 个盘子从 $A$ 移动到 $C$ 柱。
- 最后把前 $n - 1$ 个盘子从 $B$ 柱移动到 $C$ 柱。
回到本题，设 $f[n]$ 表示求解 $n$ 盘 $4$ 塔问题的最小步数，则：
\[f[n] = \min \{ 2 * f[i] + d[n - 1] \}\]其中 $f[1] = 1$。
- 上式的含义是，先把 $i$ 个盘子在 $4$ 塔模式下移动到 $B$ 柱。
- 然后把 $n-i$ 个盘子在 $3$ 塔模式下移动到 $D$ 柱。
- 最后把 $i$ 个盘子在 $4$ 塔模式下移动 $D$ 柱。
- 考虑所有可能的 $i$ 取最小值，就得到了上述递推公式。
在时间复杂度可以接受的前提下，上述做法可以推广到 $n$ 盘 $m$ 塔的计算。
完整代码：奇怪的汉诺塔.cpp