题目
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?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1.1 step + 1 step
2.2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1.1 step + 1 step + 1 step
2.1 step + 2 steps
3.2 steps + 1 step
解析
题目意思是比较好理解的，是一个正数n中，只有1和2两种累加，求解多少种方法，不妨先用数学推导一下。
n ways
1 1
2 2
3 3
4 5
...
n F(n)
当n=4时，其情况有
1,1,1,1
1,1,2
1,2,1
2,1,1
2,2
共5种情况
因此，F(n) = F(n-1) + F(n-2)，意义是，F(n)是由第n-1阶走1步和第n-2阶走2步上来，两种情况的累加。这是斐波那契数列。再编写代码就很简单了。
代码
int climbStairs(int n) {
if (n == 1 || n == 2)
return n;
int prior = 1, behind = 2, ways = 0;
for (int i = 3; i <= n; ++i) {
ways = prior + behind;
prior = behind;
behind = ways;
}
return ways;
}
n=1和n=2的情况直接返回n1和2。从3开始，设置prior为F(n-2)，behind为F(n-1)，依次赋值，最终得到ways方式数量。
