Problem: You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Thinking: this is a question reforms Fibonacci numbers. The reason is that consider we have n stairs, then there are two subproblems we can accomplish such task. One is take one step on this level, which leaves the rest n-1 stairs, or we can take 2 steps this level, which leaves that rest n-2 stairs.

Then this routine goes on and on until we have one stairs and no stairs, which both have only one way to climb. Therefore it is identical to Fibonacci numbers. For space complexity, use dynamic programming to solve it.

```
public class Solution {
public int climbStairs(int n) {
int i = 1;
int j = 1;
for (int x = 0; x < n - 1; x++) {
int temp = i + j;
i = j;
j = temp;
}
return j;
}
}
```

Advertisements