n-th-tribonacci-number.cpp (430B)
1 class Solution { 2 public: 3 int tri(int n, vector<int>& lookup) { 4 if(n <= 1) { 5 return n; 6 } 7 if(n == 2) { 8 return 1; 9 } 10 if(lookup[n] != -1) { 11 return lookup[n]; 12 } 13 14 int rest = tri(n-1, lookup) + tri(n-2, lookup) + tri(n-3, lookup); 15 lookup[n] = rest; 16 return rest; 17 18 } 19 int tribonacci(int n) { 20 vector<int> lookup (n+1,-1); 21 return tri(n, lookup); 22 } 23 };