1137. 第 N 个泰波那契数 #
- 标签:记忆化搜索、数学、动态规划
- 难度:简单
题目大意 #
描述:给定一个整数 $n$。
要求:返回第 $n$ 个泰波那契数。
说明:
- 泰波那契数:$T_0 = 0, T_1 = 1, T_2 = 1$,且在 $n >= 0$ 的条件下,$T_{n + 3} = T_{n} + T_{n+1} + T_{n+2}$。
- $0 \le n \le 37$。
- 答案保证是一个 32 位整数,即 $answer \le 2^{31} - 1$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:记忆化搜索 #
- 问题的状态定义为:第 $n$ 个泰波那契数。其状态转移方程为:$T_0 = 0, T_1 = 1, T_2 = 1$,且在 $n >= 0$ 的条件下,$T_{n + 3} = T_{n} + T_{n+1} + T_{n+2}$。
- 定义一个长度为 $n + 1$ 数组
memo
用于保存一斤个计算过的泰波那契数。 - 定义递归函数
my_tribonacci(n, memo)
。- 当 $n = 0$ 或者 $n = 1$,或者 $n = 2$ 时直接返回结果。
- 当 $n > 2$ 时,首先检查是否计算过 $T(n)$,即判断 $memo[n]$ 是否等于 $0$。
- 如果 $memo[n] \ne 0$,说明已经计算过 $T(n)$,直接返回 $memo[n]$。
- 如果 $memo[n] = 0$,说明没有计算过 $T(n)$,则递归调用
my_tribonacci(n - 3, memo)
、my_tribonacci(n - 2, memo)
、my_tribonacci(n - 1, memo)
,并将计算结果存入 $memo[n]$ 中,并返回 $memo[n]$。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。
思路 2:动态规划 #
1. 划分阶段 #
我们可以按照整数顺序进行阶段划分,将其划分为整数 $0 \sim n$。
2. 定义状态 #
定义状态 dp[i]
为:第 i
个泰波那契数。
3. 状态转移方程 #
根据题目中所给的泰波那契数的定义:$T_0 = 0, T_1 = 1, T_2 = 1$,且在 $n >= 0$ 的条件下,$T_{n + 3} = T_{n} + T_{n+1} + T_{n+2}$。,则直接得出状态转移方程为 $dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]$(当 $i > 2$ 时)。
4. 初始条件 #
根据题目中所给的初始条件 $T_0 = 0, T_1 = 1, T_2 = 1$ 确定动态规划的初始条件,即 dp[0] = 0, dp[1] = 1, dp[2] = 1
。
5. 最终结果 #
根据状态定义,最终结果为 dp[n]
,即第 n
个泰波那契数为 dp[n]
。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。