# N-th Tribonacci Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/n-th-tribonacci-number)
Canonical: https://scaleengineer.com/dsa/problems/n-th-tribonacci-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [tcs](https://scaleengineer.com/companies/tcs), [Coursera](https://scaleengineer.com/companies/coursera)
---
## Problem
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 <= 37`
* The answer is guaranteed to fit within a 32-bit integer, ie. `answer <= 2^31 - 1`.

# Approaches
## Brute-Force Recursion
This is the most straightforward approach, where the Tribonacci recurrence relation is directly translated into a recursive function. The function calls itself for the three preceding numbers until it reaches the base cases.
**Time:** O(3^n) - For each number `n`, the function makes three recursive calls. This leads to an exponential number of function calls, making it highly inefficient. · **Space:** O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can go up to `n`.
**Pros:** Very simple to understand and implement as it directly follows the mathematical definition.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' error for even moderately large values of `n` (e.g., n > 30).
### Explanation
The function `tribonacci(n)` is defined to compute the n-th Tribonacci number. The base cases `T_0 = 0`, `T_1 = 1`, and `T_2 = 1` are handled explicitly. For any `n > 2`, the function makes three recursive calls to compute `tribonacci(n-1)`, `tribonacci(n-2)`, and `tribonacci(n-3)`, and returns their sum. This creates a recursion tree where many branches recalculate the same values. For instance, `tribonacci(5)` calculates `tribonacci(4)` and `tribonacci(3)`. The call to `tribonacci(4)` will also calculate `tribonacci(3)`, leading to redundant work.

```java
class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
    }
}
```
### Algorithm
- Define a function `tribonacci(n)`.
- If `n` is 0, return 0.
- If `n` is 1 or 2, return 1.
- Otherwise, return the sum of `tribonacci(n-1)`, `tribonacci(n-2)`, and `tribonacci(n-3)`.

## Memoization (Top-Down DP)
This approach, also known as top-down dynamic programming, optimizes the brute-force recursion. It uses a data structure (like an array or map) to store the results of subproblems so that they don't need to be recomputed. This technique is called memoization.
**Time:** O(n) - Each Tribonacci number from 0 to `n` is computed exactly once. The lookup and storage operations are constant time. · **Space:** O(n) - An array of size `n+1` is used for memoization, and the recursion stack can also go up to depth `n`.
**Pros:** Drastically improves time complexity from exponential to linear.; Retains the logical structure of the recursive definition.
**Cons:** Uses O(n) space for the memoization array.; Incurs overhead from recursive function calls, which can be slightly less performant than an iterative solution.
### Explanation
We introduce a `memo` array to cache the results. The `trib(n, memo)` function first checks if the value for `n` has already been computed by looking it up in `memo`. If it exists, the cached value is returned immediately, avoiding redundant computation. If not, the value is computed recursively, stored in `memo[n]`, and then returned. This ensures that each Tribonacci number from 0 to `n` is calculated only once.

```java
class Solution {
    public int tribonacci(int n) {
        // Using an array of size 38 as per constraints 0 <= n <= 37
        int[] memo = new int[38];
        // Initialize with a value to indicate not computed, e.g., -1
        // (or rely on default 0, but handle T_0=0 case)
        return trib(n, memo);
    }

    private int trib(int n, int[] memo) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        if (memo[n] != 0) return memo[n];

        memo[n] = trib(n - 1, memo) + trib(n - 2, memo) + trib(n - 3, memo);
        return memo[n];
    }
}
```
### Algorithm
- Create a memoization array `memo` of size `n+1` to store computed results.
- Define a recursive helper function that takes `n` and `memo` as arguments.
- In the helper, first check for base cases (n=0, 1, 2).
- Before computing, check if `memo[n]` already holds a computed value. If so, return it.
- If not, compute the result recursively: `trib(n-1) + trib(n-2) + trib(n-3)`.
- Store the computed result in `memo[n]` before returning it.

## Tabulation (Bottom-Up DP)
This approach, also known as bottom-up dynamic programming, solves the problem iteratively. It builds a table of solutions for subproblems, starting from the smallest ones (the base cases) and working its way up to the target `n`.
**Time:** O(n) - We iterate through a single loop from 3 to `n`. · **Space:** O(n) - An array of size `n+1` is used to store the intermediate results.
**Pros:** Efficient O(n) time complexity.; Avoids recursion overhead, which can make it slightly faster in practice than memoization.; Easy to understand and implement.
**Cons:** Requires O(n) space to store the entire table of Tribonacci numbers, which is not optimal.
### Explanation
Instead of using recursion, we use an array, `dp`, to store the Tribonacci numbers in order. We start by filling in the known base cases: `dp[0]`, `dp[1]`, and `dp[2]`. Then, we loop from 3 up to `n`, and for each index `i`, we calculate `dp[i]` by summing the three preceding values in the array (`dp[i-1]`, `dp[i-2]`, and `dp[i-3]`). This process fills the table from the bottom up. The final answer is the last value computed, `dp[n]`.

```java
class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;

        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];
    }
}
```
### Algorithm
- Handle the base cases for `n=0, 1, 2`.
- Create a `dp` array of size `n+1`.
- Initialize the first three values: `dp[0] = 0`, `dp[1] = 1`, `dp[2] = 1`.
- Iterate from `i = 3` to `n`.
- In each iteration, calculate `dp[i]` as `dp[i-1] + dp[i-2] + dp[i-3]`.
- Return `dp[n]` as the final result.

## Space-Optimized Dynamic Programming
This is the most efficient approach in terms of space. By observing the recurrence relation `T_n = T_{n-1} + T_{n-2} + T_{n-3}`, we can see that to compute any Tribonacci number, we only need the three previous ones. This allows us to discard older values and use only a constant amount of space.
**Time:** O(n) - A single loop runs from 3 to `n`, performing constant time operations inside. · **Space:** O(1) - Only a constant number of variables are used, regardless of the input `n`.
**Pros:** Optimal O(1) space complexity.; Efficient O(n) time complexity.; Simple and fast implementation, ideal for competitive programming and interviews.
**Cons:** For the given constraints, this approach has no significant cons and is considered optimal.
### Explanation
This method optimizes the tabulation approach by reducing the space complexity from O(n) to O(1). Instead of an entire array, we only use three variables to keep track of the last three computed Tribonacci numbers. Let's call them `t0`, `t1`, and `t2`, initialized to `T_0`, `T_1`, and `T_2`. We then loop from 3 to `n`. In each iteration, we calculate the next value as their sum. Then, we update the three variables to prepare for the next iteration: `t0` takes the value of `t1`, `t1` takes the value of `t2`, and `t2` takes the newly computed value. This effectively slides our window of three numbers one step forward. The final result is the last computed value.

```java
class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        
        int t0 = 0;
        int t1 = 1;
        int t2 = 1;
        
        for (int i = 3; i <= n; i++) {
            int nextVal = t0 + t1 + t2;
            t0 = t1;
            t1 = t2;
            t2 = nextVal;
        }
        
        return t2;
    }
}
```
### Algorithm
- Handle base cases for `n=0, 1, 2`.
- Initialize three variables to hold the first three Tribonacci numbers: `t0 = 0`, `t1 = 1`, `t2 = 1`.
- Iterate from `i = 3` to `n`.
- In each iteration, calculate the next Tribonacci number: `nextVal = t0 + t1 + t2`.
- Update the three variables to 'slide' the window: `t0 = t1`, `t1 = t2`, `t2 = nextVal`.
- After the loop, `t2` will hold the value for `T_n`. Return `t2`.

# Solutions
### Java

```java
class Solution {
public
  int tribonacci(int n) {
    int a = 0, b = 1, c = 1;
    while (n-- > 0) {
      int d = a + b + c;
      a = b;
      b = c;
      c = d;
    }
    return a;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @return {number} */ var tribonacci = function (n) {
  let a = 0;
  let b = 1;
  let c = 1;
  while (n--) {
    let d = a + b + c;
    a = b;
    b = c;
    c = d;
  }
  return a;
};

```

### CPP

```cpp
class Solution {
public:
  int tribonacci(int n) {
    long long a = 0, b = 1, c = 1;
    while (n--) {
      long long d = a + b + c;
      a = b;
      b = c;
      c = d;
    }
    return (int)a;
  }
};

```

### Python

```python
class Solution:
    def tribonacci(self, n: int) -> int: a, b, c = 0, 1, 1 for _ in range(n): a, b, c = b, c, a + b + c return a

```