[数据结构与算法]LeetCode斐波那契/青蛙爬楼梯系列

今天做了一系列题目，发现很有趣，而且实现的方法很多，那就是著名的斐波那契问题，而斐波那契问题和爬楼梯问题很类似，只是初始条件不同，
斐波那契f(0) = 0,f(1) = 1 , f(2) = 1
青蛙爬楼梯 f(0) = 1, f(1) = 1 , f(2) = 2;

列出可以使用的算法

//1.递归(重复计算O(2^n) 超时)
//2.记忆化递归(O(n))
//3.动态规划
//4.动态规划优化(滚动数组) O(n)
//5.矩阵快速幂O（logn）
//6.记住通项公式O（1）

这是一个使用递归和动态规划的典型问题，如果直接使用递归，必然会超时，使用一个额外长度为n的数组可以将递归时间复杂度降为O(n)，但是还是不能满足，可以考虑动态规划，但是还是O(n),这时候就考验数学能力了，使用矩阵快速计算幂次的方法能把复杂度降为O(log n),甚至你可以直接记住斐波那契的通项公式，O(1)!!!

矩阵快速求幂法：记住{{1,1},{1,0}}这个矩阵

1.递归

public int climbStairs(int n) {
            int[] arr = new int[n];
            return climb(n , arr);
        }
        public int climb (int n , int[] arr){
            if (n == 1){
                return 1;
            }
            if (n == 2){
                return 2;
            }
            if (arr[n-1] > 0){
                return arr[n-1];
            }
            arr[n-1 ] = (climb(n-1,arr)+ climb(n-2,arr)) % MOD;
            return arr[n-1];
        }

2.动态规划：

public int climbStairs(int n){
            int p = 0 , q = 0 , r = 1;
            for(int i = 0 ; i < n ; i ++){
                p = q ; 
                q = r;
                r = (p+q) % MOD ;
            }
            return r;
        }

3.矩阵快速求幂

public int numWays(int n) {
        int[][] ans = {{1,1},{1,0}};
        int[][] res = pow(ans,n);
        return res[0][0];
    }
public int[][] pow(int[][] arr,int n){
        int[][] ans = new int[][]{{1,0},{0,1}};
        int[][] temp = arr;
        while (n > 0){
            if ((n & 1) == 1){
                ans = multiply(ans,temp);
            }
            n >>= 1;
            temp = multiply(temp,temp);
        }
        return ans;
    }

    public int[][] multiply(int[][] arr1, int[][] arr2){
        int[][] ans = new int[2][2];
        for(int i = 0; i < 2;i++){
            for (int j = 0 ; j < 2 ;j++){
                ans[i][j] = (int) (((long) arr1[i][0] * arr2[0][j] + (long) arr1[i][1] * arr2[1][j]) % MOD);
            }
        }
        return ans;
    }

4.通项公式

public int climbStairs(int n) {
            double sqrt5 = Math.sqrt(5);
            double ans = Math.pow((1 + sqrt5)/2,n+1) - Math.pow((1 - sqrt5)/2,n+1); // 斐波那契1，2，3，4个数分别为1，1，2，3
                                                                                    //而台阶问题1，2，3，4个数分别为1，2，3，5
            return (int)(ans / sqrt5);
        }

注意：
因为斐波那契和爬楼梯初始条件不一样，所以循环次数、计算次数有出入，带入初始值计算即可。