leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

nth_tribonacci_number.c (675B)

 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
}