Poj1958 Strange Towers of Hanoi — 四汉诺塔及多汉诺塔的高效动规解法

Note: 本文最初于 2011年03月24日 星期四 22:08 在 hi.baidu.com/lydrainbowcat 发表。

提供一个想到的解决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塔移动，只需要一直往回递归到三塔。

Source Code

Problem: 1958		User: lydliyudong
Memory: 844K		Time: 16MS
Language: Pascal		Result: Accepted

• Source Code

var
 f,d:array[0..12]of longint;
 n,i,j:longint;
begin
 n:=12;
 d[1]:=1;
 for i:=2 to n do d[i]:=2*d[i-1]+1;
 fillchar(f,sizeof(f),127);
 f[1]:=1;
 for i:=2 to n do
  for j:=1 to i-1 do
   if 2*f[j]+d[i-j]<f[i] then
    f[i]:=2*f[j]+d[i-j];
 for i:=1 to n do writeln(f[i]);
end.

šš