leetcode

0 // memorization approach

1 class Solution {

2 public:

3 int tribonacci(int n) {

4 vector<int> f(38);

5 f[0] = 0;

6 f[1] = 1;

7 f[2] = 1;

8 for (int i = 3; i <= n; i++)

9 f[i] = f[i - 1] + f[i - 2] + f[i - 3];

10 return f[n];

11 }

12 };

13

14 // optimized, memorize only the previous three values

15 class Solution {

16 public:

17 int tribonacci(int n) {

18 if (n == 0) return 0;

19 if (n == 1) return 1;

20 int a = 0, b = 1, c = 1;

21 for (int i = 3; i <= n; i++) {

22 int tmp = a + b + c;

23 a = b;

24 b = c;

25 c = tmp;

26 }

27 return c;

28 }

29 };