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楼的走法是第n-1楼走一步或者n-2楼走两步，所以有公式f(n)=f(n-1)+f(n-2)。就是斐波那契数列。
这种有规律的题有个共同解法，建立一个数组或vector记录每一个解，很好理解，不过空间复杂度为O(n)。
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 vector<int> f(n+1,0); 5 f[1]=1; 6 f[2]=2; 7 for(int i=3;i<=n;i++) 8 { 9 f[i]=f[i-2]+f[i-1]; 10 } 11 return f[n]; 12 } 13 };
使用迭代可以将空间复杂度降为O(1)。
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 vector<int> f(n+1,0); 5 int pre = 0; 6 int cur =1; 7 for(int i=1;i<=n;i++) 8 { 9 int temp = cur; 10 cur = cur+pre; 11 pre = temp; 12 } 13 return cur; 14 } 15 };
原文：http://www.cnblogs.com/Sean-le/p/4787699.html