# 資訊

:::info
- Question: 1137. N-th Tribonacci Number
- From: Leetcode Daily Challenge 2024.04.24
- Difficulty: Easy
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

The Tribonacci sequence $T_n$ is defined as follows:

$T_0 = 0$, $T_1 = 1$, $T_2 = 1$, and $T_{n+3} = T_n + T_{n+1} + T_{n+2}$ for $n \geq 0$

Given $n$, return the value of $T_n$

> Example 1:
:::success
* Input: n = 4
* Output: 4
* Explanation:
* $T_3$ = 0 + 1 + 1 = 2
* $T_4$ = 1 + 1 + 2 = 4
:::

> Example 2:
:::success
* Input: n = 25
* Output: 1389537
:::

> Constraints:
:::success
* 0 <= n <= 37
* The answer is guaranteed to fit within a 32-bit integer, ie. answer <= $2^{31} - 1$
:::

---

# 解法

## 概念

經典 DP 題，只是疊了三層，看到昨天 CPE 出了 Fib 但偷動手腳於是沒解出來就把停更幾天的 leetcode 抓出來寫，順便拿這題洩憤

## 程式碼

class Solution:
    def tribonacci(self, n: int) -> int:
        T = [0, 1, 1]
        for i in range(3, n+1):
            T.append( T[i-3] + T[i-2] + T[i-1] )
        return T[n]

---

# 複雜度

## 時間複雜度

DP 所以是 $O(N)$


## 空間複雜度

也是因為 DP 所以花了 $O(N)$ 的空間