1137. N-th Tribonacci Number
The Tribonacci sequence Tn is defined as follows:
T 0 = 0 T_0 = 0 T0=0, T 1 = 1 T_1 = 1 T1=1, T 2 = 1 T_2 = 1 T2=1, and T n + 3 = T n + T n + 1 + T n + 2 T_{n+3} = T_n + T_{n+1} + T_{n+2} Tn+3=Tn+Tn+1+Tn+2 for n >= 0.
Given n, return the value of T n T_n Tn.
Example 1:
Example 2:
Constraints:
- 0 <= n <= 37
- The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2 31 − 1 2^{31} - 1 231−1.
From: LeetCode
Link: 1137. N-th Tribonacci Number
Solution:
Ideas：
This function first checks for the base cases, i.e., when n is 0, 1, or 2, and returns the corresponding Tribonacci number directly. For other cases, it iteratively calculates the Tribonacci numbers up to n and returns the last computed value. This solution is efficient and avoids the overhead of recursion, making it well-suited for the constraints given in the problem statement.
Caode:
int tribonacci(int n) {
// Base cases
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
// Initial values for T_0, T_1, and T_2
int T0 = 0, T1 = 1, T2 = 1;
// To store the next Tribonacci number
int nextT;
// Compute Tribonacci from T_3 to T_n
for (int i = 3; i <= n; i++) {
nextT = T0 + T1 + T2; // Compute the next Tribonacci number
T0 = T1; // Update T0 to T1's value
T1 = T2; // Update T1 to T2's value
T2 = nextT; // Update T2 to the newly computed value
}
// T2 now contains T_n
return T2;
}