各位题友大家好，@负雪明烛 又出现了。

解题思路

本题是斐波那契数列的拓展，可以使用类似的思路。
本文分为 3 个部分，思路是 递归 => 记忆化搜索 => 动态规划。

递归

求第 n 个数的时候需要知道第 n-1 个数、第 n-2 个数、第 n-3 个数，也就是大问题被拆解成了小问题，这很符合递归的逻辑。

斐波那契数列是我们学过的第一个递归问题，相信大家都会写。本题是个简单的拓展，很快我们就写出来下面的 python 代码：

  1. class Solution(object):
  2.     def tribonacci(self, n):
  3.         if n == 0: return 0
  4.         if n == 1: return 1
  5.         if n == 2: return 1
  6.         return self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)
  • 时间复杂度：，类似于三叉树的节点数。
  • 空间复杂度：1137. 第 N 个泰波那契数 - 图1#card=math&code=O%28n%29&id=fP0r6)，栈的深度。

但是我们提交了之后，发现超时了。为什么呢？

因为，直接递归解法由于有很多的重复计算，比如计算 fib(4) 的时候需要计算 fib(3)、 fib(2) 和 fib(1)；而计算 fib(5) 的时候，又计算了一遍 fib(4)、 fib(3) 和 fib(2) 。

记忆化搜索

为了解决重复计算的问题，可以使用「记忆化搜索」，它的思路是使用字典保存计算过的 fib(n)。当计算 fib(n + 1)的时候，就可以从字典中直接获取 fib(n)，省去了重复的计算，速度很快。

Python 代码如下：

  1. class Solution(object):
  2.     def __init__(self):
  3.         self.memo = {0:0, 1:1, 2:1}
  5.     def tribonacci(self, n):
  6.         if n in self.memo:
  7.             return self.memo[n]
  8.         res = self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)
  9.         self.memo[n] = res
  10.         return res

在 python3 中，可以使用语言自带的「记忆化搜索」的注解：@functools.lru_cache()，它的用法只有一行，即在要执行记忆化的函数上面加上一行注解，即可在语言级别的自动化的记忆化递归。

  1. class Solution:
  2.     @functools.lru_cache()
  3.     def tribonacci(self, n: int) -> int:
  4.         if n == 0: return 0
  5.         if n == 1: return 1
  6.         if n == 2: return 1
  7.         return self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)
  • 时间复杂度：1137. 第 N 个泰波那契数 - 图2#card=math&code=O%28n%29&id=K2cbk)，因为避免了重复的计算。
  • 空间复杂度：1137. 第 N 个泰波那契数 - 图3#card=math&code=O%28n%29&id=ZZM77)，栈的深度。

动态规划

在「记忆化搜索」的基础上，再迈出一步，就能得到「动态规划」的解法。它们都是把大问题拆解成小问题的方法，但是处理思路是相反的。

  • 「记忆化搜索」：是 从顶向下 的思路，即把大问题一步步拆分成小问题；
  • 「动态规划」：是 从底向上 的思路，即先得到小问题，然后再一步步推到出大问题。

动态规划的推导过程如下。

  • 定义状态：T[i] 表示泰波那契数列的第 n 个数字；
  • 状态转移方程：T(N) = T(N - 1) + T(N - 2) + T(N - 3), 其中 N >= 3.
  • 初始条件： T(0) = 0, T(1) = 1, T(2) = 2.

Python 的代码如下：

  1. class Solution(object):
  2.     def tribonacci(self, n):
  3.         T = [0] * 38
  4.         T[0] = 0
  5.         T[1] = 1
  6.         T[2] = 1
  7.         for i in range(3, n + 1):
  8.             T[i] = T[i - 1] + T[i - 2] + T[i - 3]
  9.         return T[n]

C++ 代码如下：

  1. class Solution {
  2. public:
  3.     int tribonacci(int n) {
  4.         if (n == 0) return 0;
  5.         if (n == 1) return 1;
  6.         if (n == 2) return 1;
  7.         vector<int> T(n + 1);
  8.         T[0] = 0;
  9.         T[1] = T[2] = 1;
  10.         for (int i = 3; i <= n; ++i) {
  11.             T[i] = T[i - 1] + T[i - 2] + T[i - 3];
  12.         }
  13.         return T[n];
  14.     }
  15. };
  • 时间复杂度：1137. 第 N 个泰波那契数 - 图4#card=math&code=O%28n%29&id=L4oWl)
  • 空间复杂度：1137. 第 N 个泰波那契数 - 图5#card=math&code=O%28n%29&id=giJQR)

由于 T[i] 的状态只跟 T[i - 1] 、 T[i - 2] 、T[i - 3]有关，所以可以进行状态的压缩，从而降低空间复杂度。即使用 3 个变量 a, b, c，分别表示 T[i]、T[i + 1] 、 T[i + 2] 。

Python 代码如下：

class Solution(object):
    def tribonacci(self, n):
        a, b, c = 0, 1, 1
        for i in range(n):
            a, b, c = b, c, a + b + c
        return a
  • 时间复杂度：1137. 第 N 个泰波那契数 - 图6#card=math&code=O%28n%29&id=wUhkT)
  • 空间复杂度：1137. 第 N 个泰波那契数 - 图7

刷题心得

很多朋友经常问，不知道动态规划是怎么想出来的。我的建议还是从 递归 => 记忆化搜索 => 动态规划 一步步推出来，这 3 步是个递进的，按照这个思路更容易理解。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！