My idea is simple:
  a[0]=1;
  a[1]=k-1;
  for i>=2 -> a[i]=(k-1)*a[i-1]+a[i-2];
  It should work.
  Here is my code:
  var n,k,i:longint;
    a,b,c:extended;

begin
     readln(n,k);
     a:=1;
     b:=k-1;
     for i:=2 to n do
        begin
             c:=(k-1)*(a+b);
             a:=b;
             b:=c;
         end;
     writeln(c:0:0);
end.

No, your 'dimamic program' shouldn't 'word' because you have to use big numbers...


Edited by author 23.03.2005 06:42