# Explanation of the problem

• 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.