第 N 个泰波那契数

迭代

  1. 复杂度：

    • 时间复杂度：O(n)；
    • 空间复杂度：O(1)；

  2. 代码实现：

    function tribonacci(n: number): number {
  let memo = [0, 1, 1];
  let res = 0;

  if (n < 3) return memo[n];

  for (let i = 3; i <= n; i++) {
    res = memo[0] + memo[1] + memo[2];
    memo[0] = memo[1];
    memo[1] = memo[2];
    memo[2] = res;
  }

  return res;
}

递归

  1. 复杂度：

    • 时间复杂度：O(n)；
    • 空间复杂度：O(n)；

  2. 代码实现：

    function tribonacci(n: number): number {
  var list = [0, 1, 1];

  function reverse(memo, n) {
    if (n < 3) return list[n];
    if (memo[n]) return memo[n];

    memo[n] = reverse(memo, n - 1) + reverse(memo, n - 2) + reverse(memo, n - 3);
    return memo[n];
  }

  return reverse(list, n);
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 第 N 个泰波那契数
  2. 2. 迭代
  3. 3. 递归