> For the complete documentation index, see [llms.txt](https://interviews.woojiahao.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://interviews.woojiahao.com/problems-guide/dynamic-programming-roadmap/warmup/nth-tribonacci-number.md).

# Nth Tribonacci Number

This problem is basically [Climbing Stairs](/problems-guide/dynamic-programming-roadmap/warmup/climbing-stairs.md) but using three states instead.

## Bottom-up

$$
dp(m) = \begin{cases}
0, m = 0\\
1, m = 1\\
1, m = 2\\
dp(m-2) + dp(m - 1) + dp(m)
\end{cases}
$$

As discussed in [Climbing Stairs](/problems-guide/dynamic-programming-roadmap/warmup/climbing-stairs.md), since we only rely on the past `3` states, we can use $$n$$ state caching and store them as variables instead.

```python
def tribonacci(n):
    if n == 0: return 0 # base case
    t0, t1, t2 = 0, 1, 1
    for i in range(3, n + 1):
        t0, t1, t2 = t1, t2, t0 + t1 + t2
    return t2
```