Companies: Coursera
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.
Example 1:
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
Example 2:
Constraints:
- 0 <= n <= 37
- 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:
- Initialize an array of Tribonacci numbers of size 38 with
0
. - Return tribo(n-1).
The next is Recursion:
- if
k = 0
, return0
. - If
nums[k] != 0
, returnnums[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.