1. The maximum number of total staircases is 500 but not
60!!!
2. Your program didn't generated correct answer. (eg. 0)

And, I don't think you can use DP here.

But it doesn't look like solution :)

> But it doesn't look like solution :)
What tricks aree you talking about? This problem is
extremely simple. Here's the source:

var TAB : array [0..500] of comp; n, i, j : longint;
begin
  read(n); fillchar(TAB, sizeof(TAB), 0); TAB[0] := 1;
  for i := 1 to n - 1 do
    for j := n - i downto 0 do TAB[j + i] := TAB[j + i] +
TAB[j]; writeln(TAB[n]:0:0);
end.

O? What's the trick?!
I'm curious about the trick, can you have a explain?

 What tricks ... Hall of Shame ones :))

Petko.