My algo is
------------------------------------
we take an array[-2..N]
then we do this:
A[-2]:=0
A[-1]:=1
for i:=1 to k do
  a[i]:=2^i

for i:=k to n do
  a[i]:=2*a[i-1]-a[i-2-k]
-------------------------------------
at the end we get a[n]-output number
-------------------------------------
certainly i used long arithmetic and my array is not such simple as in this example: it's only algo


Edited by author 19.03.2008 00:23

This algo isn't correct
instead
for i := 1 to k do a[i] := 2^i;
must be
for i := 0 to k do a[i] := 2^i;//may be runtime error
OR
a[0] = 1
for i := 1 to k do a[i] := a[i - 1] * 2;
its works nicely:)

Edited by author 23.04.2009 19:56

Special case -
k = 0 then answer is 1