Sponsored
Sponsored
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.
Time Complexity: O(n), Space Complexity: O(1).
1#include <stdio.h>
2
3int tribonacci(int n){
4 if (n == 0) return 0;
5 if (n == 1 || n == 2) return 1;
6
7 int t0 = 0, t1 = 1, t2 = 1;
8 int t = 0;
9 for (int i = 3; i <= n; i++) {
10 t = t0 + t1 + t2;
11 t0 = t1;
12 t1 = t2;
13 t2 = t;
14 }
15 return t;
16}
17
18int main() {
19 int n = 25;
20 printf("%d", tribonacci(n));
21 return 0;
22}The C solution initializes the three previous values T0, T1, and T2 and iteratively calculates up to the N-th term.
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.
Time Complexity: O(n), Space Complexity: O(n).
1#include <iostream>
2#include <unordered_map>
3
4int tribonacci(int n, std::unordered_map<int, int>& memo) {
5 if (memo.find(n) != memo.end()) {
6 return memo[n];
}
memo[n] = tribonacci(n-1, memo) + tribonacci(n-2, memo) + tribonacci(n-3, memo);
return memo[n];
}
int main() {
std::unordered_map<int, int> memo = {{0, 0}, {1, 1}, {2, 1}};
int n = 25;
std::cout << tribonacci(n, memo) << std::endl;
return 0;
}The C++ solution takes advantage of STL's unordered_map to store and look up the precomputed Tribonacci numbers.