【动态规划】leetcode 1137. 第 N 个泰波那契数

1137. 第 N 个泰波那契数

题目描述

泰波那契序列 $T_n$ 定义如下：

$T_0$ = 0, $T_1$ = 1, $T_2$ = 1, 且在 n >= 0 的条件下 $T_{n+3}$ = $T_n$ + $T_{n+1}$ + $T_{n+2}$

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例1：

输入： n = 4
输出： 4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例2：

输入： n = 25
输出： 1389537

提示

• $0<=n<=37$
• $答案保证是一个32位整数，即answer<=2^{31}-1。$

方法：动态规划

解题思路

1. 确定 dp 数组以及下标的含义
   dp[i] 的定义为：第 i 个泰波那契数的值
2. 确定递推公式
   状态转移方程：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
3. dp 数组如何初始化
   dp[0] = 0, dp[1] = 1, dp[2] = 1
4. 确定遍历顺序
   从递归公式 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] ; 中可以看出，dp[i] 是依赖 dp[i - 1] 、dp[i - 2] 和 dp[i - 3] 的，那么遍历的顺序一定是从前到后遍历的。
5. 举例推导 dp 数组
   按照这个递推公式 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]，我们来推导一下，当 n 为 10 的时候，dp 数组应该是如下的数列：
   0 1 1 2 4 7 13 24 44 81 149

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

代码

class Solution {
public:
    int tribonacci(int n) {
        if(n == 0 || n == 1)    return n;
        int dp[n + 1];
        dp[0] = 0, dp[1] = 1, dp[2] = 1;
        for(int i = 3; i <= n; i++)
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11

复杂度分析

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