# Leetcode 1137. N-th Tribonaacci Number

## 題解

### 動態規劃

#### Bottom up

class Solution:
    def tribonacci(self, n: int) -> int:
        # Time complexity: O(n)
        # Space complexity: O(1)
        if n == 0:
            return n
        t1 = 0
        t2 = 1
        t3 = 1
        for i in range(2,n):
            t_next = t1 + t2 + t3
            t1 = t2
            t2 = t3
            t3 = t_next
        return t3