1137.第-n-个泰波那契数.md

1137.第-n-个泰波那契数

/*
 * @lc app=leetcode.cn id=1137 lang=typescript
 *
 * [1137] 第 N 个泰波那契数
 */

// @lc code=start
function tribonacci(n: number): number {}
// @lc code=end

解法 1: 动态规划

• 时间复杂度:
• 空间复杂度:

DP 方程: dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

function tribonacci(n: number): number {
  if (n < 1) return 0
  let [cur, pre, second] = [1, 1, 0]
  for (let i = 3; i <= n; i++) {
    ;[cur, pre, second] = [cur + pre + second, cur, pre]
  }
  return cur
}

Case

test.each([
  { input: { n: 4 }, output: 4 },
  { input: { n: 25 }, output: 1389537 },
])(`input: n = $input.n`, ({ input: { n }, output }) => {
  expect(tribonacci(n)).toBe(output)
})