描述
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?
Note: Given n will be a positive integer.
分析
设 f (n) 表示爬 n 阶楼梯的不同方法数，为了爬到第 n 阶楼梯，有两个选择: • 从第n−1阶前进1步; • 从第n−1阶前进2步; 这是一个斐波那契数列。 方法 1：递归，太慢; 方法 2：迭代，也可以看作动态规划。 方法3：数学公式。斐波那契数列的通项公式为
an=15‾‾√⎡⎣⎢⎢(1+5‾‾√2)n−(1−5‾‾√2)n⎤⎦⎥⎥代码
// 迭代，时间复杂度 O(n)，空间复杂度 O(1) class Solution { public: int climbStairs(int n) { int prev = 0; int cur = 1; for (int i = 1; i <= n; ++i) { int tmp = cur; cur += prev; prev = tmp; } return cur; } }; // 数学公式，时间复杂度O(1)，空间复杂度O(1) class Solution { public: int climbStairs(int n) { const double s = sqrt(5); return floor((pow((1+s)/2, n+1) - pow((1-s)/2, n+1)) / s ); } };