I have read some the top viewed solutions, they are brilliant. I am not trying to improve the solution of this question, but try to explain the solution in an easier manner.

Recap: you have 2 options, you can take 1 step, or 2 steps at once to climb N steps stair. How many distinct ways can you climb to the top?

If stair only has 1 step (N=1), we have 1 way to climb.

If stair is 2 steps (N=2), we have 2 ways to climb. Either take 1 step and then 1 step, or take 2 steps at once.

If stair is 3 steps (N=3), if the first step we take 1, we have 2 steps remain, and we have 2 ways to complete the remaining 2 steps(N=2 case); if the first step we take 2, we have 1 way to complete the remaining 1 step (N=1 case).

As you see, the fibonacci pattern is obvious.

N= number of steps

S1 first step take 1 step

S2 first step take 2 steps

N | S1 | S2 | Total ways = S1 + S2 |

1 | 1 | N/A | 1 |

2 | 1 | 1 | 2 |

3 | 2 | 1 | 3 |

4 | 3 | 2 | 5 |

5 | 5 | 3 | 8 |

6 | 8 | 5 | 13 |

Let' say, the stair is 5 steps. If the first step takes 1 step, 4 steps remain. As the table show, we have 5 ways to complete a 4 steps stair. If the first step takes 2 steps, 3 steps remain, and we have 3 ways to complete them. So, in total, we have 8 ways (5+3) to climb a 5 steps stair.

Thus, total ways is a fibonacci number (starts from N=3)

Now, what if you can take 1 step, 2 steps, or 3 steps at once. How many distinct ways can you climb to the top?

```
// in Java
static long climbStair(int n){
// we have 3 options, take 1,2,3 steps,
if (n <= 0) return 0;
if (n <= 1) return 1;
if (n <= 2) return 2;
if (n <= 3) return 4;
long[] solutions = new long[n+1];
// n indicates number of stairs.
// value is the number of distinct ways to climb the stair.
solutions[0]=0;
solutions[1]=1;
solutions[2]=2;
solutions[3]=4;
for (int i = 4; i < n+1; i++)
solutions[i] = solutions[i-1] + solutions[i-2] + solutions[i-3];
return solutions[n];
}
```

Note: my post and code are solely to explain the question.