Fibonacci sequence: “Dynamic Programming” & “Tabulation” & “Matrix Fast Power”

Topic describes

This is the finger Offer 10-I on LeetCode. Fibonacci sequence, the difficulty is simple.

Tag: “Dynamic Programming”, “Linear DP”, “Mnemonic Search”, “Tabulation”, “Matrix Fast Power”

Write a function, input n, to find the NTH term of the Fibonacci sequence. The Fibonacci sequence is defined as follows:

• F(0) = 0,   F(1) = 1
• F(N) = F(n-1) + F(n-2), where N is greater than 1.

The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers.

1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1.

Example 1:

Input: n = 2 Output: 1Copy the code

Example 2:

Input: n = 5 Output: 5Copy the code

Tip:

• 0 <= n <= 100

Recursive implementation of dynamic programming

Now that we have the transfer equation, we can just recurse from the beginning to the end of the transfer equation.

Code:

class Solution {
    int mod = (int)1e9+7;
    public int fib(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int c = a + b;
            c %= mod;
            a = b;
            b = c;
        }
        returnb; }}Copy the code

• Time complexity: O(n)O(n)O(n)
• Space complexity: O(1)O(1)O(1)

Recursive implementation of dynamic programming

Dynamic programming can be implemented in a “recursive” form, and of course it can be implemented in a “recursive” form.

To prevent double counting, we need to add the “memorized search” function, and use a value XXX that may be repeated as an “intermediate result” between different samples, and the result fib(x)fib(x)fib(x) is fixed. We can use static to modify the cache, To enable the computed results to be shared among all test samples.

Code:

class Solution {
    static int mod = (int)1e9+7;
    static int N = 110;
    static int[] cache = new int[N];
    public int fib(int n) {
        if (n <= 1) return n;
        if(cache[n] ! =0) return cache[n];
        cache[n] = fib(n - 1) + fib(n - 2);
        cache[n] %= mod;
        returncache[n]; }}Copy the code

• Time complexity: O(n)O(n)O(n)
• Space complexity: O(1)O(1)O(1)

The meter

After “solution 2”, we further found that the data range of 100100100 can be used for tabulating pre-processing, and then directly returned.

Code:

class Solution {
    static int mod = (int)1e9+7;
    static int N = 110;
    static int[] cache = new int[N];
    static {
        cache[1] = 1;
        for (int i = 2; i < N; i++) {
            cache[i] = cache[i - 1] + cache[i - 2]; cache[i] %= mod; }}public int fib(int n) {
        returncache[n]; }}Copy the code

• Time complexity: When the tabling logic is executed locally, the complexity is O(1)O(1)O(1). Otherwise, it is O(C)O(C)O(C). CCC is a constant and the fixed value is 110110110
• Space complexity: O(C)O(C)O(C)

Matrix rapid power

For the recursion problem, matrix fast power can be used to accelerate, the most complete introduction is inhereTalked about.

In this case, some f(n)f(n)f(n) depends on f(n−1)f(n-1)f(n−1) and f(n−2)f(n-2)f(n−2) f(n−2). Store the dependent states as column vectors:

The target value f(n)f(n) is located in the matrix:

According to matrix multiplication, it is not difficult to find:

We make:

Starting, we only [f (1) f (0)] \ begin {bmatrix} f (1) \ \ f (0) \ end {bmatrix} [f (1) f (0)], according to the recursive formula:

Then according to the “associative law” of matrix multiplication, the final result can be obtained:

Calculation Matn −1mat^{n-1} Matn −1 can be solved by using “fast powers”.

Code:

class Solution {
    int mod = (int)1e9+7;
    long[][] mul(long[][] a, long[][] b) {
        int r = a.length, c = b[0].length, z = b.length;
        long[][] ans = new long[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                for (int k = 0; k < z; k++) { ans[i][j] += a[i][k] * b[k][j]; ans[i][j] %= mod; }}}return ans;
    }
    public int fib(int n) {
        if (n <= 1) return n;
        long[][] mat = new long[] [] {{1.1},
            {1.0}};long[][] ans = new long[] [] {{1},
            {0}};int x = n - 1;
        while(x ! =0) {
            if ((x & 1) != 0) ans = mul(mat, ans);
            mat = mul(mat, mat);
            x >>= 1;
        }
        return (int)(ans[0] [0] % mod); }}Copy the code

• Time complexity: O(log⁡n)O(\log{n})O(logn)
• Space complexity: O(1)O(1)O(1)

Other “tabulated” content

Note: The above catalogues are fromwiki, any form of reprint quote please retain the source.

Other matrix Quick powers content

Note: The above catalogues are fromwiki, any form of reprint quote please retain the source.

The last

This is the first Offer 10-I of our series of articles “Brush through LeetCode”. The series started on January 21, 01/01, and there are 1916 questions on LeetCode by the start date, some of which have lock questions. We will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.