Hi
I very enjoy from this little solution for problem 1009:
here is it (dynamic):

var
  n,k,i               :byte;
  p1,p2,p3            :longint;
begin
  read(n,k);
  p2:=1; p1:=k;
  for i:=1 to n-2 do begin
    p3:=p1;
    p1:=(k-1)*(p1+p2);
    p2:=p3;
  end;
  writeln((k-1)*p1);
end.

isn`t it beauty?