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

Leetcode -1137- the NTH Tabbonacci number

[Blog link]

The way to study

The nuggets home page

[Topic description]

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 n, return the value of the NTH Tabbonacci number Tn.

Example 1:

Input: n = 4 Output: 4 Explanation: 0,1,1,2,3,5 T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 T_5 =Copy 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: answer <= 231−12^{31} -1231 −1.

Related Topics

• Memorized search
• mathematics
• Dynamic programming
• 0 85

[Topic link]

Leetcode title link

[making address]

Code link

[思路介绍]

Idea 1: loop + uncompressed array

• This is very similar to the Fibonacci sequence
• It’s all about finding the last number by the states of the first few numbers
• By defining three special case decisions, and then return
• This situation is going to TLE

public int tribonacci(int n) {
    if (n < 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {return 1;
    }
    if (n == 3) {
        return 2;
    }
    return tribonacci(n-1) + tribonacci(n-2) +tribonacci(n-3);
}
Copy the code

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

Idea 2: Optimization of idea 1

• It’s easy to think of the Fibonacci sequence
• The current evaluation is only related to the first three numbers
• So you can just define three variables
• Loop iteration

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

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

Idea 3: Combinatorial mathematics

• Yeah, that’s a simple math problem
• The big boys can always find all kinds of mathematical formulas, mathematical logic
• This problem can be solved using matrices from linear algebra
• The formula is the contribution of the Big Mo ‘ao

• Actually, the logic of this matrix is pretty easy to solve, but I can’t think of a matrix
• The first row of the matrix that I end up with is
• [ Ti ∗ Ti + 1 0 + + Ti + 2 ∗ ∗ 1 0, + Ti Ti ∗ 0 + 1 1 + Ti + 2 ∗ ∗ 1, Ti ∗ ∗ 1 + 1 + 1 + Ti Ti + 2 ∗ 1 T_ {I} * 0 + T_ (I + 1} * 1 + T_ {2} I + * 0, T_ {I} * 0 + T_ (I + 1} * 1 + T_ {2} I + * 1, T_ {I} * 1 + T_ (I + 1} * 1 + T_ {2} I + * 1 + Ti Ti ∗ 0 + 1 + Ti + 2 ∗ ∗ 1 0, + Ti Ti ∗ 0 + 1 1 + Ti + 2 ∗ ∗ 1, Ti ∗ ∗ 1 + 1 + 1 + Ti Ti + 2 ∗ 1]
• [
  $T_{i+1},T_{i+2},T_{i+3}$]

class Matrix {
    int[][] a = new int[3] [3];

    Matrix(boolean x) {
        {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    a[i][j] = x ? i == j ? 1 : 0 : 0; }}}}// Multiply
    Matrix multi(Matrix b) {
        Matrix C = new Matrix(false);
        for (int k = 0; k < 3; k++) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) { C.a[i][j] = (C.a[i][j] + a[i][k] * b.a[k][j]); }}}return C;
    }

    // Intersection operation
    Matrix babel(int n) {
        Matrix C = new Matrix(true);
        Matrix A = new Matrix(false);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) { A.a[i][j] = a[i][j]; }}for (; n > 0; n >>= 1, A = A.multi(A)) {
            if ((n & 1) = =1) { C = C.multi(A); }}returnC; }}public int tribonacci(int n) {
    Matrix A = new Matrix(false);
    A.a[0] [1] =1;
    A.a[0] [2] =1;
    Matrix B = new Matrix(false);
    B.a[0] [2] =1;
    B.a[1] [0]=B.a[1] [2] =1;
    B.a[2] [1]=B.a[2] [2] =1;
    B=(B.babel(n));
    A=A.multi(B);
    return A.a[0] [0];
}
Copy the code

• Order LGN in time.
• Space complexity O(1)

Thought dead: metaphysical mathematics

• This formula was also found by the Mo ‘ao boss
• These are some really good mathematicians.

public int tribonacci(int n) {
    return (int)Math.floor((Math.pow(33.0* (99.0-17.0*Math.sqrt(33.0)),1.0/3.0)+Math.pow(33.0* (99.0+17.0*Math.sqrt(33.0)),1.0/3.0)) /66.0*Math.pow((1.0+Math.pow(19.0-3.0*Math.sqrt(33.0),1.0/3.0)+Math.pow(19.0+3.0*Math.sqrt(33.0),1.0/3.0)) /3.0.1.0*n)+0.5);

}
Copy the code

• Time complexity O(1)

• Space complexity O(1)

• ToDo: today to go out during the day, first write here, and DP start can also use, but and before the scrolling array gap is not big, come back at night, by the way, the week match of the supplement