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?

**Thoughts:**

This is just Fibonacci numbers. The number of distinct ways for steps are the sum of distinct ways for (because we can move 1 step first, then move the rest steps) and distinct ways for (because we can move 2 steps first, there are two ways to do it: move 1 steps twice and move 2 steps once, the former is a duplicate for the case so we should eliminate).

**Code (Java):**

Recursive version:

public class Solution {
public int climbStairs(int n) {
if(n == 0 || n == 1)
return 1;
else
return climbStairs(n-1) + climbStairs(n-2);
}
}

**Code (Java):**

Iterative version:

public class Solution {
public int climbStairs(int n) {
if(n == 0 || n == 1)
return 1;
int steps_n_2 = 1;
int steps_n_1 = 1;
for(int i = 2; i <= n; ++i) {
int steps_n = steps_n_1 + steps_n_2;
steps_n_2 = steps_n_1;
steps_n_1 = steps_n;
}
return steps_n_1;
}
}

### Like this:

Like Loading...

*Related*