-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNth-Tribonacci.cpp
More file actions
63 lines (52 loc) · 1000 Bytes
/
Nth-Tribonacci.cpp
File metadata and controls
63 lines (52 loc) · 1000 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
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
*/
#include <bits/stdc++.h>
using namespace std;
vector<int>dp;
int solve(int n)
{
if(dp[n]!=-1)
return dp[n];
if(n==0)
return dp[n]=0;
if(n==1 || n==2)
return dp[n]=1;
return dp[n]=solve(n-1)+solve(n-2)+solve(n-3);
}
int tribonacci(int n)
{
dp.resize(n+1,-1);
return solve(n);
}
int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
cout<<tribonacci(n)<<"\n";
}
return 0;
}
//Tabulation - DP
int tribonacci(int n) {
int arr[39];
arr[0]=0; arr[1]=1;arr[2]=1;
if(n<=2) return arr[n];
for(int i=3;i<=n;i++){
arr[i]=arr[i-1]+arr[i-2]+arr[i-3];
}
return arr[n];
}