线性递推 首先我们来看一下基本的Hanoi塔问题有个盘子,我们的目标是将起点柱上的盘子,借助过渡柱移到目标柱上去。其中大盘子不能压在小盘子上,一次只能移动个盘子。 我们来一步一步思考: 如果只有个盘子,那么我们只需要将这个盘子移到上去 如果有个盘子,那么就将小盘字移到上,再把大盘子移到上,再把小盘子移到大盘子上 如果移动的盘子数为,那么像上图那样考虑: 我们想要移蓝色盘子,就需要把它上面的盘子全部移到过渡柱(这里不一定是,下同)上去 然后再把前个盘子移到目标上所以,我们得出结论,对于移动第个盘子的步数,只与移动第个盘子所需步数有关 这里设为移动个盘子所需的步数。那么将前i-1个盘子移...