爬楼梯
WangScaler: 一个用心创作的作者。声明：才疏学浅，如有错误，恳请指正。
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
初步分析
其实爬楼梯这个题很常见，可能数学找规律也做过。
- 爬第一阶台阶的方法只有一种。爬1个台阶，共1个方法。
- 爬第二个台阶的方法有两种。爬1+1个台阶或者爬2个台阶，共2个方法。
- 爬第三个台阶的方法。有1+1+1个台阶或者1+2个台阶或者2+1个台阶，共3个方法。
- 爬第四个台阶的方法。有1+1+1+1个台阶或者1+2+1个台阶或者1+1+2个台阶或者2+1+1个台阶或者2+2个台阶，共5个方法
- .....
- 总结下去，你会发现。f(3)=f(1)+f(2)=1+2=3。f(4)=f(3)+f(2)=3+2=5。
public static int climbStairs(int n) {
if(n==1||n==2){
return n;
}
return climbStairs(n-1)+climbStairs(n-2);
}使用递归轻松实现。但是时间复杂度O(2^n)比较高。比如我们要算10级台阶，需要算九级台阶和八级台阶的个数。那么计算九级台阶的时候其实也会算八级台阶以及之前的台阶的个数，算完之后再去算八级台阶以及之前台阶的个数就是重复性操作。也就是算了两遍八级以及八级之前台阶的次数，那么我们能不能减少这个次数呢？
继续分析
既然要减少重复运算，那么必须要进行存储，存储之前计算过的台阶的值。
public static int climbStairs(int n) {
int [] data = new int[n+1];
return climb(n,data);
}
public static int climb(int n, int data[]){
if(data[n]>0){
return data[n];
}
if(n==1||n==2){
data[n]=n;
return n;
}
data[n] = climb(n-1,data)+climb(n-2,data);
return data[n];
}这样我们只需要计算n级台阶，每一级台阶的次数即可，将时间复杂度降到O(n)。
那么从这里可以看到，我们每次递归都得回到第一级台阶计算，用数组的空间复杂度比较高，那么我们从头往后推不就行了吗？
public static int climbStairs(int n) {
int first = 1;
int next = 2;
int model = 0;
if(n==1||n==2){
return n;
}
for (int i = 3; i < n ; i++) {
model = first;
first = next;
next = model+first;
}
return first+next;
}这里有三个遍量。看起来不好理解，但是有个经典的游戏，将一个杯子的红水倒入另一个带蓝水杯子。倒完之后蓝水(不融合，也不会上浮)在上边。这时候我们需要借助第三个杯子，也就是三个变量中的model。剩下两个变量也很容易理解。f(3)时，first是1，next是2。那么f(4)是first就是2，next是1+2。这样空间复杂度就降低为O(1),只需要三个变量即可。
答案
其实上边的这个公式就是著名的斐波那契数列，也就是斐波那契数列。他的特征方程
求出x1和x2带入通解就得到下边的公式。
我们把这个公式转换成代码即可
public int climbStairs(int n) {
double sqrt5 = Math.sqrt(5);
double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
return (int) Math.round(fibn / sqrt5);
}总结
答案中的数学公式，各位还会吗？这是初中还是高中的知识？不会的可以考虑考虑是否应该回去重学了。都还给老师了可不行。答案中还有个矩阵快速幂，建议大家去研究研究。今天先到此为止了。
都来了，点个赞再走呗！关注WangScaler，祝你升职、加薪、不提桶！
