题目链接:(链接)
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. 迭代：f(n) = f(n - 1) + f(n - 2)
1 class Solution { 2 public: 3 // 斐波那契数列, f(n) = f(n - 1) + f(n - 2) 4 int climbStairs(int n) { 5 if (n <= 1) { 6 return 1; 7 } 8 9 int a = 1, b = 1; 10 for (int i = 2; i <= n; ++i) { 11 int tmp = b; 12 b = a + b; 13 a = tmp; 14 } 15 16 return b; 17 } 18 };
2. 斐波那契额公式
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 };
原文：http://www.cnblogs.com/skycore/p/4872362.html