The Tribonacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.
Example 1:
Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4
Example 2:
Input: n = 25 Output: 1389537
Constraints:
0 <= n <= 37answer <= 2^31 - 1.
class Solution {
public int tribonacci(int n) {
if( n==0){
return 0;
}else if ( n==1 || n==2){
return 1 ;
}
int ft = 0 ;
int st = 1 ;
int tt = 1 ;
for(int i=1 ; i<=n;i++){
int fot = ft + st + tt ;
ft = st ;
st = tt ;
tt = fot ;
}
return ft ;
}
}
class Solution {
public:
int tribonacci(int n) {
if(n<3)return (n!=0);
int first=0;
int second=1;
int third=1;
int fourth=0;
for(int i=3; i<=n; i++)
{
fourth=first+second+third;
first=second;
second=third;
third=fourth;
}
return third;
}
};
def tribonacci(self, n: int) -> int:
if n == 0:
return 0
if n == 1 or n == 2:
return 1
dp = [0, 1, 1]
for i in range(3, n + 1):
dp.append(dp[i - 1] + dp[i - 2] + dp[i - 3])
return dp[n]
