提供一个想到的解决N个盘K个塔的汉诺塔问题的高效动规算法:以本题中四塔为例:
设f[i]表示移动i个盘子(在4塔下)的最少步数;
d[i]表示移动i个盘子(在3塔下)的最少步数.
若有n个盘需要移动,则从1~n-1枚举i,f[n]=min{2*f[i]+d[n-i]}
上述方程可以这样想到:当有i个盘子在四塔下被移动到一个柱子之后,剩下n-i个盘子可看作在除了前i个盘子所占据的一个柱子外的剩余3个柱子下移动,移完后在把前i个盘子移回到这n-i个盘子上来.故有2*f[i]+d[n-i].
而且该方法可以推广至N盘K塔移动,只需要一直往回递归到三塔.