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 走一步 or 从 n - 2 走两步.
所以 f(n) = f(n - 1) + f (n - 2), 即斐波那契数列。可以迭代求解或者直接用通项公式。
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 vector <int> v(n + 1); 5 v[0] = 1; 6 v[1] = 1; 7 for (int i = 2; i <= n; ++i) { 8 v[i] = v[i - 1] + v[i - 2]; 9 } 10 return v[n]; 11 } 12 };
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 const double s = sqrt(5); 5 return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1))/s + 0.5); 6 } 7 };
【Leetcode】Climbing Stairs,布布扣,bubuko.com
原文：http://www.cnblogs.com/dengeven/p/3612506.html
