This is the 7th day of my participation in the August Text Challenge.More challenges in August

Topic describes

Tn of The Tebonacci sequence is defined as follows:

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

Given the integer n, please return the value of the NTH Tebonacci number Tn.

T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 https://leetcode-cn.com/problems/n-th-tribonacci-number copyright belongs to The Collar network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • This is a common problem, the same kind of problem as the Fibonacci sequence, so the solution is universal.
  • The Fibonacci sequence is also known as the Golden section sequence. As the number of terms increases, the ratio of the former term to the latter term is closer and closer to the golden section value 0.6180339887.
  • The simple solution is to use recursion, recursion algorithm has a large number of repeated calculation, high time complexity. In view of repeated calculation, memorization can be used to optimize and avoid repeated calculation.
  • The boundary conditions of Tibonacci numbers are T(0)=0, T(1)=1, T(2)=1. When n>2, the sum of each term is equal to the sum of the first three terms, and the recursive relation is obtained: T(n)=T(n-1)+T(n-2)+T(n-3). The memorization implementation code is as follows:

Through the code

    public int tribonacci(int n) {
        if (n == 0) {
            return n;
        }
        if (n <= 2) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }
Copy the code

conclusion

  • The above code has O(n) time complexity and O(n) space complexity.
  • This topic is better implemented in the form of variables, dynamic update, space complexity is O(1), higher efficiency! The code is basically the same as above, please interested students to achieve their own, in the message or comment with me.
  • Stick to the daily question, come on!