【动态规划：斐波那契数列模型】第 N 个泰波那契数

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

输入：n = 25
输出：1389537

class Solution {
public:
    int tribonacci(int n) {
        // 创建dp表
        int dp[38];

        // 初始化
        dp[0] = 0;
        dp[1] = dp[2] = 1;

        // 通过状态转移方程填表
        for(int i = 3; i <= n; ++i)
        {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        // 返回值
        return dp[n];
    }
};

class Solution {
public:
    int tribonacci(int n) {
        // 特殊情况
        if(n == 0)
            return 0;
        if(n == 1 || n == 2)
            return 1;

        // 初始化
        int a = 0, b = 1, c = 1, ret = 0;

        // 通过状态转移方程填表
        for(int i = 3; i <= n; ++i)
        {
            ret = a + b + c;
            a = b;
            b = c;
            c = ret;
        }

        // 返回值
        return ret;
    }
};