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).
1using System;
2
3public class Program
4{
5 public static int Tribonacci(int n)
6 {
7 if (n == 0) return 0;
8 if (n == 1 || n == 2) return 1;
9
10 int t0 = 0, t1 = 1, t2 = 1;
11 int t = 0;
12 for (int i = 3; i <= n; i++)
13 {
14 t = t0 + t1 + t2;
15 t0 = t1;
16 t1 = t2;
17 t2 = t;
18 }
19 return t;
20 }
21
22 public static void Main()
23 {
24 int n = 25;
25 Console.WriteLine(Tribonacci(n));
26 }
27}A C# implementation using a static method within a class to compute Tribonacci using iteration, printed via Console.WriteLine().
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()) {
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.