【动态规划】-- 第N个泰波拉契数

1. 题目

在线oj
泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+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。

2. 题目解析

1. 状态表示

动态规划的一般流程：创建一个一维的或者二维的dp表，然后想办法将dp表填满，填满之后，dp表中的某一个值可能就是最终结果。

【状态表示是什么？】：其中状态表示就是dp表中的某一个位置的值所代表的含义。其中这个含义就是状态表示。

【怎么确定状态表示？】

1. 题目要求
2. 经验 + 题目要求
3. 分析问题的过程中，发现重复子问题

本题的状态表示是直接根据题目要求所得的。
dp[i] 表示 ： 第 i 个泰波拉契数的值
2. 状态转移方程
【什么是状态转移方程?】
dp[ i ] 等于什么，什么就是状态转移方程。

本题的状态转移方程：dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] + dp[ i - 3 ]

3. 初始化
根据状态转移方程填表时，保证填表的时候不越界。

根据上面我的根据题意得出的状态转移方程，在填0位置的dp表时，会出现dp[ - 1 ]、dp[ - 2 ]、dp[ - 3 ]，此时就会越界， 同理，在填1位置和2位置时也会出现越界的问题。

所以， 初始化dp[ 0 ] = 0、dp[ 1 ] = dp[ 2 ] = 1。

4. 填表顺序
为了填写当前状态的时候所需要的状态已经计算过了。

所以，这道题的填表顺序是：从左往右。

5. 返回值
结合题目要求 + 题目要求。

所以，这道题的返回值是dp[ n ]

3. 代码

class Solution {
    public int tribonacci(int n) {
        //处理一下边界情况
        if (n == 0){
            return 0;
        }
        if (n == 2 || n == 1){
            return 1;
        }

        //1. 创建一个dp表
        int[] dp = new int[n + 1];
        //2. 初始化
        dp[0] = 0;
        dp[1] = dp[2] = 1;
        //3. 填表
        for (int i = 3; i < dp.length; i++) {
            dp[i] = dp[i - 3] + dp[i -2] + dp[i - 1];
        }
        //4. 返回值
        return dp[n];
    }
}

时间复杂度：0（N）
空间复杂度：0（N）

空间优化
动态规划 的空间优化一般都是使用滚动数组。

【分析】：在求n位置的状态时，只需要该位置前三个的状态表示，那么其余的前面的状态表示都是多余的。

在填写dp表时，仅需要所求状态的前面的部分状态表示，这样的都可以使用滚动数组来进行空间优化。
使用滚动数组来优化空间的结果：0（N^2）—> 0(N)， 0（N）—> 0（1）.

class Solution {
    public int tribonacci(int n) {

        //处理一下边界情况
        if (n == 0){
            return 0;
        }
        if (n == 2 || n == 1){
            return 1;
        }

        int a = 0;
        int b = 1;
        int c = 1;
        int d = 0;
        for (int i = 3; i <= n ; i++) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        //4. 返回值
        return d;
    }
}