> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/dp/1137.-n-th-tribonacci-number.md).

# 1137. N-th Tribonacci Number

Easy  |  DP  |  24 ms (94.39%),  14.2 MB (43.64%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - N-th Tribonacci Number](https://leetcode.com/problems/n-th-tribonacci-number/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/1137-n-th-tribonacci-number)

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.**
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `0 <= n <= 37`
* The answer is guaranteed to fit within a 32-bit integer, ie. `answer <= 2^31 - 1`.

```
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Input: n = 25
Output: 1389537
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Same as [**0509. Fibonacci Number**](https://yyloumike.gitbook.io/leetcode/dp/0509.-fibonacci-number)
{% endhint %}
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def tribonacci(self, n: int) -> int:
        # (base case)
        if n == 0: return 0
        if n == 1: return 1
        if n == 2: return 1
        
        # ==================================================
        #  Dynamic Programming                             =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        first, second, third = 0, 1, 1
        
        for i in range(n - 2):
            ans = first + second + third
            first = second
            second = third
            third = ans
            
        return third
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */

    public int tribonacci(int n) {
        /* base case */
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        
        int first = 0, second = 1, third = 1;
        
        for(int i=0 ; i<n-2 ; i++) {
            int ans = first + second + third;
            first = second;
            second = third;
            third = ans;
        }
        
        return third; 
    }
}
```

{% endtab %}
{% endtabs %}