Long Legged Larry

For 1-6 stairs, you can quickly figure out that there are 0,1,1,1,2,2 ways respectively to get there. Now, to get to the $n^\text{th}$ stair, he must have come from either stair $n-2$ , or $n-3$ (or $\frac n2$ if $n$ is even). So if $f(n)$ is the number of ways he can climb to n stairs, then for $n>6$ you can use this equation: $f(n) = f(n-3) + f(n-2)$ for odd $n$ , and $f(n) = f(n-3) + f(n-2) + f(n/2)$ for even $n$ . So, for $n=20$ , $f(n) =\boxed{174}.$

1
2
3
4
5
6
7
8

int N = 20;
int c[] = new int[N+1];
c[0] = 1; c[1] = 0; c[2] = 1;

for (int i = 3; i <= N; i++)
    c[i] = c[i-2] + c[i-3] + ((i > 6 && i%2 == 0) ? c[i/2] : 0);

System.out.println(c[N]);

Output:

1

174