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:
Input: n = 25 Output: 1389537
Constraints:
0 <= n <= 37answer <= 2^31 - 1.This approach uses an iterative method with dynamic programming principles to compute the N-th Tribonacci number. We maintain a list or variables to store previously computed values to avoid redundant calculations. This approach provides an optimal solution both in terms of time and space.
The C solution initializes the three previous values T0, T1, and T2 and iteratively calculates up to the N-th term.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1).
This approach employs recursion with memoization to compute the Tribonacci numbers. Here, we recursively break the problem into smaller subproblems and cache the results of each computed Tribonacci number to avoid redundant calculations, thus optimizing the recursive solution in terms of performance.
In this Python code, a dictionary is used as a memoization cache, storing the results of each calculated Tribonacci number.
C++
Time Complexity: O(n), Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Iterative Dynamic Programming Approach | Time Complexity: O(n), Space Complexity: O(1). |
| Recursive Solution with Memoization | Time Complexity: O(n), Space Complexity: O(n). |
N-th Tribonacci Number - Leetcode 1137 • NeetCodeIO • 10,701 views views
Watch 9 more video solutions →Practice N-th Tribonacci Number with our built-in code editor and test cases.
Practice on FleetCode