题目大意:
给出一个玩到一半的汉诺塔。叫你把所有的盘子归到任意一根针上,求最少步数。
由于结果很大,输出它和100000的模。
最基本的思路是动态规划,跟一般的汉诺塔问题类似
位于任意一个状态的汉诺塔。必然有位于最底层的最大的盘子。
最终的目的是把这个盘子移动到某根针上。
所以必然会出现的一个场景就是:
最大的盘子单独在一根针上,其他的盘子在另外一根针上
假设:
f(n, idx) = { 将初始状态下盘子 1~n 集中到第idx根针上所需要的最小步数 }
g(n) = { 将位于一根针上的盘子 1~n 移动到另外一根针所需要的最小步数 }
那么转移方程就是:
f(n, idx) = {
如果盘子n位于idx:f(n - 1, idx)
否则:f(n - 1, idx)
}
从普通的汉诺塔问题上可以得出:
g(n) = 2^n - 1