The NTH Tabbonacci number: “iteration” & “recursion” & “Matrix quick power” & “tabulation”

This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic describes

This is the 1137.nth Tabbonacci number in LeetCode, and the difficulty is easy.

Tag: “dynamic programming”, “recursion”, “recursion”, “matrix quick power”, “tabulation”

The Taibonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn+ Tn+1 + Tn+2 if n >= 0

Given the integer NNN, return the value of the NNTH tabbonacci number TnT_nTn.

Example 1:

Input: n = 4 Output: 4 Description: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4Copy the code

Example 2:

Input: n = 25 Output: 1389537Copy the code

Tip:

• 0 <= n <= 37
• The answer is guaranteed to be a 32-bit integer, i.e. Answer <= 2312^{31} 231-1.

Iterative implementation of dynamic programming

It gives you the state transition equation, which is actually a simulation problem.

Using three variables, just go back and forth.

Code:

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        returnc; }}Copy the code

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

Recursive dynamic programming

It’s a memorized search, creating a cache array to prevent double counting.

Code:

class Solution {
    int[] cache = new int[40];
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        if(cache[n] ! =0) return cache[n];
        cache[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3); 
        returncache[n]; }}Copy the code

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

Matrix fast power

Again, this is a board problem for quick powers of matrices.

First you need to understand the concepts of fast powers and matrix multiplication.

The matrix fast power is used to solve the general problem: given the matrix MMM of size n∗ NN * NN ∗ N, find the answer matrix MkM^kMk, and modulo PPP to each element in the answer matrix.

In the above two solutions, when we want to solve f[I]f[I]f[I]f[I], we need to calculate f[0]f[0]f[0] f[0] to F [n−1]f[n-1]f[n−1], so linear complexity is required.

For such “sequence recursion” problems, we can use “matrix fast powers” to accelerate (for example, if we recurse a sequence of length 1e91E91e9, the linear complexity will get stuck).

Using matrix fast powers, we only need O(log⁡n)O(\log{n})O(logn) complexity.

(I >=3i >=3i >=3i)

We found that require solutions f (I) f (I) f (I), it relies on the f (I – 1) f (I – 1) f (I – 1), f (I) – 2 f (I – 2) f (I – 2) and f (I) – 3 f (I – 3) f (I – 3).

We can store it as a column vector:

After sorting out the dependent column vectors, it’s not difficult to find that the column vector that we want to find f(I)f(I)f(I) looks like this:

The target matrix elements are expanded by using the dependencies given in the topic:

So according to matrix multiplication, we have:

We make

Then we found that we could also recurse the sequence using MatMatMat (the formula is too hard to type, just list two terms) :

Then according to the associative law of matrix operation, the final result is:

Thus, the problem is transformed into solving Matn−2Mat^{n-2}Matn−2, and the “matrix quick power” solution can be applied.

Code:

class Solution {
    int N = 3;
    int[][] mul(int[][] a, int[][] b) {
        int[][] c = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j]; }}return c;
    }
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int[][] ans = new int[] [] {{1.0.0},
            {0.1.0},
            {0.0.1}};int[][] mat = new int[] [] {{1.1.1},
            {1.0.0},
            {0.1.0}};int k = n - 2;
        while(k ! =0) {
            if ((k & 1) != 0) ans = mul(ans, mat);
            mat = mul(mat, mat);
            k >>= 1;
        }
        return ans[0] [0] + ans[0] [1]; }}Copy the code

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

The meter

Of course, we can also preprocess all the answers in the range of data, and then directly look up the table when asking.

However, the benefits brought by this kind of questions are not as large as the usual tabulating questions, because the tabulating content is not as a necessary link of the algorithm, but directly as the answer to the question, but the test sample is not the same, that is, there will not be two test data n= 37N = 37N =37.

For example, n= 36N = 36N =36 and n= 37N = 37N =37. The calculation before 353535 will only be calculated once.

Therefore, it is better to simply add static to the cache in solution 2: the code is shorter and has the same amount of computation savings.

Code:

class Solution {
    static int[] cache = new int[40];
    static {
        cache[0] = 0;
        cache[1] = 1;
        cache[2] = 1;
        for (int i = 3; i < cache.length; i++) {
            cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3]; }}public int tribonacci(int n) {
        returncache[n]; }}Copy the code

• Time complexity: the time complexity is O(C)O(C)O(C) O(C)O(C)O(C). CCC is fixed to 404040. Place the typing logic locally, O(1)O(1)O(1)
• Space complexity: O(n)O(n)O(n)

The last

This is article No.1035 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

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

In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.