# Climbing Stairs

This problem is actaully asking you to generate the Fibonacci sequence. According to the problem statement. When you are getting to the th stair. You can at first get to the th stair and climb 1 stair to met the top, or, you can at first get to the th stair and then climb 2 stairs to the top. So the total ways to get the th stair equals to the sum of ways to get th and th stair. If we regard this problem as a Dynamic Programing problem, we have

We have , so it will be a Fibonacci sequence generated for .

public class ClimbingStairs {
public int climbStairs(int n) {
if (n < 2) return 1;

int a = 1;
int b = 1;
int c = 1;

for (int i = 2; i <= n; i++) {
c = b;
b = a + b;
a = c;
}

return b;
}
}