1137. N-th Tribonacci Number

Leetcode link

题目简介

/**
 * @param {number} n
 * @return {number}
 */

题目定义了一个 Tribonacci 序列：T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0

要求我们求出 Tn

解题思路

使用一个数组保存前三个，后面循环计算即可

Javascript

/**
 * @param {number} n
 * @return {number}
 */
var tribonacci = function (n) {
    const dp = [0, 1, 1]
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    }

    return dp[n]
};

复杂度分析

时间

O(n)

空间

O(n)