509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

1
2
3
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

1
2
3
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

1
2
3
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

  • 0 <= n <= 30

一维线性dp

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int fib(int n) {
        if (n == 0) return 0;
        int f[] = new int[n+1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 0; i < n-1; i++) {
            f[i+2] = f[i] + f[i+1];
        }
        return f[n];
    }
}

矩阵快速幂优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int fib(int n) {
        if (n == 0) return 0;
        int f[] = new int[n+1];
        f[0] = 0; f[1] = 1;
        // f[i+2]   = f[i+1] + f[i] = 1*f[i+1] + 1*f[i]
        // f[i+1]   = f[i+1]        = 1*f[i+1] + 0*f[i]
        // 所以: {f[i+2], f[i+1]} = [[1,1],[1,0]] * {f[i+1], f[i]}
        // 所以: {f[n], f[n-1]} = [[1,1],[1,0]]^(n-1) * {f[1], f[0]}
        // 假设矩阵快速幂结果是[[a,b],[c,d]，则f[n] = a*f[1]+b*f[0] = a
        long a[][] = {{1,1}, {1,0}};
        long res[][] = pow(a, n-1);
        return (int)res[0][0];
    }
    public long[][] pow(long matrix[][], long k) {
        long res[][] = new long[][]{{1,0},{0,1}};
        if (k == 0) return res;
        long newMatrix[][] = multi(matrix, matrix, 2);
        res = pow(newMatrix, k/2);
        if (k % 2 == 1) {
            res = multi(res, matrix, 2);
        }
        return res;
    }
    private long[][] multi(long a[][], long b[][], int n) {
        long res[][] = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    res[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return res;
    }
}