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?
当n=1时，有1种方法，即直接走1步
当n=2时，有2方法：连续走2步，或直接走两步
对于n，设f(n)为总方法，则 f(n) = f(n-1)+f(n-2)
ps:f(n-1)即第一次走一步的走法，
f(n-2)即第一次走两步的走法
归回fibnacci问题解法：
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 if(n < 0) 5 return -1; 6 int res[] = {0,1}; 7 if(n<2) 8 return res[n]; 9 10 int fib1 = 0; 11 int fib2 = 1; 12 13 int result = 1; 14 15 for(int i = 1 ; i <= n ; i++){ 16 result = fib1 + fib2; 17 fib1 = fib2; 18 fib2 = result; 19 } 20 21 return result; 22 } 23 };
Climbing Stairs 爬楼梯问题，每次可以走1或2步，爬上n层楼梯总方法 （变相fibnacci）
原文：http://www.cnblogs.com/fanchangfa/p/4059079.html