题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

（详情请见leetcode70）

动态规划

一开始用递归写，然后超时了...

随后开了大小为n的数组，后来发现没有必要，只需要三个整型...

大致思路：

在第 n 级台阶上的人，一定是从第 n-1 或第 n-2 级台阶迈上来的

由此可以列出状态转移方程

边界条件是，

推荐的写法是利用滚动数组思想

接下来是从答案抄来的代码

复杂度分析

时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。

空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。

矩阵快速幂

是的，这种题对于大神来讲，是用来秀肌肉的orzorzorz

官方给出的答案里说，随着n的增大，时间复杂度会以O(n)增长

所以我们试图把时间复杂度降至O(logn)

利用小学二年级知识——矩阵乘法，推导出下面神奇的递推式

然后：

定义矩阵

问题变成了求解矩阵M的n次方问题

普通求法时间复杂度为O(n)，为了降低时间复杂度

使用魔法快速幂加速n次方的求解

（快速幂视频友情链接）

直接上代码...

纳尼(⊙o⊙)？这是什么......

好的......中间那个函数是取矩阵M的快速幂用的

相当于把n二进制形式有1的位数取出，通过M不断做2次方次方（？）

求解出最终的M的n次方

具体可以看上面那个视频

那么，神魔情况下会用快速幂呢？

需要用到高等数学微分方程和线性代数的知识！orz

复杂度分析

时间复杂度：同快速幂，O(logn)。

空间复杂度：O(1)。

通项公式

不知道大佬们有没有看出来，这个递推式恰好是斐波那契数列

所以我们可以站在巨人的肩膀上

直接用公式求第n项！

（推导过程需要用到线性代数知识！可以前往leetcode70答案区看视频，一时半会我也说不清楚orz）

公式：

代码

打表法

找个层数在50左右的楼，走一走，数一数，既锻炼了身体，也增强了脑力！

写在最后

只有不停奔跑，才能勉强停在原地！