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阶或2阶，问爬到顶端一共有多少种方法
方法一：
利用二叉树的思想，对于n=3时有3种方法，有几个叶子节点便有几种方法
1 void climb( int remainder, int &way) 2 { 3 if(remainder==0 || remainder==1) 4 { 5 way++; 6 return; 7 } 8 9 climb(remainder-1, way); 10 climb(remainder-2, way); 11 return; 12 } 13 14 class Solution { 15 public: 16 int climbStairs(int n) { 17 int result=0; 18 climb(n, result); 19 return result; 20 } 21 };
但是这种方法对于n比较大时会超时，在测试用例中对于n=38就会TLE（Time Limit Exceed）。
方法二：
总结规律，通过以下数据，我们发现
way(1)=1
way(n) = way(n-1) + Fibonacci(n-1) n=2,3,4,5,6,....
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 int result=1; 5 int Fibonacci_0=0, Fibonacci_1=1, temp; 6 for(int i=1; i<n; i++) 7 { 8 result += Fibonacci_1; 9 temp = Fibonacci_1; 10 Fibonacci_1 = Fibonacci_0 + Fibonacci_1; 11 Fibonacci_0 = temp; 12 13 } 14 return result; 15 } 16 };
对于leetcode中所有的测试数据都可以通过
[LeetCode OJ]-Climbing Stairs,布布扣,bubuko.com
原文：http://www.cnblogs.com/Marrybe/p/3799097.html