Dynamic programming - 509. Fibonacci number

1 Title Description

Fibonacci number （ Usually use F(n) Express ） The sequence formed is called Fibonacci sequence . The sequence is composed of 0 and 1 Start , Each of the following numbers is the sum of the first two numbers . That is to say ：

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2), among n > 1
Given n , Please calculate F(n) .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/fibonacci-number

2 Title Example

Example 1：
Input ：n = 2
Output ：1
explain ：F(2) = F(1) + F(0) = 1 + 0 = 1

Example 2：
Input ：n = 3
Output ：2
explain ：F(3) = F(2) + F(1) = 1 + 1 = 2

Example 3：
Input ：n = 4
Output ：3
explain ：F(4) = F(3) + F(2) = 2 + 1 = 3

3 Topic tips

0 <= n <= 30

4 Ideas

The boundary condition of Fibonacci number is F(0)=0 and F(1)=1. When n >1 when , Every time — The sum of terms is equal to the sum of the first two terms , Therefore, there is the following recurrence relationship :
F(n)= F(n- 1)＋F(n -2)

Because the Fibonacci number has a recursive relationship , Therefore, dynamic programming can be used to solve . The state transition equation of dynamic programming is the above recursive relationship , The boundary condition is F(0) and F(1).
According to the state transition equation and boundary conditions , We can get that the time complexity and space complexity are O(n) The implementation of the . because F(nz) And the only F(n—1) And F(n ―2) of , So you can use 「 The idea of scrolling arrays 」 Optimize the space complexity to O(1). This implementation is given in the following code .

Complexity analysis
Time complexity :O(n).·
Spatial complexity :O(1).

Method 2 : Matrix fast power
Method — The time complexity of is o(n). Using the fast power of matrix can reduce the time complexity .
First, we can construct such a recursive relationship :

So as long as we can calculate the matrix quickly M Of n The next power , You can get F(n) Value . If you get it directly Mⁿ, The time complexity is O(n), Matrix multiplication can be defined , Then use the fast power algorithm to speed up here Mⁿ The solution of .

5 My answer

class Solution {
    
    public int fib(int n) {
    
        if (n < 2) {
    
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
    
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

Method 2 ：

class Solution {
    
    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];
    }

    public int[][] pow(int[][] a, int n) {
    
        int[][] ret = {
    {
    1, 0}, {
    0, 1}};
        while (n > 0) {
    
            if ((n & 1) == 1) {
    
                ret = multiply(ret, a);
            }
            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] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}