剑指Offer10- I. 斐波那契数列

题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

提示：

0 <= n <= 100

JAVA代码

一、递归方法（超出时间限制）

class Solution {
public int fib(int n) {
if(n0){
return 0;
}
if(n1){
return 1;
}
return fib(n-1)+fib(n-2);
}
}

二、数组辅助方法（动态规划dp）

class Solution {
    
    public int fib(int n) {
    
        final int MOD = 1000000007;
        int[] result = new int[100000];
        result[0] = 0;
        result[1] = 1;
        for(int i = 2;i<=n;i++){
    
            result[i] = (result[i-1]+result[i-2])%MOD;
        }
        return result[n];
    }
}

无需数组辅助方法（动态规划dp）

也可以像官方一样，不使用数组赋值，直接进行计算也是可以的。

class Solution {
    
    public int fib(int n) {
    
        final int MOD = 1000000007;
        if(n==0||n==1) return n;
        int num1 = 0,num2 =0,sum = 1;
        for(int i = 2;i<=n;i++){
    
            num1 = num2;
            num2 = sum;
            sum = (num1 + num2) % MOD;
        }
        return sum;
    }
}

官方方法：矩阵快速幂

算法设计思想：

class Solution {
    
    static final int MOD = 1000000007;

    public int fib(int n) {
    
        if (n < 2) {
    
            return n;
        }
        int[][] q = {
    {
    1, 1}, {
    1, 0}};
        int[][] res = pow(q, n - 1);
        return res[0][0];
    }
    
	//矩阵的n次幂乘
    public int[][] pow(int[][] a, int n) {
    
    	//初始化为单位矩阵，存储计算结果
        int[][] ret = {
    {
    1, 0}, {
    0, 1}};
        //偶数位我们直接计算a*a,这样就相当于规模减半
        //有奇数位时，我们将提取保存好的res与奇数位相乘。->奇数位*偶数次幂乘
        //这部分比较抽象，可以记住幂次相乘可以这样减少算法规模
        while (n > 0) {
    
        	//判断是否为奇数 n%2==1
            if ((n & 1) == 1) {
    
                ret = multiply(ret, a);
            }
            //相当于n = n/2
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }
    
	//两个二维矩阵相乘方法
    public int[][] multiply(int[][] a, int[][] b) {
    
    	//存放相乘后的结果
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
    
            for (int j = 0; j < 2; j++) {
    
                c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % MOD);
            }
        }
        return c;
    }
}

时间复杂度O(logn),空间复杂度O(1)

总结：矩阵快速幂
矩阵快速幂：即矩阵的n次幂快速乘法
总结工具类：套用到任何一个矩阵的n次幂求解中

	//矩阵的n次幂乘（n次幂相乘都可以套用这个思路）
    public int[][] pow(int[][] a, int n) {
    
    	//初始化为单位矩阵，存储计算结果
        int[][] ret = {
    {
    1, 0}, {
    0, 1}};
        //偶数位我们直接计算a*a,这样就相当于规模减半
        //有奇数位时，我们将提取保存好的res与奇数位相乘。->奇数位*偶数次幂乘
        //这部分比较抽象，可以记住幂次相乘可以这样减少算法规模
        while (n > 0) {
    
        	//判断是否为奇数 n%2==1
            if ((n & 1) == 1) {
    
                ret = multiply(ret, a);
            }
            //相当于n = n/2
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }
    
	//两个二维矩阵相乘方法
    public int[][] multiply(int[][] a, int[][] b) {
    
    	//存放相乘后的结果
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
    
            for (int j = 0; j < 2; j++) {
    
                c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % MOD);
            }
        }
        return c;
    }