题目描述

Tribonacci 序列 TnTn 定义如下：

T0=0,T1=1,T2=1T0=0,T1=1,T2=1，且对于 n>=0n>=0，有 Tn+3=Tn+Tn+1+Tn+2Tn+3=Tn+Tn+1+Tn+2。

给定 n，返回 TnTn 的值。

样例

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

输入：n = 25
输出：1389537

限制
0 <= n <= 37
答案保证在 32 位整数内，即 answer <= 2^31 - 1。

算法

(DFS) $O(n)$

和斐波那契数列做法差不多，加个备忘录记录算过的值。

Java 代码

class Solution {
    Map<Integer, Integer> memo = new HashMap<>() {{
        put(0, 0);
        put(1, 1);
        put(2, 1);
    }};

    public int tribonacci(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        int res = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
        memo.put(n, res);
        return res;
    }
}