继续刷LeetCode 热题 HOT 100 的题目，并且在博客更新我的solutions。在csdn博客中我会尽量用文字解释清楚，相关Java代码大家可以前往我的个人博客jinhuaiyu.com中查看。
题目：爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶
   示例 2：
   输入：n = 3
   输出：3
   解释：有三种方法可以爬到楼顶。
3. 1 阶 + 1 阶 + 1 阶
4. 1 阶 + 2 阶
5. 2 阶 + 1 阶
   提示：1 <= n <= 45

solution 1：动态规划
这道题和前几道动态规划题（二维移动）也是一个思想，只不过这道题只向一个方向移动，但有两种移动方式。第n级台阶的爬法可以由前两级台阶的爬法决定，包括从第n-2级台阶一次爬两级上来，以及从第n-1级台阶爬一级上来。设第n级台阶的爬法为f(n)，状态转移方程为：
f(n)=f(n−1)+f(n−2)
我们可以通过迭代从第1级开始往上计算，利用动态规划记住前面每级台阶的爬法数量。f(0)=1,f(1)=1，f(2)=1+1=2……
我们可以不用O(n)空间来存储每级的爬法，因为每次计算只需要知道前两级的爬法，所以我们可以只用两个变量更新即可。如果不想把第1级台阶列为特殊处理，我们可以在最前面再引入一个0，f(1)=0+f(0)=1，f(2)=f0)+f(1)=2。

solution 2：矩阵快速幂
先介绍一下什么是快速幂，如果我们要求a^n，需要O(n) 的时间复杂度来把n个a相乘，但是我们可以利用快速幂在O(logn)时间复杂度内求出答案。每次将指数缩小一半，底数进行平方（相乘），结果不变：
a^n =(a²⁾(n/2)=(a*a)^(n/2)
当n一直除2到1或0时，共除了logn次（底为2），每次进行一次乘法运算，所以可以降低时间复杂度。对于奇数次幂，可以通过取出一位来和偶数次幂情况合并：

我们的方案一时间复杂度显然是O(n)，因为要从f(1)迭代计算到f(n)，我们是否可以利用快速幂，降低时间复杂度呢？
这个递推公式正是斐波那契数列：0，1，1，2，3……
关于齐次线性递推的思想大家可以去复习一下线性代数，这块我就不讲怎么能联想了，直接给出斐波那契数列的矩阵型递推公式：

迭代可得：

令
我们想得到f(n)，只需要对M进行快速幂即可，但是这里是矩阵的乘法，我们需要写一个方法定义矩阵相乘（很简单，这里不介绍了）。至此，我们就可以在O(logn)时间复杂度内求得结果了。

solution 3：通项公式
斐波那契数列的通项公式如下：

我们可以直接代入n进行浮点数计算，比如java有Math.sqrt和Math.pow来计算开方和幂，这种方法简单粗暴，但是浮点数可能会丢失精度。

Finally，带有详细注释的代码放在我的个人博客http://jinhuaiyu.com/leetcode-climbing-stairs/