Nth Tribonacci Number

Problem Source

Companies: Coursera

The Tribonacci sequence Tn is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

Input: n = 4

Output: 4

Explanation:

T_3 = 0 + 1 + 1 = 2

T_4 = 1 + 1 + 2 = 4

Example 2:

Constraints:

1. 0 <= n <= 37
2. The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Solution:

There can be two possible scenerios to implement the solution: 1. Space Optimisation, 2. Performance Optimisation.

Space Optimisation can be implementated using dynamic programming without using recursion in it.

We will implement second type of optimisation here:
Performance based Optimisation. We will use both dynamic programming as well as recursion.

Dynamic Programming has two major categories: Memoization and Tabulation.

Memoization is a term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again.

We will use precomputed 38 Tribonacci numbers:

1. Initialize an array of Tribonacci numbers of size 38 with 0.
2. Return tribo(n-1).

The next is Recursion:

• if k = 0, return 0.
• If nums[k] != 0, return nums[k].
• Otherwise, nums[k] = tribo(k - 1) + tribo(k - 2) + tribo(k - 3). Return nums[k].

Implementation

Java

class Tri {
  private int n = 38;
  public int[] nums = new int[n];

  int tribo(int k) {
    if (k == 0) return 0;
    if (nums[k] != 0) return nums[k];

    nums[k] = tribo(k - 1) + tribo(k - 2) + tribo(k - 3);
    return nums[k];
  }

  Tri() {
    nums[1] = 1;
    nums[2] = 1;
    tribo(n - 1);
  }
}

class Solution {
  public static Tri t = new Tri();
  public int tribonacci(int n) {
    return t.nums[n];
  }
}

Complexity Analysis:

• Time Complexity: O(1).
• Space Complexity: Constant Space.