878377. Tribonacci Number
Tribonacci Number
Summary
The Tribonacci number is a sequence that generalizes the Fibonacci sequence. In this problem, we need to find the nth Tribonacci number, which is defined as the sum of the last three terms in the sequence: 0, 1, 1, 2, 4, 7, 13, ... . This problem involves understanding the concept of recursion and dynamic programming.
Detailed Explanation
The Tribonacci sequence is similar to the Fibonacci sequence, but instead of adding the last two terms, we add the last three. The base cases are the first three terms: 0, 1, and 1. To generate the next term, we sum the last three terms in the sequence.
Here's a step-by-step breakdown of the solution:
- Define a function
tribonacci(n)that returns the nth Tribonacci number. - Base case: If
nis less than or equal to 2, return 0 (since the first two terms are 0 and 1). - Recursive case: For
ngreater than 2, calculate thenth Tribonacci number as the sum of the(n-1)th,(n-2)th, and(n-3)th numbers. - Use dynamic programming to store the results of previously calculated Tribonacci numbers and avoid redundant calculations.
The time complexity is O(n), since we need to calculate each term in the sequence. The space complexity is also O(n) for storing the results of previously calculated terms.
Here's an ASCII art diagram representing the Tribonacci sequence:
0, 1, 1, 2, 4, 7, 13, ...
^
|--- sum of last three terms
Optimized Solutions
Java
public class Tribonacci {
public static int tribonacci(int n) {
if (n <= 2) return 0;
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = 1; dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
}