blob: 06b374affa75612d718fa254c4945f80a8ab78aa (
plain)
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
|
// 1137. N-th Tribonacci Number
#include "leetcode.h"
/*
* the tribonacci sequence t^n is defined as follows
* t0 = 0, t1 = 1, t2 = 1, & tn+3 = tn + tn+1 + tn+2 for n >= 0
* given n, return value of tn
* eg.
* n = 4, output: 4
* t3 = 0 + 1 + 1 = 2
* t4 = 1 + 1 + 2 = 4
*/
int tribonacci(int n) {
if (n == 0)
return 0;
if (n == 1 || n == 2)
return 1;
int *tmp = malloc(sizeof(int) * (n + 1));
tmp[0] = 0;
tmp[1] = 1;
tmp[2] = 1;
for (int i = 3; i <= n; i++)
tmp[i] = tmp[i - 1] + tmp[i - 2] + tmp[i - 3];
return tmp[n];
}
int main() {
printf("%d\n", tribonacci(4)); // expect: 4
printf("%d\n", tribonacci(25)); // expect: 1389537
}
|