## Number of distinct ways to climb a stair case (Climbing Stairs)

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 $n$ steps are the sum of distinct ways for $n-1$ (because we can move 1 step first, then move the rest $n - 1$ steps) and distinct ways for $n - 2$ (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 $n - 1$ 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;
}
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2dea61d8f91', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2dea61d8fc0',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2dea61d8fc2',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});