###### tags: `Leetcode` `easy` `dynamic programming` `python` `c++`

# 1137. N-th Tribonacci Number

## [題目連結:] https://leetcode.com/problems/n-th-tribonacci-number/description/

## 題目:
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.

**Example 1:**

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

**Example 2:**

Input: n = 25
Output: 1389537

## 解題想法:
* 題目為求n-th的斐波納
* 基本做法:
* 使用DP: dp[n]=dp[n-1]+d[n-2]+dp[n-3]
* 優化:
* **節省記憶體**
* 不用整個數組紀錄所有數字
* **只需紀錄當前數字相關的前三個即可**

## Python:

class Solution(object):
    def tribonacci(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<2:
            return n
        first=0
        second=1
        third=1
        for i in range(2,n):
            tmp=first
            first=second
            second=third
            third=tmp+first+second
        return third

## C++:

class Solution {
public:
    int tribonacci(int n) {
        if (n<2)
            return n;
        int first=0, second=1, third=1;
        int tmp;
        for (int i=2; i<n; i++){
            tmp=first;
            first=second;
            second=third;
            third=tmp+first+second;
        }
        return third;
    }
};