LeetCode第 N 个泰波那契数 (认识动态规划)

**LeetCode第 N 个泰波那契数**

泰波那契数列是这样一个序列：1、1、2、4、7、11、16、22、29、37、46、56、67、79、92、...。这个序列的每个数字都是前两个数字之和。

在 LeetCode 上，有一道题目要求我们找出第 N 个泰波那契数。也就是说，我们需要写一个函数，能够计算出给定数字 N 的时候，泰波那契数列中的第 N 个数字是多少。

**动态规划**

这个问题可以使用动态规划来解决。动态规划是一种算法思想，它通过分解大问题成小问题，然后逐步求解这些小问题，最终得到大问题的答案。

在本题中，我们可以先定义一个数组，用于存储前 N 个泰波那契数列中的数字。然后，我们可以使用这个数组来计算出第 N 个数字。

**代码示例**

def tribonacci(n: int) -> int:
 """
 计算第 N 个泰波那契数。
 Args:
 n (int): 需要计算的泰波那契数列中的位置。
 Returns:
 int: 第 N 个泰波那契数。
 """
 # 如果 n 是0 或1，直接返回对应的数字 if n ==0:
 return0 elif n ==1 or n ==2:
 return1 # 初始化数组，用于存储前 N 个泰波那契数列中的数字 dp = [0] * (n +1)
 dp[0] =0 dp[1] =1 dp[2] =1 # 使用动态规划计算出第 N 个数字 for i in range(3, n +1):
 dp[i] = dp[i -1] + dp[i -2] + dp[i -3]
 # 返回第 N 个数字 return dp[n]

# 测试函数print(tribonacci(10)) # 输出：114

**代码注释**

* `tribonacci(n: int) -> int`：这是函数的定义，表示该函数接受一个整数参数 `n`，并返回一个整数。
* `if n ==0:`：如果 `n` 等于0，则直接返回0，因为泰波那契数列中的第0 个数字是0。
* `elif n ==1 or n ==2:`：如果 `n` 等于1 或2，则直接返回1，因为泰波那契数列中的第1 和第2 个数字都是1。
* `dp = [0] * (n +1)`：初始化一个长度为 `n +1` 的列表 `dp`，用于存储前 N 个泰波那契数列中的数字。列表的索引从0 开始，因此需要加1。
* `for i in range(3, n +1):`：使用循环来计算出第 N 个数字。循环从3 开始，因为我们已经知道了前两个数字（即1 和1）。
* `dp[i] = dp[i -1] + dp[i -2] + dp[i -3]`：在每次迭代中，计算出当前位置的数字。这个数字是前三个数字之和。
* `return dp[n]`：返回第 N 个数字。

**总结**

本题使用动态规划来解决。我们首先定义一个数组，用于存储前 N 个泰波那契数列中的数字，然后使用这个数组来计算出第 N 个数字。通过循环和简单的运算，我们可以轻松地得到第 N 个数字。

**参考资料**

* LeetCode： />* 动态规划：