---
title: "1137. N-th Tribonacci Number"
url: "https://laigary.com/interview/coding/1137-n-th-tribonacci-number"
type: "note"
section: "coding"
date: "2024-01-05"
updated: "2024-03-03"
tags: ["Dynamic Programming"]
---

# 1137. N-th Tribonacci Number

[1137\. N-th Tribonacci Number](https://leetcode.com/problems/n-th-tribonacci-number/)

## 自頂向下

```python
class Solution:
    def tribonacci(self, n: int) -> int:
        
        memo = defaultdict(int)
        memo[0] = 0
        memo[1] = 1
        memo[2] = 1
        def helper(n):
            if n in memo:
                return memo[n]
            
            memo[n] = helper(n - 1) + helper(n - 2) + helper(n - 3)
            return memo[n]
        return helper(n)
```

## 自底向上

```python
class Solution:
    def tribonacci(self, n: int) -> int:
        
        if n == 0:
            return 0
        elif n <= 2:
            return 1
        
        a = 0
        b = 1
        c = 1
        
        n -= 2
        
        while n > 0:
            a, b, c = b, c, a + b + c
            n -= 1
        
        return c
```