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?
思路：这道题是斐波那契数列的延伸。首先用最简单的递归的方法
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 if (n <= 3) return n; 5 return climbStairs(n - 1) + climbStairs(n - 2); 6 } 7 };
不出意料的超时了。替代递归的方法是用动态规划。
class Solution { public: int climbStairs(int n) { vector<int> res(n+1); res[0] = 1; res[1] = 1; for (int i = 2; i <= n; i++) { res[i] = res[i-1] + res[i-2]; } return res[n]; } };
时间复杂度降低了，接下来降低空间复杂度。用变量代替数组
class Solution { public: int climbStairs(int n) { if (n <= 3) return n; int f1 = 2; int f2 = 3; int f3 = 0; for (int i = 4; i <= n; ++i) { f3 = f2 + f1; f1 = f2; f2 = f3; } return f3; } };
最终的时间复杂度O(n),空间复杂度O(1)
原文：http://www.cnblogs.com/vincently/p/4122773.html