Introduction

In this article, we will solve the leetcode problem #1137, N-th Tribonacci Number. Just like the N-th term of Fibonacci sequence is the sum of last two terms, the N-th term in Tribonnaci sequence is the sum of last three terms in the sequence. 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.
Constraints: 0 <= n <= 37. The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.
  1. static void Main(string[] args)
  2. {
  3. var result = tribonacci(4);
  4. //result = 4
  5. result = tribonacci(25);
  6. //result = 1389537
  7. }

Solution

The algorithm for solving the N-th Term of Tribonacci sequence is as follows,
  1. Make an array F of length 38, and set F[0] = 0, F[1] = F[2] = 1.
  2. Now write a loop where you set F[n+3] = F[n] + F[n+1] + F[n+2], and return F[n].
Here is the C# code for the approach,
  1. static int tribonacci(int n)
  2. {
  3. if (n <= 1)
  4. {
  5. return n;
  6. }
  7. int[] numbers = new int[n + 1];
  8. numbers[0] = 0;
  9. numbers[1] = 1;
  10. numbers[2] = 1;
  11. Enumerable.Range(3, n - 2).ToList().ForEach(i=> numbers[i] = numbers[i - 1] + numbers[i - 2] + numbers[i - 3]);
  12. return numbers[n];
  13. }