Solution: N-th Tribonacci Number
Let's solve the N-th Tribonacci Number problem using the Dynamic Programming pattern.
Statement
Given a number n
, calculate the corresponding Tribonacci number.
The Tribonacci sequence is defined as:
, and for |
---|
The input number, n
, is a non-negative integer.
Constraints:
-
n
- The answer is guaranteed to fit within a 32-bit integer, i.e., answer
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.
Naive approach
The first thing that comes to mind after reading the question is to use the same approach used for solving the Fibonacci sequence: recursion. The recursive approach works and will return us the correct answer here. We’ll first initialize three numbers as 0, 1, and 1. If our required Tribonacci number is 1 or 2, we’ll return 1 in the base case. Otherwise, we’ll call the function recursively three times to compute the next number’s sum, as the tribonacci number is the sum of the previous three numbers. We’ll repeat this process until we hit the base case.
Computing the nth tribonacci number this way takes time and the space complexity of .
Optimized approach using dynamic programming
We can reduce the time complexity if we use dynamic programming here. We can store the values of the elements and then reuse them to find the next element. When the specific element is needed, we just return the already stored value. This way, we don’t need the array of size n because at any given time we just need the value to be computed and the three values preceding it.
Here is how we’ll implement this algorithm:
-
Initialize the first three variables as 0, 1, and 1.
-
If
n
is less than 3, then return . -
Otherwise, run a loop
n-2
times and perform the following steps:-
Replace the first variable with the second variable.
-
Replace the second variable with the third variable.
-
Replace the third variable with the sum of these three variables.
-
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.