70.爬楼梯 LeetCode（看我，如果学了还没看懂的话）

参考链接1

参考链接2

参考链接3

如果这些还没看懂，看下面吧

思路

这是一道很无聊的题，评论里有一个列了45个case的值得我的反思，真正解决实际问题的时候，不一定需要华丽的算法，为了求快和稳定性，如果实际项目需要，这种45个case的最值得推荐！！！??

? 哈哈哈，扯远了，这45个case也是得先通过某种算法求出来的，那么具体什么算法当然值得推敲一下呀！！

emmm其实推敲他的解法还是很无聊的，因为所有的题都只是围绕着如何快速求斐波那契数列上了，这道题的题解随着n的增大是一个斐波那契数列

n=1 1

n=2 2

n=3 3

n=4 5

也就是说：
$$
f(1)=1,f(2)=2\
f(n)=f(n-1)+f(n-2)
$$

解法一：简单递归

时间复杂度：O(2ⁿ)

空间复杂度：O(n)

首先最先想到的显然是用递归去做：

f(int n){
    if(n==1) return 1;
    if(n==2) return 2;
    else return f(n)+f(n-1);
}

那个衡量一个算法,肯定是先看一下他的时间复杂度和空间复杂度，这个递归的空间复杂度和时间复杂度都是很高的，如何感性的体会一下呢？

转载侵删

时间复杂度不难看出，需要遍历所有的结点，才能求出f（5），这里的每个结点，都是实实在在的的跑了一个递归函数，需要时间的！！程序是按顺序逐条执行的！一共是2的n次方量级。

空间复杂度：我一开始没绕明白，以为这些结点都存在与内存中，其实这些结点都存在过，但是不是同时存在的！！！，在f5被调用的时候，由于f5 = f4 + f3，所以程序需要按顺序计算，，，f4和f3，但是f4在f3前面，所以先算f4。其实f4还有好长的路要走，所以暂时f3没有被运行。所以瞬时栈里最多存在红线这么多条程序然后f1退了f0上还是5个程序段。f2因此求出来了，程序其实卡在求f3的程序段里，这时候栈里只有三段了。。。。以此类推。所以空间复杂度最大是n。

解法二：临时数组

时间复杂度：O(n)

空间复杂度：O（1）

递归这种算法，很多时候的计算是不必要的！！！！（忽然明白了大黑书里的一句话）。比方说计算f5的时候需要计算f4和f3，这是实打实递归地去算。然而计算f4 需要计算f3 和f2 ，这里的f3 又重新计算了一遍，也就是按照递归的办法，一层层算的！很是麻烦呀！！

其实细心的小伙伴很快就能看出来，下图。。。。

力扣上的图，，，，转载转载，侵删侵删；

可以放一个数组，每次计算完了，把结果放在数组里，再保留上一次数组里的最大值，就好啦

class Solution {
    public int climbStairs(int n) {
        int a = 1;
        int b = 0;
        int temp = 0;
        for(int i = 1;i<=n;i++){
            temp = a;
            a = a+b;
            b=temp;
        }
        return a;
    }
}

不难看出，计算f(n)的时间复杂度是n，只需要计算O（n）次

空间复杂度是O（1）

这个不难。。。。

解法三 矩阵快速幂

时间复杂度：O(lgn)

空间复杂度:O(1)

? 如果说一个算法的时间复杂度是O(n)已经相当不错了，那么这个解法是O（lgn）听起来是不是相当刺激呢??!!!

? 那这里涉及到一个新的名字就是快速幂，

快速幂

? 具体的就去百度一下吧！！！

我大概说一下：如果计算a的10次方

a*a*a*a*a*a*a*a*a*a*a

? 抛给计算机的就是9次乘法运算，这里没有开辟任何多余的空间

但是比方说前五个a连乘的结果被记录下来的话，令其为t

那么计算机就这么计算

a*a*a*a*a*t

? 也就是5次乘法计算就好啦（算不算以空间换时间呢 挺值的我感觉）

那么这5个a的连乘其实也可以按照这种方法继续细化下去，以减少计算乘法的次数

令 m=（a*a）

? 那就是

(a*a)*m*a*t 变成了4次计算

这里不难写出他的算法，本质上是一个二分

好了就介绍这些

那么问题来了，这个算法确实能以lgn的速度减少运算次数，但是我这个题是加法运算，跟乘法 和幂有什么关系呢？

这里就涉及到数学的魔法了。。根据力扣官方的讲解，特征方程这些就不说了。我忘记了，，，

实际上我只需要计算这个M的n次方就可以了呀，这里的（f0 = 0 ）

那不就是幂运算吗，n次方的幂运算可以变成lgn的时间复杂度，wow好特么惊奇，，，，

下边就是我按照官方给的写法写出来的代码（基本一模一样，但是我真的是自己凭感觉撸出来的）

（矩阵的乘法，和正常的乘法不是一样的，虽然矩阵的一次乘法运算要比数字的乘法运算复杂很多，需要算很多次乘法运算才能完成一次矩阵的乘法运算，但是当n足够大的时候，这个快速幂运算lgn的时间复杂度便十分牛掰了）

上代码，不多说了

class Solution {
    //主程序
    public int climbStairs(int n) {
        int[][] div = new int[][]{{1,1},{1,0}};
        int[][] res = pow(div,n);//自定义了矩阵的幂运算pow，它按照快速幂的算法
        return res[0][0];

    }
    
	//这里是pow快速幂算法的核心，不难但是不好想通
    int[][] pow(int[][] div, int n){
        //作为一个存结果的变量，他是单位矩阵，因为它第一做乘法的时候，需要满足a*1=a
        int[][] eyes = new int[][]{{1,0},{0,1}};
  		//核心
        while(n>0){
            if((n&1)==1){
                eyes = multi(div,eyes);
            }
            n>>=1;
            div = multi(div,div);       
        }
   //解释一下核心，我总纠结于他的边界条件，就是最后是奇数还是偶数，但它这样的格式，使得无论如何，n都要从1变成零，如果最后一次是2 那么移位之后是1 然后变成0；如果是1 那么直接出结果，所以无论如何，`div = multi(div,div);`都被执行了！！！
   //核心也就是，是偶数n/=2，是基数就n--,那么无论怎么样都会进行了x个--，y个/=2，
        //在每个--后边都跟着一个  暂存结果*=原矩阵，
        //在每个/=2后边div都做  div*=div 也就是自平方（快速幂的根源）
   //所以完全合理呀一点也不差 
     
    return eyes;
    }  
    
//这是矩阵乘法的函数，很简单，任何一个学过编程的人都能写出来。不注释了。。。
    int[][] multi(int[][] a, int[][] b){
            int[][] res = new int[2][2];

            for(int i=0;i<2;i++){
                for(int j =0;j<2;j++){
                    res[i][j] = a[i][0]*b[0][j]+a[i][1]*b[1][j];
                }
            }
   return res;
    } 

}

这里的快速幂算法的程序代码值得看明白，挺好玩，。。

哎一天啥也没干就做了两道中等题，课题组汇报耽误一天白天时间，我好慌，毕业论文咋办！！我还没搞呢，，研二了都，，，，55555
------------恢复内容结束------------